Auf GPU rechnen

Heutige Rechner haben bekanntlich sehr leistungsfähige CPUs mit „Quadcore“ und mehr.
Aber auch die Grafikkarten sind ziemlich toll geworden und haben zum Teil auch so große eigene Lüfter wie die CPU.
Sie haben eine Menge eigenes Memory und sie können recht komplizierte Operationen selbsttätig rechnen, natürlich nur für die grafische Darstellung.

Nun stellt sich die Frage, ob man das auch sonst zum Rechnen benutzen kann. Man hört Geschichten, dass die Grafikkarte um Größenordnungen leistungsfähiger als die CPU sei. Warum schaffen das die Grafikkartenhersteller so leicht nebenbei, besser als die CPU in deren Kernaufgabe zu sein und außerdem noch Grafik darzustellen?

Grafikkarten bieten die Möglichkeit, massiv parallel zu rechnen, aber nach dem Prinzip SIMD. Das heißt, dass ein oder sehr wenige Befehlsströme verarbeitet werden und eine große Zahl von Recheneinheiten jeweils den identischen Code mit verschiedenen Daten ausführt. Für Vektoroperationen ist das optimal. Und es erklärt auch die brachiale Leistung der Grafikchips, weil man den aufwändigen Teil, Maschinencode zu interpretieren, nur einmal (oder wenige Male) baut und nur die eigentliche Recheneinheit mehrfach. Man bekommt so mit derselben Siliziummenge mehr Rechenleistung, aber mit der Einschränkung, SIMD (oder fast SIMD) zu sein. Aber man hat diese Geräte in den Rechnern drin. Es gibt sogar „Grafikkarten“, die nur rechnen können, aber bei denen man die eigentlichen Grafikchips weggelassen hat. Und viele Rechner haben den Grafikkern mit auf dem selben Chip wie die CPU-Kerne, so dass man eine einfache Grafik zur Verfügung hat, aber man baut dann doch zusätzlich noch eine externe Grafikkarte ein, die noch besser ist. Selbst ohne die Grafikfähigkeit zu gefährden hat man also eine GPU zum Rechnen übrig.

Nun ist das Programmieren dieser Geräte nicht so einfach. Grundsätzlich muss man sich mit einem völlig neuen Programmiermodell herumschlagen. Viele Algorithmen lassen sich speziell für SIMD entwickeln, aber sie sind anders als was wir gewohnt sind und automatisch lässt sich da nur beschränkt etwas optimieren. In der Regel muss man also mit C das Programm schreiben und kann dabei auf OpenCL bauen. Das ist ein nützlicher Standard, der einiges erleichtert, aber es bleibt schwierig. Für manche Zwecke lohnt es sich aber, den Entwicklungsaufwand zu treiben.

Vor ein paar Tagen habe ich drei Vorträge über Ansätze gehört, F# zu verwenden, um die GPU zu programmieren. Man kann also unter Einhaltung gewisser Regeln F#-Programme schreiben, die sich etwa in OpenCL übersetzen lassen und dann compiliert die GPU nutzen:

  • FSCL: Homogeneous Programming and Execution on Heterogeneous Platforms (by Gabriele Cocco, Pisa University)
  • Professional GPU Development with F# and the Alea Compiler Suite (by Daniel Egloff, QuantAlea)
  • New Abstractions for Radically Simplified GPU Programming in F# and .NET (by Luc Bläser, HSR, based on joint work with QuantAlea)

All diese Ansätze sollten schon heute oder zumindest in zukünftigen Implementierungen auch für Mono laufen und damit für Linux zur Verfügung stehen.

Es würde wohl den Rahmen dieses Artikels sprengen, im Einzelnen darauf einzugehen, aber vielleicht kann ich noch Links bekommen, die auf weiterführendes Material zu den einzelnen Lösungsansätzen führen.

Share Button

Elixir II

Da ich das Glück hatte, an einer halbtägigen Elixir-Schulung teilzunehmen, möchte ich das Thema wieder aufgreifen.

Elixir ist eine relativ neue Programmiersprache, die sich von der Syntax an Ruby anlehnt. Die Programme laufen auf der Erlang-VM (BEAM). Diese VM ist anscheinend restriktiver als die Java-VM und so ist Elixir von den Konzepten her auch sehr nahe an Erlang.

