Hyperwürfel (Kommunikationsmuster)

Der $d$-dimensionale Hyperwürfel ist eine Netztopologie für Rechnerbündel mit $2^{d}$ Rechnern. Sie erlaubt eine effiziente Implementierung der Kommunikations-Grundmuster Broadcast, Gossip, All-Reduce und der Partialsummenbildung. Dazu werden die teilnehmenden Rechner von $0$ bis $2^{d}-1$ binär durchnummeriert. Jeder Rechner $i$ besitzt dann eine direkte Verbindung zu den $d$ Rechnern, deren Nummern sich in genau einem Bit von $i$ unterscheiden. Diese Struktur wird von den folgenden Algorithmen effizient ausgenutzt.

Skizze

Einige der Kommunikationsprimitiven lassen sich nach derselben Skizze implementieren, die in diesem Abschnitt vorgestellt wird. Zu Beginn jeder Kommunikationsprimitive besitzt jeder teilnehmende Rechner eine Nachricht, die im Laufe der Kommunikation einmal jeden anderen Rechner erreichen muss. Dieser Ablauf wird vom folgenden Pseudocode skizziert, wobei Initialisierung, Operation und Ausgabe von der Kommunikationsprimitive abhängige Platzhalter sind.

Eingabe: Nachricht $m$.
Ausgabe: Abhängig von den Platzhaltern Initialisierung, Operation und Ausgabe.
Initialisierung
$s:=m$
for $0\leq k<d$ do
    $y:=i{\text{ XOR }}2^{k}$
    Sende $s$ an $y$
    Empfange $m$ von $y$
    Operation$(s,m)$
endfor
Ausgabe

Im Pseudocode iteriert jeder Rechner einmal über seine Nachbarn, denn der Ausdruck $i{\text{ XOR }}2^{k}$ negiert das $k$-te Bit in der Binärdarstellung von $i$, beschreibt also gerade die Nummer des $k$-ten Nachbarns von Rechner $i$. Jeder Rechner tauscht nun eine Nachricht $s$ mit diesem Nachbarn aus und verarbeitet anschließend seine aktuelle Nachricht $s$ mit der empfangenen Nachricht $m$, wobei sich die anzuwendende Akkumulationsoperation nach Kommunikationsprimitive unterscheidet.

Die Algorithmenskizze angewandt auf einen $3$-dimensionalen Hyperwürfel. Im ersten Schritt (vor jeder Kommunikation) besitzt jeder Rechner eine Nachricht (blau), die er im jeweiligen Schritt entlang der rot markierten Dimension mit seinem Nachbarn austauscht. Nach einem Austausch werden die Nachricht in diesem Beispiel konkateniert. Nach dem letzten Schritt besitzt jeder Rechner jede Nachricht.

Kommunikationsprimitiven

Präfixsumme

Bei der Präfixsumme besitzt jeder Prozessor $i$ zu Beginn eine Nachricht $m_{i}$. Das Ziel ist es, dass jeder Prozessor $i$ am Ende $\bigoplus _{0\leq j\leq i}m_{j}$ für eine assoziative Operation $\oplus$ erhält. Der Algorithmus kann wie folgt in die Algorithmenskizze eingebettet werden:

Eingabe: Nachricht $m_{i}$ auf Prozessor $i$.
Ausgabe: Präfixsumme $\bigoplus _{0\leq j\leq i}m_{j}$ auf Prozessor $i$.
$x:=m_{i}$
$\sigma :=m_{i}$
for $0\leq k\leq d-1$ do
    $y:=i{\text{ XOR }}2^{k}$
    Sende $\sigma$ an $y$
    Empfange $m$ von $y$
    $\sigma :=\sigma \oplus m$
    if Bit $k$ in $i$ gesetzt then $x:=x\oplus m$
endfor

