User:Kortasch/Collective operation German

Kollektive Operationen sind Grundbausteine für Interaktionsmuster die häufige Anwendung in SPMD Algorithmenund parelleler Programmierungparalleler Programmierung finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das Message_Passing_Interface (MPI) stellt eine Implementierung der kollektiven Operationen bereit. DSC

Definitionen

In der asymptotischen Laufzeitanalyse sei die Latenz $\alpha$, die Bandbreite $\beta$, die Anzahl der Prozessoreinheiten $p$ und die Größe der Eingabe pro Knoten $n$. 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 $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$.

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 $p_{i}$ eine Nachricht der Größe $n_{i}$. Dann setze man $n=\max(n_{0},n_{1},\dots ,n_{p-1})$

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 . Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

Broadcast

Main article: Broadcast

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

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

Broadcast mit Pipelining auf einem balancierten Binärbaum ist in Laufzeit ${\mathcal {O}}(\alpha \log p+\beta n)$ möglich.

Reduktion

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 $\otimes$ ein assoziativer Operator, $p_{0}$ die Prozessoreinheit auf der das Ergebnis gespeichert werden soll. Dann berechnet die Reduktion das Ergebnis $m_{0}\otimes m_{1}\otimes \ldots \otimes m_{p}$ und speichert es auf Prozessoreinheit $p_{0}$. Manche Algorithmen fordern, dass $\otimes$ zusätzlich kommutativ ist. Häufige Operatoren sind $sum,min,max$.

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

All-reduce

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 $p_{i}$ die Nachricht $m_{i}$. Das Ergebnis $m_{1}\otimes m_{2}\otimes \ldots \otimes m_{p}$ liegt nach dem All-reduce auf allen $p_{i}$ vor. Konzeptionell entspricht All-reduce einer Reduktion mit anschließendem Broadcast. Auch bei All-reduce muss $\otimes$ assoziativ sein.

Für lange Nachrichten spielen die gleichen Randbedingungen eine Rolle. Für kurze Nachrichten kann die Latenz durch Nutzung einer Hyperwürfel-Topologie verbessert werden, sofern $p$ eine Zweierpotenz ist.

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

Präfixsumme/Scan

Main article: Präfixsumme

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 $\otimes$ 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 $\otimes$ mindestens Assoziativität gefordert, wobei manche Algorithmen zusätzlich Kommutativität erfordern. Häufige Operationen sind $SUM,min,max$.

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

Barriere

Die Barriere ist eine Verallgemeinerung des Konzepts der Barriere auf verteiltes Rechnen. Wenn eine Prozessoreinheit die Barriere aufruft, dann wartet sie, bis alle anderen Prozessoreinheiten ebenfalls Barriere aufgerufen haben, before sie im Programm fortfährt. Die Barriere ist also eine Möglichkeit der globalen Synchronisation.

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

Gather

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 $m_{i}$ auf Prozessoreinheit $p_{i}$, so soll nach dem Gather auf der Wurzel $r=p_{i}$ die Nachricht $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ gespeichert werden. Konzeptionell entspricht Gather der Reduktion (§ Reduktion) wobei der Operator die Konkatenation der Nachrichten ist. Konkatenation ist assoziativ und erfüllt damit die Voraussetzung der Reduktion.

Durch die Nutzung des Binomialbaum-Algorithmus der Reduktion wird eine Laufzeit von ${\mathcal {O}}(\alpha \log p+\beta pn)$ erreicht. Die Laufzeit ist ähnlich zur Laufzeit ${\mathcal {O}}(\alpha \log p+\beta n)$ see Reduktion, bis auf einen zusätzlichen Faktor $p$ der an den Term $\beta n$ 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 $min$, die eine konstante Nachrichtengröße über alle Schritte bedingen.