Grundsätzlich ist Elixir wie Erlang eine funktionale Sprache, nicht wie Ruby objektorientiert. Es gibt aber die Möglichkeit, Strukturen aus Listen und Tupeln aufzubauen und weiterzugeben. Alle diese Strukturen sind immutable. Das heißt, dass Änderungen daran stets das Original unverändert lassen und eine Kopie mit den Änderungen generieren. Im Falle von verketteten Listen funktioniert das gut, wenn man nur am Anfang ein Element hinzufügt, weil dann kein eigentliches Kopieren erforderlich ist. Fügt man am Ende etwas hinzu, muss die Liste kopiert werden, was eine aufwändigere Operation ist. Es gibt keine Schleifen, wie in den meisten herkömmlichen Programmiersprachen, sondern man verwendet stattdessen Rekursion. Endrekursion sollte bevorzugt werden, weil das intern in Schleifen umgewandelt wird. Über die Parameterliste dieser Funktion kann man einen „Zustand“ weiterreichen.

Es ist sehr einfach und auch üblich, „Prozesse“ zu generieren. Dies sind nicht OS-Prozesse, sondern Konstrukte innerhalb von Erlang, man kann etwa an Aktoren denken, wie es bei Scala und Akka genannt wird. Wenn genug Hardware-Ressourcen vorhanden sind, kann man ohne weiteres mehrere Millionen solcher „Prozesse“ gleichzeitig haben. Jeder Prozess hat seinen eigenen Speicher und kann jedem anderen Prozess mit

send(...)

Nachrichten (messages) senden. Diese werden in eine sogenannte Mailbox (eine Warteschlange / engl. Queue) des Prozesses eingefügt und von diesem mit

receive(...)

empfangen. Das typische Muster ist, dass ein Prozess mittels Rekursion in einer Endlosschleife ist und jeweils mit receive Messages empfängt und verarbeitet.

Über diese Prozesse kann man doch so etwas wie einen Zustand modellieren. Man hat einfach einen Prozess mit so einer Endlosschleife und schickt ihm „set“- und „get“-Nachrichten. Die „set“-Nachrichten ändern den Zustand, der in der Endlosschleife über die Parameter weitergereicht wird, die get-Nachrichten lösen aus, dass eine Nachricht an den Absender geschickt wird, die dieser wiederum mit receive abfangen muss.

Funktionen mit gleichem Namen werden nach der Anzahl der Parameter, nicht aber nach dem Typ der Parameter, unterschieden. Die Sprache ist dynamisch typisiert. Man kann statt ein großes „if“ innerhalb einer Funktion zu haben, diese auch für verschiedene Fälle definieren und es wird für den tatsächlichen Aufrufparameter die richtige Teildefinition gefunden.

Share Button

Sortieren mit Multithreading

Eine Barriere muss man sich so vorstellen, dass verschiedene Threads jeweils ihre eigene Aufgabe durchführen und dann auf die Barriere „warten“, was bedeutet, dass sie darauf warten, dass alle anderen beteiligten Threads auch auf die Barriere warten, also die davor angesetzte Aufgabe abgeschlossen haben.

Als Anwendung für die sogenannte „Barriere“ habe ich einmal ein kleines C-Programm geschrieben, das eingelesene Zeichenketten sortiert. Über einen Parameter kann man wählen, ob Heapsort oder Flashsort oder Quicksort verwendet wird. Dafür habe ich zwei Funktionen (mit Header-Datei) hsort und hsort_r geschrieben, die das gleiche Interface wie qsort und qsort_r haben, so dass man sie austauschbar nutzen kann. Entsprechend auch drei Funtkionen fsort, fsort_r und fsort_f (mit Headern), die sich an das Interface von qsort anlehnen, aber noch einen zusätzlichen Funktionisparameter haben, der eine Art monotone Hash-Funktion nach double darstellt. Die gegebenen Zeichenketten werden zu möglichst gleichen Teilen auf eine frei wählbare Anzahl Threads verteilt. Jeder Thread sortiert seinen Teil mittels hsort_r oder fsprtr oder qsort_r. Anschließend wird mit einer Barriere sichergestellt, dass alle Threads ihren Teil sortiert haben und dann werden baumartig die Ergebnisse von jeweils zwei Threads zusammengefügt, jeweils gefolgt von einer weiteren Verwendung Barriere. An Schluss bleibt ein Thread mit seinem Ergebnis übrig und das ist das Sortierergebnis.

