User:Kortasch/Collective operation German
Kollektive Operationen sind Grundbausteine für Interaktionsmuster die häufige Anwendung in SPMD Algorithmenund parelleler Programmierungparalleler Programmierung finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.
Das Message_Passing_Interface[1] (MPI) stellt eine Implementierung der kollektiven Operationen bereit. DSC
Definitionen
[edit]In der asymptotischen Laufzeitanalyse sei die Latenz , die Bandbreite , die Anzahl der Prozessoreinheiten und die Größe der Eingabe pro Knoten . Für Operationen die mit Nachrichten auf verschiedenen Prozessoreinheiten starten nehmen wir an, dass alle lokalen Nachrichten die gleiche Größe haben. Um einzelne Prozessoreinheiten zu bezeichnen verwenden wir .
Aus den angegebenen Laufzeiten lässt sich eine obere Schranke für den Fall bestimmen, dass die initialen Nachrichten unterschiedliche Größen haben, habe Prozessoreinheit eine Nachricht der Größe . Dann setze man
Es wird das Modell eines verteilten Speichers angenommen. Dieses Modell ist konzeptionell ähnlich zum Modell eines geteilten Speichers. Bei geteilten Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt [2]. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.
![There are three squares vertically aligned on the left and three squares vertically aligned on the right. A dotted line connects the high left and high right square. Two solid lines connect the high left square and the middle and low right sqaure. The letter a is written in the high left square and in all right squares.](http://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Broadcast_%28collective_operation%29.png/220px-Broadcast_%28collective_operation%29.png)
Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in SPMD parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion (§ Reduktion) aufgefasst werden. Zu Beginn enthält die Wurzel für ein festes die Nachricht . Hier nehmen wir an, um die Erklärung simpler zu gestalten. Während des Broadcast wird an die restlichen Prozessoreinheiten gesendet, sodass schlussendlich auf allen Prozessoreinheiten verfügbar ist.
Da die triviale Implementierung die in Iterationen jeweils direkt von an übermittelt, nicht ausreichend performant ist, wird ein Ansatz der das Prinzip 'Teile-und-herrsche-Verfahren' nutzt verwendet. Sofern eine Zweierpotenz ist, kann ein Binomialbaum als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit ist verantwortlich, die Nachricht an Prozessoreinheiten weiterzuleiten. Dann sendet die Nachricht an mit . Die Verantwortung für die Übermittlung von an Prozessoreinheiten mit Indizes wird an übertragen, ist im Folgenden nur noch für die Übermittlung von an die Prozessoreinheiten mit Indizes zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die empfängt, erst dann die Nachricht weiterleiten kann, wenn vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird in ein Array aus Paketen der Größe zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.
Broadcast mit Pipelining auf einem balancierten Binärbaum ist in Laufzeit möglich.
![There are three squares vertically aligned on the left and three squares vertically aligned on the right. A circle with the letter f inside is placed between the two columns. Three solid lines connect the circle with the left three squares. One solid line connects the circle and the high right square. The letters a, b and c are written in the left squares from high to low. The letter alpha is written in the top right square.](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fe/Reduce.png/220px-Reduce.png)
Das Muster Reduktion wird genutzt, um Daten oder partielle Ergebnisse verschiedener Prozessoreinheiten zu sammeln und in ein globales Resultat zu vereinigen. Reduktion kann als inverse Operation zum Broadcast (§ Broadcast) aufgefasst werden. Sei ein assoziativer Operator, die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis und speichert es auf Prozessoreinheit . Manche Algorithmen fordern, dass zusätzlich kommutativ ist. Häufige Operatoren sind .
Da Reduktion als inverser Broadcast aufgefasst werden kann, gelten die gleichen Randbedingungen für eine Implementierung. Um pipelining zu ermöglichen ist es wichtig, dass die Nachricht als Vektor kleinerer Objekte repräsentiert werden kann, sodass eine komponentenweise Reduktion durchgeführt werden kann.
Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit möglich.
![There are three squares vertically aligned on the left and three squares vertically aligned on the right. A circle with the letter f inside is placed between the two columns. Three solid lines connect the circle with the left three squares. One solid line connects the circle and the high right square. The letters a, b and c are written in the left squares from high to low. The letter alpha is written in the top right square.](http://upload.wikimedia.org/wikipedia/commons/thumb/7/70/All-Reduce.png/220px-All-Reduce.png)
Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit die Nachricht . Das Ergebnis liegt nach dem All-reduce auf allen vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast. Auch bei All-reduce muss assoziativ sein.
Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer Hyperwürfel-Topologie verbessert werden, sofern eine Zweierpotenz ist.
Wir sehen, dass All-reduce in möglich ist, da Reduktion und Broadcast jeweils in möglich sind.
![There are three squares vertically aligned on the left and three rectangles vertically aligned on the right. A circle with the word scan inside is placed between the two columns. Three solid lines connect the circle with the left three squares. Three solid lines connect the circle with the three right square. The letters a, b and c are written in the left squares from high to low. In the high right square the letter a is written. In the mid right square the term a plus b is written. In the low right square the term a plus b plus c is written.](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f0/Prefix-Sum_%28Scan%29.png/220px-Prefix-Sum_%28Scan%29.png)
Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators Zwischenergebnisse zu berechnen. Die Zwischenergebnisse werden auf den einzelnen Prozessoreinheiten gespeichert. Die Präfixsumme kann als Generalisierung des Musters Reduktion aufgefasst werden. Wie in Reduktion und All-reduce wird vom Operator mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind .
Nach Abschluss der Präfixsumme enthält Prozessoreinheit die Nachricht . Im Sonderfall der exklusiven Präfixsumme wird stattdessen berechnet. Manche Algorithmen fordern zudem, dass zusätzlich zur Präfixsumme auch die vollständige Summe auf jeder Prozessoreinheit gespeichert wird, dass also Präfixsumme und All-reduce kombiniert werden.
Für kurze Nachrichten kann eine optimale Implementierung durch eine Hyperwürfel-Topologie erreicht werden. Für lange Nachrichten ist der Hyperwürfel nicht effektiv, da alle Prozessoreinheiten in jedem Schritt aktiv sind und dadurch Pipelining nicht angewendet werden kann. Für lange Nachrichten ist stattdessen ein Binärbaum in Kombination mit Pipelining besser geeignet. Dabei wird die Präfixsumme in eine Aufwärts- und eine Abwärts-Phase zerlegt. Die Reduktion findet in der Aufwärts-Phase statt. Die Abwärts-Phase ist ähnlich zum Broadcast. Dabei wird die Präfixsumme berechnet, indem die Knoten je unterschiedliche Daten zu ihren linken und rechten Knoten gesendet werden. Pipelining wird wie bei Reduktion und Broadcast angewendet.
Auf einem Binärbaum ist Präfixsumme in Zeit möglich.
Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltes Rechnen. Wenn eine Prozessoreinheit die Barriere aufruft, dann wartet sie, bis alle anderen Prozessoreinheiten ebenfalls Barriere aufgerufen haben, before sie im Programm fortfährt. Die Barriere ist also eine Möglichkeit der globalen Synchronisation.
Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce (§ All-reduce) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce ist, liegt die Laufzeit der Barriere also in .
![There are three squares vertically aligned on the left and three rectangles vertically aligned on the right. A dotted line connects the high left square with the high right rectangle. Two solid lines connect the mid and low left squares with the high right rectangle. The letters a, b and c are written in the left squares from high to low. The letters a, b and c are written in the high right rectangle in a row.](http://upload.wikimedia.org/wikipedia/commons/thumb/1/17/Gather.png/220px-Gather.png)
Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht auf Prozessoreinheit , so soll nach dem Gather auf der Wurzel die Nachricht gespeichert werden. Konzeptionell entspricht Gather der Reduktion (§ Reduktion) wobei der Operator die Konkatenation der Nachrichten ist. Konkatenation ist assoziativ und erfüllt damit die Voraussetzung der Reduktion.
Durch die Nutzung des Binomialbaum-Algorithmus der Reduktion wird eine Laufzeit von erreicht. Die Laufzeit ist ähnlich zur Laufzeit see Reduktion, bis auf einen zusätzlichen Faktor der an den Term multipliziert wurde. Dieser Faktor kommt daher, dass die Größe der Nachrichten in jedem Schritt zunimmt. Dies ist durch die Konkatenation als Operator bedingt und steht im Gegensatz zu Operatoren wie , die eine konstante Nachrichtengröße über alle Schritte bedingen.
![There are three squares vertically aligned on the left and three rectangles vertically aligned on the right. Three dotted lines connect the high left square with the high right rectangle, the mid left square with the mid right rectangle and the low left square with the low right rectangle. Two solid lines connect the mid and low left squares with the high right rectangle. Two solid lines connect the high and low left squares with the mid right rectangle. Two solid lines connect the high and mid left squares with the low right rectangle. The letters a, b and c are written in the left squares from high to low. The letters a, b and c are written in all right rectangles in a row.](http://upload.wikimedia.org/wikipedia/commons/thumb/2/24/All-Gather.png/220px-All-Gather.png)
Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht auf Prozessoreinheit , soll die Nachricht auf alle Prozessoreinheiten transferiert werden.
All-gather kann auf verschiedene Arten betrachtet werden. Einerseits entspricht es dem Muster All-reduce mit der Operation Konkatenation, so wie Gather als Reduce mit Konkatenation gesehen werden kann. Andererseits entspricht es dem Muster Gather mit anschließendem Broadcast der aggregierten Nachricht mit Größe . Wir sehen, dass All-gather in Laufzeit durchgeführt werden kann.
![There are three rectangles vertically aligned on the left and three squares vertically aligned on the right. A dotted line connects the high left rectangle with the high right square. Two solid lines connect the high left rectangle with the mid and low right squares. The letters c, b and a are written in the high left rectangle in a row. The letters a, b and c are written in the right right squares from high to low.](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0f/Scatter.png/220px-Scatter.png)
Das Muster Scatter wird eingesetzt, um Daten einer Prozessoreinheit auf alle Prozessoreinheiten aufzuteilen. Es unterscheidet sich vom Broadcast insofern, als dass nicht alle Prozessoreinheiten die gleiche Nachricht erhalten. Stattdessen erhält jede Prozessoreinheit einen Ausschnitt. Es soll also die auf der Wurzel vorliegende Nachricht so verteilt werden, dass anschließend auf Prozessoreinheit die Nachricht vorliegt. Scatter kann als invertierter Gather gesehen werden.
Für Scatter lassen sich die gleichen Überlegungen wie für Gather anstellen. Das Resultat ist eine Laufzeit in .
Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für ist die Nachricht, die zu Beginn auf Prozessoreinheit vorliegt und nach der Operation auf Prozessoreinheit liegt. Es hat also jede Prozessoreinheit individuelle Nachrichten für alle anderen Prozessoreinheiten. Alle anderen Muster die keine Operation benötigen lassen sich durch All-to-all ausdrücken. Beispielsweise kann Broadcast emuliert werden, bei dem die Wurzel die Nachricht verteilt emuliert werden, indem gesetzt wird und leere Nachricht für .
Sofern das Netzwerk als vollständiger Graph gesehen werden kann, ist eine Laufzeit in möglich. Dabei wird All-to-all durch Runden paarweisen Nachrichtenaustauschs implementiert. Falls eine Zweierpotenz ist, kann dazu in Runde Knoten mit Knoten kommunizieren.
Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen Hyperwürfel eine Laufzeit in erreicht werden.
![There are three rectangles vertically aligned on the left and three rectangles vertically aligned on the right. The rectangles are three time higher as wide. The terms a1, a2 and a3 are written in the high left rectangle one below the other. The terms b1, b2 and b3 are written in the mid left rectangle one below the other. The terms c1, c2 and c3 are written in the low left rectangle one below the other. The terms a1, b1 and c1 are written in the high right rectangle one below the other. The terms a2, b2 and c2 are written in the mid right rectangle one below the other. The terms a3, b3 and c3 are written in the low right rectangle one below the other. A dotted line connects a1 from the high left rectangle and a1 from the high right rectangle. A dotted line connects b2 from the mid left rectangle and b2 from the mid right rectangle. A dotted line connects c3 from the low left rectangle and c3 from the low right rectangle. Solid lines connect the other corresponding terms between the left and right rectangles.](http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/All-to-All.png/220px-All-to-All.png)
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der Netzwerktopologie frei ist.
Beispieltopologien für eine optimale Laufzeit sind je nach Algorithmus Binärbaum, Binomialbaum und Hyperwürfel.
In der Praxis müssen die Algorithmen an die tatsächlich verfügbaren Topologien angepasst werden, beispielsweise Fat tree, Gitter, Dragonfly.
Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße abhängen. Beispielsweise ist Broadcast für kurze Nachrichten optimal auf einem Binomialbaum während für lange Nachrichten Kommunikation die Pipelining verwendet auf einem Binärbaum optimal ist.
In der Tabelle steht in der Spalte Name der Name des jeweiligen Musters. Die Spalte # Sender listet die Anzahl Prozessoreinheiten, die initial eine zu verteilende Nachricht haben. # Empfänger listet die Anzahl Knoten die eine Nachricht zu empfangen haben. # Nachrichten zeigt die Anzahl Nachrichten, die insgesamt auszuliefern sind. Berechnung listet, ob zusätzlich zur Kommunikation noch eine Berechnung stattfindet. Laufzeitkomplexität listet die asymptotische Laufzeit einer optimalen Implementierung unter freier Wahl der Topologie.
Name | # Sender | # Empfänger | # Nachrichten | Berechnung | Laufzeitkomplexität |
---|---|---|---|---|---|
Broadcast | nein | ||||
Reduktion | ja | ||||
All-reduce | ja | ||||
Präfixsumme/ Scan | ja | ||||
Barriere | nein | ||||
Gather | nein | ||||
All-gather | nein | ||||
Scatter | nein | ||||
All-to-all | nein | oder |
TODO:
[edit]Add ref from Parallel algorithm#Communication
Distributed algorithm (ref to or from?)
Deutscher Wiki-Artikel zu MPI enthält manche Algorithmen
Sharded memory vs distributed memory ? Wir reden über distributed memory.
References
[edit]Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer Nature Switzerland AG. ISBN 978-3-030-25208-3.
- ^ Intercommunicator Collective Operations. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, Argonne National Laboratory.
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408
- ^ a b Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418
- ^ Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394