All-gather

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 $m_{i}$ auf Prozessoreinheit $p_{i}$, soll die Nachricht $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ 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 $pn$. Wir sehen, dass All-gather in Laufzeit ${\mathcal {O}}(\alpha \log p+\beta pn)$ durchgeführt werden kann.

Scatter

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 $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ so verteilt werden, dass anschließend auf Prozessoreinheit $p_{i}$ die Nachricht $m_{i}$ 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 ${\mathcal {O}}(\alpha \log p+\beta pn)$.

All-to-all

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

Sofern das Netzwerk als vollständiger Graph gesehen werden kann, ist eine Laufzeit in ${\mathcal {O}}(p(\alpha +\beta n))$ möglich. Dabei wird All-to-all durch $p-1$ Runden paarweisen Nachrichtenaustauschs implementiert. Falls $p$ eine Zweierpotenz ist, kann dazu in Runde $k$ Knoten $p_{i}$ mit Knoten $p_{j},j=i\oplus k$ kommunizieren.

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

Information flow of All-to-All operation performed on three nodes. Letters indicate nodes and numbers indicate information items.

Laufzeitüberblick

Diese Tabelle gibt einen Überblick über die bestmöglichen asymptotischen Laufzeiten, sofern die Wahl der Netzwerktopologie frei ist.

Beispieltopologien für eine optimale Laufzeit sind je nach Algorithmus Binärbaum, Binomialbaum und Hyperwürfel.

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

Bei einigen Operationen kann die Wahl des optimalen Algorithmus von der Eingabegröße $n$ abhängen. Beispielsweise ist Broadcast für kurze Nachrichten optimal auf einem Binomialbaum während für lange Nachrichten Kommunikation die Pipelining verwendet auf einem Binärbaum optimal ist.

In der Tabelle steht in der Spalte Name der Name des jeweiligen Musters. Die Spalte # Sender listet die Anzahl Prozessoreinheiten, die initial eine zu verteilende Nachricht haben. # Empfänger listet die Anzahl Knoten die eine Nachricht zu empfangen haben. # Nachrichten zeigt die Anzahl Nachrichten, die insgesamt auszuliefern sind. Berechnung listet, ob zusätzlich zur Kommunikation noch eine Berechnung stattfindet. Laufzeitkomplexität listet die asymptotische Laufzeit einer optimalen Implementierung unter freier Wahl der Topologie.

Name	# Sender	# Empfänger	# Nachrichten	Berechnung	Laufzeitkomplexität
Broadcast	$1$	$p$	$1$	nein	${\mathcal {O}}(\alpha \log p+\beta n)$
Reduktion	$p$	$1$	$p$	ja	${\mathcal {O}}(\alpha \log p+\beta n)$
All-reduce	$p$	$p$	$p$	ja	${\mathcal {O}}(\alpha \log p+\beta n)$
Präfixsumme/ Scan	$p$	$p$	$p$	ja	${\mathcal {O}}(\alpha \log p+\beta n)$
Barriere	$p$	$p$	$0$	nein	${\mathcal {O}}(\alpha \log p)$
Gather	$p$	$1$	$p$	nein	${\mathcal {O}}(\alpha \log p+\beta pn)$
All-gather	$p$	$p$	$p$	nein	${\mathcal {O}}(\alpha \log p+\beta pn)$
Scatter	$1$	$p$	$p$	nein	${\mathcal {O}}(\alpha \log p+\beta pn)$
All-to-all	$p$	$p$	$p^{2}$	nein	${\mathcal {O}}(\log p(\alpha +\beta pn))$ oder ${\mathcal {O}}(p(\alpha +\beta n))$

TODO:

Add ref from Parallel algorithm#Communication

Distributed algorithm (ref to or from?)

Deutscher Wiki-Artikel zu MPI enthält manche Algorithmen

Sharded memory vs distributed memory ? Wir reden über distributed memory.

References

Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures - The Basic Toolbox. Springer Nature Switzerland AG. ISBN 978-3-030-25208-3.