Bei einer Beispieleingabe mit 8603049 Wörtern war fsort mit einem Thread etwas schneller als qsort und qsort war etwa viermal so schnell wie hsort, aber mit einer größeren Anazhl Threads ließen sich alle drei beschleunigen.
Interessant war auf einem Rechner mit 4 Core-CPU und Hyperthreading, also 8 logischen CPUs, die unter /proc/cpuinfo angezeigt wurden, dass das Sortieren mit mehr Threads bei hsort mehr profitierte als bei qsort und um Faktor 5 schneller wurde, während fsort nur um Faktor 2 schneller wurde.

Das erklärt sich wohl vor allem durch das assymptotisch gute Verhalten von fsort (O(n)), was beim Sortieren großer Datenmengen in einem Thread besonders stark zum Tragen kommt. hsort ist im „worst case“ auch noch O(n \log n)

Threads Messwert Quicksort Heapsort Flashsort
1 real 4.090s 16.909s 3.757s
1 user 4.028s 16.815s 3.686s
1 sys 0.053s 0.053s 0.062s
           
2 real 2.753s 8.915s 2.672s
2 user 4.177s 16.457s 3.925s
2 sys 0.074s 0.054s 0.066s
           
3 real 2.333s 6.584s 2.392s
3 user 4.261s 16.676s 4.159s
3 sys 0.070s 0.064s 0.067s
           
4 real 2.027s 5.288s 2.093s
4 user 4.331s 16.202s 4.137s
4 sys 0.067s 0.072s 0.077s
           
5 real 2.151s 5.013s 2.254s
5 user 4.681s 17.423s 4.567s
5 sys 0.060s 0.056s 0.076s
           
6 real 2.039s 4.519s 2.104s
6 user 5.264s 18.511s 4.892s
6 sys 0.072s 0.062s 0.078s
           
7 real 1.928s 4.127s 2.092s
7 user 5.333s 18.878s 5.265s
7 sys 0.080s 0.056s 0.094s
           
8 real 1.862s 3.879s 1.931s
8 user 5.638s 19.338s 5.380s
8 sys 0.080s 0.061s 0.069s
           
9 real 2.032s 4.079s 2.174s
9 user 5.484s 19.594s 5.460s
9 sys 0.072s 0.066s 0.081s
           
10 real 2.017s 4.040s 2.130s
10 user 5.426s 19.091s 5.356s
10 sys 0.084s 0.080s 0.090s
           
11 real 1.954s 4.055s 2.081s
11 user 5.427s 19.240s 5.460s
11 sys 0.077s 0.081s 0.095s
           
12 real 1.928s 3.842s 2.053s
12 user 5.409s 18.860s 5.462s
12 sys 0.078s 0.075s 0.092s
           
13 real 1.923s 3.884s 2.040s
13 user 5.384s 19.123s 5.511s
13 sys 0.077s 0.072s 0.080s
           
14 real 1.870s 3.793s 2.037s
14 user 5.482s 18.566s 5.610s
14 sys 0.064s 0.070s 0.089s
           
15 real 1.895s 3.679s 1.979s
15 user 5.578s 18.549s 5.554s
15 sys 0.090s 0.067s 0.084s
           
16 real 1.861s 3.790s 1.979s
16 user 5.576s 19.033s 5.640s
16 sys 0.088s 0.085s 0.101s
           
17 real 2.025s 3.885s 2.181s
17 user 5.647s 18.699s 5.799s
17 sys 0.090s 0.076s 0.102s
           
18 real 2.019s 3.879s 2.156s
18 user 5.688s 18.532s 5.723s
18 sys 0.069s 0.107s 0.095s
           
19 real 2.022s 3.918s 2.140s
19 user 5.774s 18.783s 5.681s
19 sys 0.093s 0.085s 0.091s
           
20 real 1.975s 3.774s 2.129s
20 user 5.588s 18.095s 5.732s
20 sys 0.093s 0.087s 0.105s
           
100 real 1.978s 3.263s 2.099s
100 user 5.686s 15.371s 6.034s
100 sys 0.150s 0.115s 0.141s
           
400 real 2.013s 2.996s 2.092s
400 user 5.719s 13.150s 6.184s
400 sys 0.242s 0.185s 0.259s
           
1000 real 1.992s 2.876s 2.106s
1000 user 5.802s 12.608s 6.469s
1000 sys 0.325s 0.250s 0.392s

