Wikipedia - Benutzerbeiträge [de]

Kollektive Operationen

2020-03-03T21:14:09Z

RenderFlamingo: RenderFlamingo verschob die Seite Benutzer:RenderFlamingo/Kollektive Kommunikation nach Kollektive Operationen: Artikel fertig.

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>.

Es wird das Modell eines verteilten Speichers angenommen. Die vorgestellten Konzepte sind im Modell eines geteilten Speichers ähnlich. Bei geteiltem Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|upright=1.2|alt=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.|thumb|Informationsfluss von Broadcast ausgeführt auf drei Einheiten.]]

Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in [[Single-Program Multiple-Data|SPMD]] parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion ([[#Reduktion]]) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung, die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz, der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt, verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.

{{Absatz}}
== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|upright=1.2|alt=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.|thumb|Informationsfluss von Reduktion ausgeführt auf drei Einheite. f sei ein assoziativer Operator und α sei das Resultat der Reduktion.]]

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 <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 möglich ist.

Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{Absatz}}
== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|upright=1.2|alt=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.|thumb|Informationsfluss von All-Reduce ausgeführt auf drei Einheiten. f sei ein assoziativer Operator und α sei das Resultat der Reduktion.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion ([[#Reduktion]]) allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast ([[#Broadcast]]). Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.

{{Absatz}}
== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|upright=1.8|alt=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.|thumb|Informationsfluss von Prefix-Sum/Scan ausgeführt auf drei Einheiten. Der Operator + kann ein beliebiger assoziativer Operator sein.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> Zwischenergebnisse zu berechnen. Die Zwischenergebnisse werden auf den einzelnen Prozessoreinheiten gespeichert. Die Präfixsumme kann als Generalisierung des Musters Reduktion ([[#Reduktion]]) aufgefasst werden. Wie in Reduktion und All-reduce ([[#All-reduce]]) wird vom Operator <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>sum, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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%C3%BCrfel_(Kommunikationsmuster)|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%C3%A4rbaum|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 ([[#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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{Absatz}}
== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltem 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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ([[#All-reduce]]) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

{{Absatz}}
== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|upright=1.8|alt=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.|thumb|Informationsfluss von Gather ausgeführt auf drei Einheiten.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ([[#Reduktion]]) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> der Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

{{Absatz}}
== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|upright=1.8|alt=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.|thumb|Informationsfluss von All-Gather ausgeführt auf drei Einheiten.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

{{Absatz}}
== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|upright=1.8|alt=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.|thumb|Informationsfluss von Scatter ausgeführt auf drei Einheiten.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> vorliegt. Scatter kann als invertierter Gather ([[#Gather]]) gesehen werden.

Für Scatter lassen sich die gleichen Überlegungen wie für Gather anstellen. Das Resultat ist eine Laufzeit in <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

{{Absatz}}
== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math>, kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]] eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|upright=1.4|alt=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.|thumb|Informationsfluss von All-to-All ausgeführt auf drei Einheiten. Buchstaben indizieren Einheiten und Nummern indizieren Informationselemente.]]

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|Netzwerktopologie]] frei ist.

Beispieltopologien für eine optimale Laufzeit sind je nach Algorithmus [[Bin%C3%A4rbaum|Binärbaum]], [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] und [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]].

In der Praxis müssen die Algorithmen an die tatsächlich verfügbaren Topologien angepasst werden, beispielsweise [[Fat_Tree|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

{{Absatz}}
== Anmerkungen ==
<references />

== Einzelnachweise ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}
[[Kategorie:Parallelverarbeitung]]
[[Kategorie:Algorithmus]]
[[Kategorie:Verteiltes Rechnen]]

Kollektive Operationen

2020-03-03T21:11:16Z

RenderFlamingo:

Kollektive Operationen

2020-03-03T20:47:36Z

RenderFlamingo:

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>.

Es wird das Modell eines verteilten Speichers angenommen. Die vorgestellten Konzepte sind im Modell eines geteilten Speichers ähnlich. Bei geteiltem Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|upright=1.2|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in [[Single-Program Multiple-Data|SPMD]] parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion ([[#Reduktion]]) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung, die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz, der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt, verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.

{{Absatz}}
== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|upright=1.2|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 möglich ist.

Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{Absatz}}
== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|upright=1.2|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion ([[#Reduktion]]) allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast ([[#Broadcast]]). Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.

{{Absatz}}
== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|upright=1.8|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> Zwischenergebnisse zu berechnen. Die Zwischenergebnisse werden auf den einzelnen Prozessoreinheiten gespeichert. Die Präfixsumme kann als Generalisierung des Musters Reduktion ([[#Reduktion]]) aufgefasst werden. Wie in Reduktion und All-reduce ([[#All-reduce]]) wird vom Operator <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>sum, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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%C3%BCrfel_(Kommunikationsmuster)|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%C3%A4rbaum|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 ([[#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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{Absatz}}
== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltem 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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ([[#All-reduce]]) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

{{Absatz}}
== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|upright=1.8|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ([[#Reduktion]]) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> der Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

{{Absatz}}
== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|upright=1.8|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

{{Absatz}}
== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|upright=1.8|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> vorliegt. Scatter kann als invertierter Gather ([[#Gather]]) gesehen werden.

Für Scatter lassen sich die gleichen Überlegungen wie für Gather anstellen. Das Resultat ist eine Laufzeit in <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

{{Absatz}}
== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math>, kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]] eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|upright=1.4|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|Netzwerktopologie]] frei ist.

Beispieltopologien für eine optimale Laufzeit sind je nach Algorithmus [[Bin%C3%A4rbaum|Binärbaum]], [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] und [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]].

In der Praxis müssen die Algorithmen an die tatsächlich verfügbaren Topologien angepasst werden, beispielsweise [[Fat_Tree|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

{{Absatz}}
== Anmerkungen ==
<references />

== Einzelnachweise ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}
[[Kategorie:Parallelverarbeitung]]
[[Kategorie:Algorithmus]]
[[Kategorie:Verteiltes Rechnen]]

Kollektive Operationen

2020-03-03T20:46:45Z

RenderFlamingo:

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>.

Es wird das Modell eines verteilten Speichers angenommen. Die vorgestellten Konzepte sind im Modell eines geteilten Speichers ähnlich. Bei geteiltem Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|upright=1.2|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in [[Single-Program Multiple-Data|SPMD]] parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion ([[#Reduktion]]) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung, die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz, der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt, verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.

{{Absatz}}
== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|upright=1.2|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 möglich ist.

Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{Absatz}}
== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|upright=1.2|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion ([[#Reduktion]]) allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast ([[#Broadcast]]). Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.

{{Absatz}}
== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|upright=1.8|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> Zwischenergebnisse zu berechnen. Die Zwischenergebnisse werden auf den einzelnen Prozessoreinheiten gespeichert. Die Präfixsumme kann als Generalisierung des Musters Reduktion ([[#Reduktion]]) aufgefasst werden. Wie in Reduktion und All-reduce ([[#All-reduce]]) wird vom Operator <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>sum, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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%C3%BCrfel_(Kommunikationsmuster)|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%C3%A4rbaum|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 ([[#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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{Absatz}}
== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltem 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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ([[#All-reduce]]) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

{{Absatz}}
== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|upright=1.8|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ([[#Reduktion]]) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> der Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

{{Absatz}}
== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|upright=1.8|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

{{Absatz}}
== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|upright=1.8|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> vorliegt. Scatter kann als invertierter Gather ([[#Gather]]) gesehen werden.

Für Scatter lassen sich die gleichen Überlegungen wie für Gather anstellen. Das Resultat ist eine Laufzeit in <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

{{Absatz}}
== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math>, kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]] eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|upright=1.4|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|Netzwerktopologie]] frei ist.

Beispieltopologien für eine optimale Laufzeit sind je nach Algorithmus [[Bin%C3%A4rbaum|Binärbaum]], [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] und [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]].

In der Praxis müssen die Algorithmen an die tatsächlich verfügbaren Topologien angepasst werden, beispielsweise [[Fat_Tree|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

== Anmerkungen ==
<references />

== Einzelnachweise ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}
[[Kategorie:Parallelverarbeitung]]
[[Kategorie:Algorithmus]]
[[Kategorie:Verteiltes Rechnen]]

Kollektive Operationen

2020-03-03T20:44:39Z

RenderFlamingo:

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>.

Es wird das Modell eines verteilten Speichers angenommen. Die vorgestellten Konzepte sind im Modell eines geteilten Speichers ähnlich. Bei geteiltem Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|upright=1.2|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in [[Single-Program Multiple-Data|SPMD]] parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion ([[#Reduktion]]) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung, die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz, der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt, verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.

{{Absatz}}
== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|upright=1.2|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 möglich ist.

Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{Absatz}}
== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|upright=1.2|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion ([[#Reduktion]]) allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast ([[#Broadcast]]). Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.

{{Absatz}}
== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|upright=1.8|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> Zwischenergebnisse zu berechnen. Die Zwischenergebnisse werden auf den einzelnen Prozessoreinheiten gespeichert. Die Präfixsumme kann als Generalisierung des Musters Reduktion ([[#Reduktion]]) aufgefasst werden. Wie in Reduktion und All-reduce ([[#All-reduce]]) wird vom Operator <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>sum, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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%C3%BCrfel_(Kommunikationsmuster)|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%C3%A4rbaum|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 ([[#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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{Absatz}}
== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltem 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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ([[#All-reduce]]) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

{{Absatz}}
== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|upright=1.8|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ([[#Reduktion]]) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> der Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

{{Absatz}}
== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|upright=1.8|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

{{Absatz}}
== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|upright=1.8|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> vorliegt. Scatter kann als invertierter Gather ([[#Gather]]) gesehen werden.

Für Scatter lassen sich die gleichen Überlegungen wie für Gather anstellen. Das Resultat ist eine Laufzeit in <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

{{Absatz}}
== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math>, kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]] eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|upright=1.4|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|Netzwerktopologie]] frei ist.

Beispieltopologien für eine optimale Laufzeit sind je nach Algorithmus [[Bin%C3%A4rbaum|Binärbaum]], [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] und [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]].

In der Praxis müssen die Algorithmen an die tatsächlich verfügbaren Topologien angepasst werden, beispielsweise [[Fat_Tree|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

== Anmerkungen ==
<references />

== Einzelnachweise ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}

Kollektive Operationen

2020-03-03T20:19:51Z

RenderFlamingo:

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>.

Es wird das Modell eines verteilten Speichers angenommen. Die vorgestellten Konzepte sind im Modell eines geteilten Speichers ähnlich. Bei geteiltem Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in [[Single-Program Multiple-Data|SPMD]] parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion ([[#Reduktion]]) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung, die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz, der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt, verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.

== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 möglich ist.

Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion ([[#Reduktion]]) allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast ([[#Broadcast]]). Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.

== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> Zwischenergebnisse zu berechnen. Die Zwischenergebnisse werden auf den einzelnen Prozessoreinheiten gespeichert. Die Präfixsumme kann als Generalisierung des Musters Reduktion ([[#Reduktion]]) aufgefasst werden. Wie in Reduktion und All-reduce ([[#All-reduce]]) wird vom Operator <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>sum, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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%C3%BCrfel_(Kommunikationsmuster)|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%C3%A4rbaum|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 ([[#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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltem 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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ([[#All-reduce]]) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ([[#Reduktion]]) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> der Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> vorliegt. Scatter kann als invertierter Gather ([[#Gather]]) gesehen werden.

Für Scatter lassen sich die gleichen Überlegungen wie für Gather anstellen. Das Resultat ist eine Laufzeit in <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math>, kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]] eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|Netzwerktopologie]] frei ist.

Beispieltopologien für eine optimale Laufzeit sind je nach Algorithmus [[Bin%C3%A4rbaum|Binärbaum]], [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] und [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]].

In der Praxis müssen die Algorithmen an die tatsächlich verfügbaren Topologien angepasst werden, beispielsweise [[Fat_Tree|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

== Anmerkungen ==
<references />

== Einzelnachweise ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}

Kollektive Operationen

2020-03-03T20:14:00Z

RenderFlamingo:

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>.

Es wird das Modell eines verteilten Speichers angenommen. Die vorgestellten Konzepte sind im Modell eines geteilten Speichers ähnlich. Bei geteiltem Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in [[Single-Program Multiple-Data|SPMD]] parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion ([[#Reduktion]]) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung, die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz, der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt, verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.

== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 möglich ist.

Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion ([[#Reduktion]]) allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast ([[#Broadcast]]). Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.

== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> Zwischenergebnisse zu berechnen. Die Zwischenergebnisse werden auf den einzelnen Prozessoreinheiten gespeichert. Die Präfixsumme kann als Generalisierung des Musters Reduktion ([[#Reduktion]]) aufgefasst werden. Wie in Reduktion und All-reduce ([[#All-reduce]]) wird vom Operator <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>sum, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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%C3%BCrfel_(Kommunikationsmuster)|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%C3%A4rbaum|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 ([[#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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltem 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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ([[#All-reduce]]) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ([[#Reduktion]]) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> der Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> vorliegt. Scatter kann als invertierter Gather ([[#Gather]]) gesehen werden.

Für Scatter lassen sich die gleichen Überlegungen wie für Gather anstellen. Das Resultat ist eine Laufzeit in <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math>, kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]] eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|Netzwerktopologie]] frei ist.

Beispieltopologien für eine optimale Laufzeit sind je nach Algorithmus [[Bin%C3%A4rbaum|Binärbaum]], [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] und [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]].

In der Praxis müssen die Algorithmen an die tatsächlich verfügbaren Topologien angepasst werden, beispielsweise [[Fat_Tree|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

== References ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}

Kollektive Operationen

2020-03-03T19:49:35Z

RenderFlamingo:

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>.

Es wird das Modell eines verteilten Speichers angenommen. Die vorgestellten Konzepte sind im Modell eines geteilten Speichers ähnlich. Bei geteiltem Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in [[Single-Program Multiple-Data|SPMD]] parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion ([[#Reduktion]]) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung, die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz, der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt, verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.

== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 möglich ist.

Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion ([[#Reduktion]]) allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast ([[#Broadcast]]). Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.

== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> Zwischenergebnisse zu berechnen. Die Zwischenergebnisse werden auf den einzelnen Prozessoreinheiten gespeichert. Die Präfixsumme kann als Generalisierung des Musters Reduktion ([[#Reduktion]]) aufgefasst werden. Wie in Reduktion und All-reduce ([[#All-reduce]]) wird vom Operator <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>sum, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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%C3%BCrfel_(Kommunikationsmuster)|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%C3%A4rbaum|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 ([[#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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltem 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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ([[#All-reduce]]) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ({{section link||Reduktion}}) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> see Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

{{clear}}

== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

{{clear}}

== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> 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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

{{clear}}

== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt emuliert werden, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math> kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen Hyperwürfel eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

{{clear}}

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|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|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

== References ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}

Kollektive Operationen

2020-03-03T19:33:46Z

RenderFlamingo:

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>.

Es wird das Modell eines verteilten Speichers angenommen. Die vorgestellten Konzepte sind im Modell eines geteilten Speichers ähnlich. Bei geteiltem Speicher besteht jedoch die Möglichkeit, dass die Hardware Operationen wie Broadcast unmittelbar unterstützt <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

Das Broadcast-Muster wird genutzt, um Daten einer Prozessoreinheit an alle anderen Prozessoreinheiten zu verteilen. Ein Anwendungsfall des Broadcast ist, in [[Single-Program Multiple-Data|SPMD]] parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse Reduktion () aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung, die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz, der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt, verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.

== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 ({{section link||Broadcast}}) aufgefasst werden. Sei <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 möglich ist.

Reduktion mit Pipelining auf einem balancierten Binärbaum ist in Zeit <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast. Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.
{{clear}}

== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> 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 <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>SUM, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{clear}}

== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ({{section link||All-reduce}}) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ({{section link||Reduktion}}) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> see Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

{{clear}}

== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

{{clear}}

== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> 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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

{{clear}}

== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt emuliert werden, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math> kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen Hyperwürfel eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

{{clear}}

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|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|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

== References ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}

Kollektive Operationen

2020-03-02T23:59:17Z

RenderFlamingo:

'''Kollektive Operationen''' sind Grundbausteine für Interaktionsmuster, die häufig Anwendung in [[Single-Program_Multiple-Data|SPMD]] Algorithmen und [[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message Passing Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die Kommunikationszeit pro Wort <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>

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 <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

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 ({{section link||Reduktion}}) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.
{{clear}}

== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 ({{section link||Broadcast}}) aufgefasst werden. Sei <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{clear}}

== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast. Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.
{{clear}}

== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> 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 <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>SUM, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{clear}}

== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ({{section link||All-reduce}}) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ({{section link||Reduktion}}) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> see Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

{{clear}}

== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

{{clear}}

== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> 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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

{{clear}}

== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt emuliert werden, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math> kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen Hyperwürfel eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

{{clear}}

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|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|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

== References ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}

Kollektive Operationen

2020-03-02T23:46:24Z

RenderFlamingo: AZ: Die Seite wurde neu angelegt: Kollektive Operationen sind Grundbausteine für Interaktionsmuster die häufige Anwendung in Single-…

Kollektive Operationen sind Grundbausteine für Interaktionsmuster die häufige Anwendung in [[Single-Program_Multiple-Data|SPMD]] [[Algorithmus|Algorithmen]]und parelleler Programmierung[[Parallele_Programmierung|paralleler Programmierung]] finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das [[Message_Passing_Interface]]<ref>[http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/node144.htm Intercommunicator Collective Operations]. The Message Passing Interface (MPI) standard, chapter 7.3.1. Mathematics and Computer Science Division, [[Argonne National Laboratory]].</ref> (MPI) stellt eine [[Implementierung]] der kollektiven Operationen bereit. DSC

== Definitionen ==
In der [[Landau-Symbole|asymptotischen Laufzeitanalyse]] sei die [[Verz%C3%B6gerung_(Telekommunikation)|Latenz]] <math>\alpha</math>, die [[Bandbreite]] <math>\beta</math>, die Anzahl der Prozessoreinheiten <math>p</math> und die Größe der Eingabe pro Knoten <math>n</math>. 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 <math>p_i \in \{ p_0, p_1, \dots, p_{p - 1} \}</math>.

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 <math>p_i</math> eine Nachricht der Größe <math>n_i</math>. Dann setze man <math>n = \max(n_0, n_1, \dots, n_{p-1})</math>

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 <ref name=":1">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 395</ref>. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

== Broadcast <ref name=":2">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 396-401</ref>==
{{Main|Broadcast}}

[[File:Broadcast_(collective_operation).png|alt=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.|thumb|Information flow of Broadcast operation performed on three nodes.]]

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 ({{section link||Reduktion}}) aufgefasst werden. Zu Beginn enthält die Wurzel <math>r = p_i</math> für ein festes <math>i</math> die Nachricht <math>m</math>. Hier nehmen wir <math>i = 0</math> an, um die Erklärung simpler zu gestalten. Während des Broadcast wird <math>m</math> an die restlichen Prozessoreinheiten gesendet, sodass <math>m</math> schlussendlich auf allen Prozessoreinheiten verfügbar ist.

Da die triviale Implementierung die in <math>p-1</math> Iterationen jeweils <math>m</math> direkt von <math>r</math> an <math>p_j</math> übermittelt, nicht ausreichend performant ist, wird ein Ansatz der das Prinzip '[[Teile-und-herrsche-Verfahren|Teile-und-herrsche-Verfahren]]' nutzt verwendet. Sofern <math>p</math> eine Zweierpotenz ist, kann ein [[Binomial-Heap#Binomial-B%C3%A4ume|Binomialbaum]] als unterliegende Struktur verwendet werden. Angenommen Prozessoreinheit <math>p_k</math> ist verantwortlich, die Nachricht an Prozessoreinheiten <math>p_l, ..., p_n</math> weiterzuleiten. Dann sendet <math>p_k</math> die Nachricht <math>m</math> an <math>p_o</math> mit <math>o = \left \lceil (i+j)/2 \right \rceil</math>. Die Verantwortung für die Übermittlung von <math>m</math> an Prozessoreinheiten mit Indizes <math>\left \lceil (i+j)/2 \right \rceil .. \left \lceil (i+j)-1 \right \rceil</math> wird an <math>p_o</math> übertragen, <math>p_k</math> ist im Folgenden nur noch für die Übermittlung von <math>m</math> an die Prozessoreinheiten mit Indizes <math>i..\left \lceil (i+j)/2 \right \rceil-1</math> zuständig. Die Performance des Binomialbaum-Broadcast ist für lange Nachrichten nicht gut, da eine Prozessoreinheit, die <math>m</math> empfängt, erst dann die Nachricht weiterleiten kann, wenn <math>m</math> vollständig empfangen wurde. Als Ausgleich wird Pipelining verwendet. Dabei wird <math>m</math> in ein [[Feld_(Datentyp)|Array]] aus <math>k</math> [[Datenpaket|Paketen]] der Größe <math>\left \lceil n/k \right \rceil </math> zerlegt. Die Pakete werden dann nacheinander per Broadcast verteilt, was bessere Auslastung des Kommunikationsnetzes erlaubt.

Broadcast mit Pipelining auf einem balancierten [[Bin%C3%A4rbaum|Binärbaum]] ist in Laufzeit <math> \mathcal{O}(\alpha \log p + \beta n)</math> möglich.
{{clear}}

== Reduktion <ref name=":3">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 402-403</ref>==

[[File:Reduce.png|alt=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.|thumb|Information flow of Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

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 ({{section link||Broadcast}}) aufgefasst werden. Sei <math>\otimes</math> ein [[Assoziativgesetz|assoziativer]] [[Operator_(Mathematik)|Operator]], <math>p_0</math> die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis <math>m_0 \otimes m_1 \otimes \ldots \otimes m_p</math> und speichert es auf Prozessoreinheit <math>p_0</math>. Manche Algorithmen fordern, dass <math>\otimes</math> zusätzlich [[Kommutativgesetz|kommutativ]] ist. Häufige Operatoren sind <math>sum, min, max</math>.

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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{clear}}

== All-reduce <ref name=":4">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 403-404</ref>==

[[File:All-Reduce.png|alt=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.|thumb|Information flow of All-Reduce operation performed on three nodes. f is the associative operator and α is the result of the reduction.]]

Das Muster All-reduce wird genutzt, wenn das Ergebnis einer Reduktion allen Prozessoreinheiten zur Verfügung gestellt werden soll. Zu Beginn liegt auf Prozessoreinheit <math> p_i </math> die Nachricht <math>m_i</math>. Das Ergebnis <math> m_1 \otimes m_2 \otimes \ldots \otimes m_p</math> liegt nach dem All-reduce auf allen <math> p_i </math> vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast. Auch bei All-reduce muss <math>\otimes</math> assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer [[Hyperw%C3%BCrfel_(Kommunikationsmuster)|Hyperwürfel]]-Topologie verbessert werden, sofern <math>p</math> eine Zweierpotenz ist.

Wir sehen, dass All-reduce in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich ist, da Reduktion und Broadcast jeweils in <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich sind.
{{clear}}

== Präfixsumme/Scan <ref name=":5">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 404-406</ref>==
{{Main|Pr%C3%A4fixsumme}}

[[File:Prefix-Sum_(Scan).png|alt=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.|thumb|Information flow of Prefix-Sum/Scan operation performed on three nodes. The operator + can be any associative operator.]]

Das Muster Präfixsumme oder Scan wird genutzt, um Daten oder partielle Resultate mehrerer Prozessoreinheiten zusammenzutragen und mittels eines Operators <math> \otimes </math> 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 <math>\otimes</math> mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind <math>SUM, min, max</math>.

Nach Abschluss der Präfixsumme enthält Prozessoreinheit <math>p_i</math> die Nachricht <math>\otimes_{i' <= i}</math><math>m_{i'}</math>. Im Sonderfall der exklusiven Präfixsumme wird stattdessen <math>\otimes_{i' < i}</math><math>m_{i'}</math> 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 <math> \mathcal{O}(\alpha \log p + \beta n) </math> möglich.

{{clear}}

== Barriere <ref name=":6">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 408</ref>==

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 [[Prozesssynchronisation|Synchronisation]].

Eine Möglichkeit, die Barriere zu implementieren ist es, All-reduce ({{section link||All-reduce}}) mit einem leeren Operanden aufzurufen. Dadurch wird die Nachrichtengröße <math>n</math> auf einen konstanten Faktor reduziert und nur der Latenz-Term in der Laufzeitbetrachtung bleibt übrig. Da die Laufzeit für All-reduce <math>\mathcal{O}(\alpha \log p + \beta n)</math> ist, liegt die Laufzeit der Barriere also in <math>\mathcal{O}(\alpha \log p)</math>.

== Gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:Gather.png|alt=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.|thumb|Information flow of Gather operation performed on three nodes.]]

Das Muster Gather wird genutzt, um Daten von allen Prozessoreinheiten zu sammeln und auf einer einzelnen Prozessoreinheit zusammenzuführen. Liegt zu Beginn die Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, so soll nach dem Gather auf der Wurzel <math>r = p_i</math> die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> gespeichert werden. Konzeptionell entspricht Gather der Reduktion ({{section link||Reduktion}}) wobei der Operator die [[Konkatenation_(Listen)|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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math> erreicht.
Die Laufzeit ist ähnlich zur Laufzeit <math>\mathcal{O}(\alpha \log p + \beta n)</math> see Reduktion, bis auf einen zusätzlichen Faktor <math> p </math> der an den Term <math> \beta n </math> 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 <math> min </math>, die eine konstante Nachrichtengröße über alle Schritte bedingen.

{{clear}}

== All-gather <ref name=":7">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 412-413</ref>==

[[File:All-Gather.png|alt=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.|thumb|Information flow of All-Gather operation performed on three nodes.]]

Das Muster All-gather wird genutzt, um Daten aller Prozessoreinheiten auf allen Prozessoreinheiten zu sammeln. Gegeben Nachricht <math> m_i </math> auf Prozessoreinheit <math> p_i </math>, soll die Nachricht <math>m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> 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 <math>pn</math>. Wir sehen, dass All-gather in Laufzeit <math>\mathcal{O}(\alpha \log p + \beta p n)</math> durchgeführt werden kann.

{{clear}}

== Scatter <ref name=":8">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 413</ref>==

[[File:Scatter.png|alt=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.|thumb|Information flow of Scatter operation performed on three nodes.]]

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 <math>m = m_1 \cdot m_2 \cdot \ldots \cdot m_p</math> so verteilt werden, dass anschließend auf Prozessoreinheit <math>p_i</math> die Nachricht <math>m_i</math> 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 <math>\mathcal{O}(\alpha \log p + \beta p n)</math>.

{{clear}}

== All-to-all <ref name=":9">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, pp. 413-418</ref>==

Das Muster All-to-all stellt das allgemeinste Kommunikationsmuster dar. Für <math>0 \leq i < p, 0 \leq j < p</math> ist <math>m_{i, j}</math> die Nachricht, die zu Beginn auf Prozessoreinheit <math>i</math> vorliegt und nach der Operation auf Prozessoreinheit <math>j</math> 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 <math>r = p_i</math> die Nachricht <math>m</math> verteilt emuliert werden, indem <math>m_{i, j} = m</math> gesetzt wird und <math>m_{k, j}</math> leere Nachricht für <math>k \neq i</math>.

Sofern das Netzwerk als [[Vollst%C3%A4ndiger_Graph|vollständiger Graph]] gesehen werden kann, ist eine Laufzeit in <math>\mathcal{O}(p (\alpha + \beta n))</math> möglich. Dabei wird All-to-all durch <math> p - 1 </math> Runden paarweisen Nachrichtenaustauschs implementiert. Falls <math> p </math> eine Zweierpotenz ist, kann dazu in Runde <math> k </math> Knoten <math> p_i </math> mit Knoten <math> p_j, j= i \oplus k</math> kommunizieren.

Falls die Nachrichtengröße klein ist und die Latenz die Laufzeit dominiert, kann durch einen Hyperwürfel eine Laufzeit in <math>\mathcal{O}(\log p (\alpha + \beta p n))</math> erreicht werden.

[[File:All-to-All.png|alt=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.|thumb|Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.]]

{{clear}}

== Laufzeitüberblick <ref name=":10">Sanders, Mehlhorn, Dietzfelbinger, Dementiev 2019, p. 394</ref>==
Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der [[Topologie_(Rechnernetz)|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|Fat tree]], Gitter, Dragonfly.

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße <math>n</math> 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.
{| class="wikitable"
|+
!Name
!# Sender
!# Empfänger
!# Nachrichten
!Berechnung
!Laufzeitkomplexität
|-
|Broadcast
|<math>1</math>
|<math>p</math>
|<math>1</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Reduktion
|<math>p</math>
|<math>1</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|All-reduce
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Präfixsumme/ Scan
|<math>p</math>
|<math>p</math>
|<math>p</math>
|ja
|<math>\mathcal{O}(\alpha \log p + \beta n)</math>
|-
|Barriere
|<math>p</math>
|<math>p</math>
|<math>0</math>
|nein
|<math>\mathcal{O}(\alpha \log p)</math>
|-
|Gather
|<math>p</math>
|<math>1</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-gather
|<math>p</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|Scatter
|<math>1</math>
|<math>p</math>
|<math>p</math>
|nein
|<math>\mathcal{O}(\alpha \log p + \beta p n)</math>
|-
|All-to-all
|<math>p</math>
|<math>p</math>
|<math>p^2</math>
|nein
|<math>\mathcal{O}(\log p (\alpha + \beta p n))</math> oder <math>\mathcal{O}(p (\alpha + \beta n))</math>
|}

== References ==
{{cite book|last1=Sanders|first1=Peter|title=Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer Nature Switzerland AG|isbn=978-3-030-25208-3|authorlink1=Peter Sanders (computer scientist)|authorlink2=Kurt Mehlhorn}}