Ein Hyperwürfel der Dimension $d$ kann in zwei Hyperwürfel der Dimension $d-1$ zerlegt werden. Dazu wird im Weiteren der Teilwürfel aller Knoten, deren Nummer in Binärdarstellung mit 0 beginnen, als 0-Teilwürfel bezeichnet. Die restlichen Knoten bilden analog den 1-Teilwürfel. Nachdem in beiden Teilwürfeln die Präfixsumme berechnet wurde, muss die Gesamtsumme der Elemente im 0-Teilwürfel noch auf alle Elemente des 1-Teilwürfels aufaddiert werden. Das liegt daran, dass nach Definition die Rechner im 0-Teilwürfel einen kleineren Rang als die Rechner im 1-Teilwürfel besitzen. In der Implementierung speichert jeder Knoten deswegen neben seiner Präfixsumme (Variable $x$) außerdem die Summe über alle Elemente im Teilwürfel (Variable $\sigma$). So können in jedem Schritt alle Knoten im 1-Teilwürfel die Gesamtsumme über den 0-Teilwürfel beziehen.

Bei der Laufzeit ergibt sich ein Faktor von $\log p$ für $T_{\text{start}}$ und ein Faktor von $n\log p$ für $T_{\text{byte}}$: $T(n,p)=(T_{\text{start}}+nT_{\text{byte}})\log p$.

Beispiel für eine Präfixsummenberechnung. Jeder Knoten startet mit seiner eigenen Knotennummer als Nachricht, d. h. $m_{i}=i$. Die obere Zeile eines Knotens zeigt $x$, die untere Zeile $\sigma$. Die Operation ist Addition.

Gossip / All-Reduce

Bei der Gossip Operation startet jeder Rechner mit einer Nachricht $m_{i}$. Ziel ist es, dass nach der Ausführung jeder Rechner alle Rechner kennt, also über die Nachricht $x:=m_{0}\cdot m_{1}\dots m_{p}$ verfügt, wobei $\cdot$ die Konkatenation bezeichne. Diese Operation kann wie folgt mit der Algorithmenskizze implementiert werden:

Eingabe: Nachricht $x:=m_{i}$ auf Prozessor $i$.
Ausgabe: Alle Nachrichten $m_{1}\cdot m_{2}\dots m_{p}$.
$x:=m_{i}$
for $0\leq k<d$ do
    $y:=i{\text{ XOR }}2^{k}$
    Sende $x$ an $y$
    Empfange $x'$ von $y$
    $x:=x\cdot x'$
endfor

Der Ablauf folgt der Skizze. Man beachte, dass sich die Länge der übermittelelten Nachrichten in jedem Schritt verdoppelt. Dadurch ergibt sich folgende Laufzeit: $T(n,p)\approx \sum _{j=0}^{d-1}(T_{\text{start}}+n\cdot 2^{j}T_{\text{byte}})=\log(p)T_{\text{start}}+(p-1)nT_{\text{byte}}$.

Bei All-Reduce werden im Gegensatz zu Gossip die Nachrichten nicht konkateniert, sondern ein Operator auf die zwei Nachrichten angewandt. Es ist also eine Reduce-Operation deren Ergebnis jedem Prozessor zur Verfügung steht. Im Hyperwürfel lässt sich der Gossip-Algorithmus anpassen. Dies reduziert die Anzahl der Kommunikationsschritte gegenüber Reduce und Broadcast.

All-to-All

Bei der All-to-All Kommunikation hat jeder Prozessor eine eigene Nachricht für alle anderen Prozessoren.

Eingabe: Nachrichten $m_{ij}$ auf Prozessor $i$ an Prozessor $j$.
for $d>k\geq 0$ do
   Erhalte von Prozessor $i{\text{ XOR }}2^{k}$:
       alle Nachrichten für meinen $k$-dimensionalen Teilwürfel
   Sende an Prozessor $i{\text{ XOR }}2^{k}$:
       alle Nachrichten für seinen $k$-dimensionalen Teilwürfel