Man sieht also, was auch zu erwarten ist, dass Parallelisierung beim Sortieren hilfreich sein kann. In diesem Fall eignet sich der Algorithmus gut für die Parallelisierung, weil im ersten Schritt jeder Thread seinen getrennten Bereich sortiert und in den weiteren Schritten jeweils ein Thread die eigenen Daten mit denen eines anderen Threads zusammenfügt, während dieser andere Thread nur auf die Barriere wartet. Es gibt sicher noch bessere Verfahren, das zu parallelisieren, aber man sieht, dass es sich lohnt, wenn man wirklich genug CPUs zur Verfügung hat.

Share Button

Elixir

English

Wenn es darum geht, hochperformante, skalierbare und hochverfügbare Applikationen zu entwickeln, die die Parallelisierungsmöglichkeiten der heutigen Hardware gut ausnutzen, ist Erlang ein Klassiker. Dieses verwendet eine virtuelle Maschine (BEAM), ähnlich wie Java und wie die meisten modernen interpretierten Sprachen. Erlang ist funktional und verwendet eigene Prozesse, die man eher als Aktoren denn als Betriebssystemprozesse verstehen sollte, zwischen denen via Messages kommunziert wird.

So wie in der IT-Welt die Java-VM sehr geschätzt wird, und sei es auch nur wegen ihrer großen Verbreitung und des Knowhows im Betrieb, so hat doch das Bedürfnis nach bessere Programmiersprachen für die Java-VM zu Entwicklungen wie Scala, JRuby, Clojure, Groovy, Ceylon und Dutzenden, weiteren Sprachen für die Java-VM geführt.

Diese Idee bringt nun Elixir in die Erlang-Welt. Die Sprache ist noch im Alpha-Stadion und wir werden sehen, was sich daraus entwickelt. Die Idee ist grundsätzlich, dass man eine Syntax verwendet, die sich an Ruby anlehnt, einige Ideen aus Clojure übernimmt und natürlich dann die Möglichkeiten und Paradigmen der Erlang-Welt in diesem Rahmen anbietet. Man hat also auch wieder beliebig viele „Prozesse“, wiederum im Sinne des Aktoren-Patterns, nicht als Betriebssystemprozesse oder -threads und eine Kommunikation via Messages.

Es ist sicher interessant, zu beobachten, wie sich das entwickelt und wie brauchbar es in Bezug auf Performance und Stabilität im Vergleich mit Erlang, aber auch mit JVM-basierten Lösungen wie dem Akka-Framework mit Scala sein wird.

Links dazu

Share Button

Alles Immutable: Wie geht das?

Ein radikaler Ansatz, um Multithreading zu vereinfachen, ist es „alles“ immutable zu machen. Man meint, dass das in Java schon recht gut der Fall ist, sind doch Objekte von grundlegenden Klassen wie String, Long, Integer, BigInteger, BigDecimal u.s.w. immutable. Date ist ein bisschen ein Spezialfall, da es fast immer verwendet wird, als wäre es immutable, was aber in Wirklichkeit nicht stimmt.

Aber die Collection-Klassen sind natürlich a priori fast alle mutable. Müssen sie ja sein, weil es z.B. keine vernünftige Schreibweise für eine Map gibt und man sie deshalb sukzessive aufbauen muss. Zwar gibt es die unmodifiable-Wrapper in Collections, aber wenn man Zugriff auf die eingebaute Collection hat, kann man diese immer noch ändern, was zu Überraschungen führen kann.

Die üblichen Collections in Clojure funktionieren anders. Sie sind wirklich immutable. Wenn man also so etwas ähnliches wie ein map.put(k, v) oder map[k]=v in Clojure macht, wird map selber nicht verändert, sondern es wird eine Kopie zurückgegeben, die zusätzlich das neue Paar enthält.

Hier ein Beispiel:

user=> (def x (hash-map 3 4 5 6))
#'user/x
user=> x
{3 4, 5 6}
user=> (def y (assoc x 7 8))
#'user/y
user=> y
{3 4, 5 6, 7 8}
user=> x
{3 4, 5 6}

Man kann sich vorstellen, dass da tatsächlich immer Kopien gemacht werden. Dann würde Clojure natürlich für größere Programme exorbitant Speicher verbrauchen und wäre auch sehr langsam.

Man muss sich eher vorstellen, dass ausgenutzt wird, dass auch die Eingaben immutable sind und dass geschickte interne Datenstrukturen sicherstellen, dass man das Verhalten bekommt, als wäre es kopiert worden, aber intern Optimierungen stattfinden, die mehrfach benutzte Daten gemeinsam nutzen.

