Kollektive Operationen

Kollektive Operationen sind Grundbausteine für Interaktionsmuster von Prozessen der elektronischen Datenverarbeitung, die häufig Anwendung in SPMD-Algorithmen und paralleler Programmierung finden. Dadurch entsteht die Notwendigkeit, diese Operationen effizient zu realisieren.

Das Message Passing Interface (MPI) stellt eine Realisierung der kollektiven Operationen bereit.

Definitionen

In der asymptotischen Laufzeitanalyse sei die Latenz $\alpha$, die Kommunikationszeit pro Wort $\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. 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. Diese Unterstützung öffnet in der Entwicklung von Algorithmen zusätzliche Möglichkeiten.

Broadcast

→ Hauptartikel: Broadcast

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 SPMD parallelen Programmen Eingaben und globale Variablen zu verteilen. Der Broadcast kann als inverse 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' 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

Informationsfluss von Reduktion ausgeführt auf drei Einheiten. 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 $\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 möglich ist.

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

All-reduce

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 $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 (#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

→ Hauptartikel: Präfixsumme

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 $\otimes$ 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 $\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 (#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 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 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

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 $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)$ der 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

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 $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

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 $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 (#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, 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.

Informationsfluss von All-to-All ausgeführt auf drei Einheiten. Buchstaben indizieren Einheiten und Nummern indizieren Informationselemente.

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))$

Literatur

• Peter Sanders, Kurt Mehlhorn, Martin Dietzfelbinger, Roman Dementiev: Sequential and Parallel Algorithms and Data Structures – The Basic Toolbox. Springer Nature Switzerland AG, 2019, ISBN 978-3-03025208-3.