endfor

Eine Nachricht kommt in jedem Iterationsschritt eine Dimension näher an ihr Ziel, sollte sie es noch nicht erreicht haben. Demnach werden nur maximal $d=\log {p}$ viele Schritte benötigt. In jedem Schritt werden $p/2$ Nachrichten verschickt. Für den ersten Schritt liegen genau die Hälfte der Nachrichten nicht im eigenen Teilwürfel. In den allen folgenden Schritten ist der Teilwürfel nur noch halb so groß wie davor, allerdings wurden im vorhergegangenen Schritt genauso viele Nachrichten von einem anderen Prozessor erhalten, die auch für diesen Teilwürfel bestimmt sind.

Insgesamt bedeutet dies eine Laufzeit von $T(n,p)\approx \log {p}(T_{\text{start}}+{\frac {p}{2}}nT_{\text{byte}})$.

ESBT-Broadcast

Der ESBT-Broadcast (Edge-disjoint Spanning Binomial Tree) Algorithmus ist ein zeitoptimaler Broadcast für Rechnerbündel mit Hyperwürfel-Netztopologie. Dazu wird das Netz ausgehend von der Quelle (im Folgenden der $0$-Rechner) in $d$ kantendisjunkte Binomialbäume aufgeteilt, so dass jeder Nachbar der Quelle die Wurzel eines Binomialbaums mit $2^{d}-1$ Rechnern ist. Die Quelle zerteilt ihre Nachricht nun in $k$ Teilnachrichten, die dann zyklisch an die Wurzeln der Binomialbäume verteilt werden. Jeder Binomialbaum führt anschließend einen Broadcast aus.

Verteilt die Quelle in jedem Schritt eine Teilnachricht, hat sie nach $k$ Schritten alle Teilnachrichten verteilt. Der Broadcast in einem Binomialbaum benötigt $d$ Schritte. Insgesamt werden somit $k+d$ Schritte benötigt, bis der Broadcast für die letzte Nachricht abgeschlossen ist und die Laufzeit für eine Nachricht der Länge $n$ ergibt sich zu $T(n,p,k)=\left({\frac {n}{k}}T_{\text{byte}}+T_{\text{start}}\right)(k+d)$. Das optimale $k^{*}={\sqrt {\frac {nd\cdot T_{\text{byte}}}{T_{\text{start}}}}}$ minimiert die Laufzeit zu $T^{*}(n,p)=n\cdot T_{\text{byte}}+\log(p)\cdot T_{\text{start}}+{\sqrt {n\log(p)\cdot T_{\text{start}}\cdot T_{\text{byte}}}}$.

Aufbau der Binomialbäume

Ein $3$-dimensionaler Hyperwürfel mit drei kantendisjunkten ESBTs.

Die $d$ Binomialbäume können systematisch nach der folgender Vorschrift konstruiert werden. Dazu wird zunächst ein Binomialbaum mit $2^{d}$ Knoten definiert. Anschließend werden durch Translation und Rotation $d$ kantendisjunkte Kopien des Binomialbaums in den Hyperwürfel eingebettet.

Ein einzelner Binomialbaum hat Knoten $0$ als Wurzel. Die Kinder eines Knotens ergeben sich durch Negation der führenden Nullen in der Binärdarstellung der Knotennummer. Der so resultierende Graph ist offensichtlich ein Binomialbaum. Die Kantenmenge des $k$-ten Binomialbaums im Hyperwürfel erhält man nun wie folgt: auf jeden Knoten wendet man eine XOR-Operation mit $2^{k}$ an und verschiebt die Binärdarstellung der Knotennummer anschließend um $k$ Stellen zyklisch nach rechts. Die so entstehenden $d$ Kopien des ausgehenden Binomialbaums sind kantendisjunkt und erfüllen somit die Voraussetzungen des ESBT-Broadcast Algorithmus.