Share Button

Entwicklung der Hardware: Parallelisierung

English

Bis etwa einigen Jahren konnte man davon ausgehen, daß sich die Taktfrequenz von gängigen Mikroprozessoren regelmäßig erhöht und bei der Entwicklung neuer Software darauf vertrauen, daß die Hardware zumindest in naher Zukunft leistungsfähig genug sein würde, um gewisse Ineffizienzen zu kompensieren. Nun ist die Leistungsfähigkeit eines Rechners von sehr viel mehr Faktoren als der Taktfrequenz abhängig, vor allem auch davon, wieviele Operationen in einem Takt bzw. wieviele Takte für eine Operation benötigt werden. Wichtig ist erfahrungsgemäß aber auch ein genügend großer Hauptspeicher und natürlich gewisse Optimierungen auf der Platine und auf dem Chip, die man gar nicht so explizit wahrnimmt und auch nicht so leicht ändern kann. Grundsätzlich ist aber die Leistung einzelner CPU-Kerne nur noch langsam gestiegen, man bekommt aber ohne weiteres einen Chip, auf dem mehrere CPU-Kerne implementiert sind. Dualcore, Quadcore u.s.w. sind ja gut bekannt. Ein Link dazu: The Free Lunch is Over

Nun kann man diese mehrfachen Prozessoren mit einer einzelnen Ressourcen-hungrigen Applikation nutzen, wenn diese mehrere parallel verlaufende Threads oder Prozesse verwendet. Leider gibt es dabei ein paar Probleme. Das ärgerlichste ist, daß man zwar viele Entwickler findet, die sagen, das zu können, aber daß die Sache nachher tatsächlich stabil funktioniert, ist leider seltener. Häufig erlebt man Schönwetter-Software. Auf dem Rechner des Entwicklers funktioniert sie prima, vielleicht auch auf dem Testsystem. Aber im produktiven Einsatz treten dann obskure Fehler auf, die niemand nachvollziehen kann. Oder die verschiedenen Threads und Prozesse warten so oft gegenseitig aufeinander, daß in Wirklichkeit im Durchschnitt doch nur eine CPU genutzt wird. Oder das System blockiert sich selbst („Verklemmung“ oder engl. „dead-lock“). Natürlich nicht auf dem Rechner des Entwicklers, weil die spezielle Situation, die dazu führt, nur unter Last im produktiven Einsatz zum ersten Mal auftritt. Was lernt man daraus? Für diese Art von Architektur braucht man sehr gute Entwickler, die sich die parallelen Abläufe vorstellen können und die genug Erfahrung damit haben. Und man sollte sich nicht zu weit aus dem Fenster lehnen, sondern Dinge entwickeln, die zwar die Parallelität ausnutzen, aber doch robust genug sind, um nicht nur knapp zu funktionieren. Außerdem ist es wichtig, mir sehr realitätsnahen Daten und Datenmengen zu testen und auch Lasttests durchzuführen. Auf Testsystemen, die den späteren Produktivsystemen ähneln.

Ein anderer Ansatz löst das ganze Problem durch Frameworks. Es gibt sicher gute und leichtgewichtige Frameworks, aber bei gängigen Frameworks wie JEE (früher J2EE) brauchen diese schon selbst so viele Ressourcen und sie schränken die Möglichkeiten bei der Entwicklung so stark ein, daß man zumindest den Vorteil des einfacheren Multithreadings sofort wieder verliert, weil das Framework selber jetzt einen großen Teil der Rechenleistung und des Hauptspeichers in Anspruch nimmt. Es mag andere gute Gründe geben, solche Frameworks mit JEE-Applikationsservern einzusetzen, aber der Performance-Gewinn durch Parallelisierung hält sich normalerweise in Grenzen.

Das Problem ist immer wieder, daß man Datenstrukturen hat, die von mehreren Threads oder Prozessen manipuliert werden können und daß dadurch Probleme auftreten, die sich zwar handhaben lassen, die aber in der Praxis große Schwierigkeiten bereiten.

Zwei radikale Ansätze sind:

  • Verzicht auf gemeinsam genutzte Datenstrukturen
  • Verwendung von unveränderbaren Datenstrukturen

Der erste Ansatz ist zum Beispiel bei Entwicklung mit Ruby oder mit C gut möglich, weil die einzelnen Prozesse relativ wenig Hauptspeicher verbrauchen und man sich so leisten kann, mehr Prozesse gleichzeitig laufen zu lassen. Nun kann man mit verschiedenen Mechanismen Interprozeßkommunikation durchführen, z.B. unter Linux und Unix mit Posix-IPC oder mit TCP/IP. Das funktioniert vor allem dann gut, wenn man relativ unabhängige Prozesse hat, die nur wenig miteinander kommunizieren müssen. Und auch dafür braucht man ähnlich gute Entwickler wie beim Multithreading, die IPC gut beherrschen, außer man hat das Glück, daß die Prozesse so unabhängig voneinander laufen, daß sie gar nicht miteinander kommunizieren müssen. Vielleicht hat Erlang diese Idee in praktikabler Form umgesetzt. Dort kann man mit einer großen Anzahl von Prozessen arbeiten, die völlig voneinander getrennte Speicherbereiche für ihre Daten haben, während es ein Messaging-System für die Kommunikation zwischen diesen Prozessen gibt.

Die andere Idee, alle geteilten Datenstrukturen unveränderbar („immutable“) zu machen, wird z.B. von Scala und Clojure umgesetzt. Der Nachteil, daß man statt ein Objekt zu ändern, nur eine Kopie mit dieser Änderung erzeugen kann, wird durch Mechanismen abgemildert, die in gewissen Fällen intern so ein Kopieren durch teilweise Referenzierung des Eingabeobjekts ersetzen. Das gibt es auch in einem einfachen Fall in Java, wo der Zeichenketten-Type (String) immutable ist und wo Teile der Zeichenkette, die mittels substring() erzeugt werden, dieselbe interne Struktur wie die ursprüngliche Zeichenkette referenzieren.

In jedem Fall muß man sich aber über Abhängigkeiten der Prozesse und Threads untereinander Gedanken machen, damit man keine „dead-locks“ baut. Mit Scala und Clojure ist es aber möglich, leichtgewichtige Frameworks zu bauen, die die Ausführung von sehr vielen Threads gleichzeitig erlauben, weil das Versprechen der Unveränderbarkeit der geteilten Objekte viele Probleme eliminiert. Twitter benutzt zum Beispiel intern Scala und ist damit in der Lage, auch bei Ereignissen, die sehr viel Kommunikationsbedarf auslösen, mit der Last fertigzuwerden.

Ein Problem prinzipieller Natur bleibt natürlich, wenn der Kommunikationsbedarf zwischen den Prozessen sehr groß ist. In einem großen System können nicht alle Kommunikationspfade optimal schnell sein, denn bei n parallelen Prozessoren gibt es {n(n-1)\over2} Kommunikationspaare, was für große n mit dem Quadrat der Anzahl der Prozessoren wächst, also zu Kompromissen zwingt. Man bekommt entweder bei einem gemeinsamen Kanal Kapazitätsprobleme oder man muß bei getrennten Kanälen neben Pfaden zu den direkten Nachbarn auch auf zusammengesetzte Verbindungen setzen. Um es plastisch zu beschreiben: Eine wirklich große Applikation läuft verteilt über mehrere Rechenzentren, in denen es jeweils mehrere Racks gibt. Die Racks haben jeweils mehrere Rechner, die Rechner mehrere CPUs und die CPUs mehrere Kerne. Mit viel Geld kann man raffiniertere Hardware bauen, wo eine größere Anzahl von CPU-Kernen schnell miteinander kommunizieren kann, aber in unmittelbarer Nachbarschaft eines CPU-Kerns mit maximal schneller Kommunikation lassen sich nur begrenzt viele andere CPU-Kerne unterbringen.

Eine Idee war, eine große Anzahl von Rechnern topologisch in einem Hyperwürfel anzuordnen. Man hat also 2^n Teilrechner in Positionen, die den gedachten Ecken eines n-dimensionalen Würfels entsprechen und die Kanten dieses Hyperwürfels sind die leistungsfähigen Verbindungen dazwischen. So kommt man mit maximal n Schritten zu jeder anderen Teilrechner und kann auch in n Schritten ein Zwischenergebnis von allen Teilrechnern aggregieren und danach wieder verteilen. Weiß jemand, welche Ansätze man in heutigen Hochleistungsrechnern mit sehr vielen CPUs wählt?

Grundsätzlich kann eine Berechnung mit wenig Kommunikationsbedarf der Teilprozesse sehr gut parallel ablaufen, aber ein hoher Kommunikationsbedarf kann den Gewinn durch die Parallelisierung zunichte machen.

Share Button