|
The <math>d</math>-dimensional [[hypercube]] is a network topology for parallel computers with <math>2^d</math> processing elements. The topology allows for an efficient implementation of some basic communication primitives such as [[Broadcasting_Broadcasting (networking)|Broadcast]], All-[[Reduce_Reduce (parallel_patternparallel pattern)|Reduce]], and [[Prefix sum]].<ref>Grama, A.(2003). Introduction to Parallel Computing. Addison Wesley; Auflage: 2 ed. {{ISBN: |978-0201648652}}.</ref> The processing elements are numbered from <math>0</math> tothrough <math>2^d - 1</math>. Each processing elementselement is then adjacent to processing elements whose numbers differ in exactlyone and only one bit. The algorithms described onin this page utilize this structure efficiently.
== OutlineAlgorithm outline ==
Most of the communication primitives presented in this article share a common template.<ref>Foster, I.(1995). Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Addison Wesley; {{ISBN: |0201575949}}.</ref>. Initially, each processing element possesses one message that must reach every other processing element during the course of the algorithm. The following pseudo code sketches the communication steps necessary. Hereby, '''Initialization''', '''Operation''', and '''Output''' are placeholderplaceholders that depend on the given communication primitive (see next section).
'''Input:''' message <math>m</math>.
'''Output:''' depends on '''initializationInitialization''', '''operationOperation''' undand '''outputOutput'''.
'''Initialization'''
<math>s := m</math>
<math>y := i \text{ XOR } 2^k</math>
'''Send''' <math>s</math> '''to''' <math>y</math>
'''RecieveReceive''' <math>m</math> '''from''' <math>y</math>
'''Operation'''<math>(s, m)</math>
'''endfor'''
'''Output'''
Each processing element iterates over its neighbors (the expression <math>i \oplustext{ XOR } 2^k</math> negates the <math>k</math>-th bit in <math>i</math>'s binary representation, therefore obtaining the numbers of its neighbors). DuringIn aneach iteration, each processing element exchanges a message with the neighbor and processes the received message afterwards. The processing operation depends on the communication primitive.
[[File:Hypergraph Communication Pattern.png|thumb|OutlineAlgorithm outline applied to the <math>3</math>-dimensional hypercube. In the first step (before any communication), each processing element possesses one message (blue). Communication is marked red. After each step, the processing elements store the received message, but other operations are also possible.]]
== Communication Primitivesprimitives ==
=== PrefixsumPrefix sum ===
AtIn the beginngbeginning of a [[prefixsumprefix sum]] operation, each processing unitelement <math>i</math> owns a message <math>m_i</math>. AtThe thegoal end each processing unit <math>i</math>is shouldto recievecompute <math>\bigoplus_{0 \le j \le i} m_j</math>, where <math>\oplus</math> is an associative operation. The following pseudo code describes the algorithmnalgorithm.
'''inputInput''': message <math>m_i</math> of processor <math>i</math>.
'''outputOutput''': prefixsumprefix sum <math>\bigoplus_{0 \le j \le i} m_j</math> of processor <math>i</math>.
<math>x := m_i</math>
<math>\sigma := m_i</math>
<math>y := i \text{ XOR } 2^k</math>
'''Send''' <math>\sigma</math> '''to''' <math>y</math>
'''RecieveReceive''' <math>m</math> '''from''' <math>y</math>
<math>\sigma := \sigma \oplus m</math>
'''if''' bit <math>k</math> in <math>i</math> is set '''then''' <math>x := x \oplus m</math>
'''endfor'''
The algorithm works as follows. Observe that hypercubes of dimension <math>d</math> can be split into two hypercubes of dimension <math>d - 1</math>. Refer to the sub cube containing nodes with a leading 0 as the 0-sub cube and the sub cube consisting of nodes with a leading 1 as 1-sub cube. Once both sub cubes have calculated the prefix sum, the sum over all elements in the 0-sub cube has to be added to the every element in the 1-sub cube, since every processing element in the 0-sub cube has a lower rank than the processing elements in the 1-sub cube. The pseudo code stores the prefix sum in variable <math>x</math> and the sum over all nodes in a sub cube in variable <math>\sigma</math>.
Bei der [[Präfixsumme]] besitzt jeder Prozessor <math>i</math> zu Beginn eine Nachricht <math>m_i</math>. Das Ziel ist es, dass jeder Prozessor <math>i</math> am Ende <math>\bigoplus_{0 \le j \le i}</math> für eine assoziative Operation <math>\oplus</math> erhält. Der Algorithmus kann wie folgt in die Algorithmenskizze eingebettet werden:
This makes it possible for all nodes in 1-sub cube to receive the sum over the 0-sub cube in every step.
BeiThis derresults Laufzeitin ergibta sichfactor ein Faktor vonof <math>\log p</math> fürfor <math>T_\text{start}</math> undand eina Faktorfactor vonof <math>n\log p</math> fürfor <math>T_\text{byte}</math>: <math>T(n,p) = (T_\text{start} + nT_\text{byte})\log p</math>. ▼ '''Eingabe''': Nachricht <math>m_i</math> auf Prozessor <math>i</math>.
[[File:Hypergraph Communication Steps for Prefix Sum.png|thumb|Example for a prefix sum calculation. Upper number: tentatetive prefix sum (variable <math>x</math>). Lower number: sum over all elements in the sub cube (variable <math>\sigma</math>).]]
'''Ausgabe''': Präfixsumme <math>\bigoplus_{0 \le j \le i}</math> auf Prozessor <math>i</math>.
<math>x := m_i</math>
<math>\sigma := m_i</math>
'''for''' <math>0 \le k \le d - 1</math> '''do'''
<math>y := i \text{ XOR } 2^k</math> ▼ '''Sende''' <math>\sigma</math> '''an''' <math>y</math>
'''Empfange''' <math>m</math> '''von''' <math>y</math>
<math>\sigma := \sigma \oplus m</math>
'''if''' Bit <math>k</math> in <math>i</math> gesetzt '''then''' <math>x := x \oplus m</math>
'''endfor'''
Ein Hyperwürfel der Dimension <math>d</math> kann in zwei Hyperwürfel der Dimension <math>d - 1</math> 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 <math>x</math>) außerdem die Summe über alle Elemente im Teilwürfel (Variable <math>\sigma</math>). 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 <math>\log p</math> für <math>T_\text{start}</math> und ein Faktor von <math>n\log p</math> für <math>T_\text{byte}</math>: <math>T(n,p) = (T_\text{start} + nT_\text{byte})\log p</math>.
Hypercubes of dimension <math>d</math> can be split into two hypercubes of dimension <math>d - 1</math>.
[[File:Hypergraph Communication Steps for Prefix Sum.png|thumb|Beispiel für eine Präfixsummenberechnung. Jeder Knoten startet mit seiner eigenen Knotennummer als Nachricht, d.h. <math>m_i = i</math>. Die obere Zeile eines Knotens zeigt <math>x</math>, die untere Zeile <math>\sigma</math>. Die Operation ist Addition.]]
=== GossipAll-gather / Allall-Reducereduce ===
'''GossipAll-gather''' operations start with each processing unitelement having a message <math>m_i</math>. AfterThe goal of the operation is finishedfor each processing unitelement knowsto know the messages of all other processing unitselements, so has the messagei.e. <math>x := m_0 \cdot m_1 \dots m_p</math> where <math>\cdot</math> is concatenation. The operation can be implemented following the algorithmnalgorithm template.
'''inputInput''': message <math>x := m_i</math> at processing unit <math>i</math>.
'''outputOutput''': all messages <math>m_1 \cdot m_2 \dots m_p</math>.
<math>x := m_i</math>
'''for''' <math>0 \le k < d</math> '''do'''
<math>y := i \text{ XOR } 2^k</math>
'''Send''' <math>x</math> '''to''' <math>y</math>
'''RecieveReceive''' <math>x'</math> '''from''' <math>y</math>
<math>x := x \cdot x'</math>
'''endfor'''
With each iteration, the transferedtransferred message doubles in length. This leads to a run-timeruntime of <math>T(n,p) \approx \sum_{j=0}^{d-1}(T_\text{start} + n \cdot 2^jT_\text{byte})= \log(p) T_\text{start} + (p-1)nT_\text{byte}</math>.
The same principle can be applied to the '''All-Reduce''' operations, but instead of concatenating the messages, it performs a reduction operation on the two messages. So it is a '''Reduce''' operation, where all processing units know the result. Compared to a normal reduce operation followed by a broadcast, All-Reduce in hypercubes reduces the number of communication steps.
'''All-Reduce''' is an operation
Bei der Gossip Operation startet jeder Rechner mit einer Nachricht <math>m_i</math>. Ziel ist es, dass nach der Ausführung jeder Rechner die Nachrichten aller Rechner kennt, also über die Nachricht <math>x := m_0 \cdot m_1 \dots m_p</math> verfügt, wobei <math>\cdot</math> die Konkatenation bezeichne. Diese Operation kann wie folgt mit der Algorithmenskizze implementiert werden:
Here every processing element has a unique message for all other processing elements.
'''EingabeInput:''': Nachrichtmessage <math>xm_{ij}</math> :=at m_iprocessing element <math>i</math> aufto Prozessorprocessing element <math>ij</math>.
'''Ausgabefor''': Alle Nachrichten <math>m_1d \cdot> m_2k \dotsgeq m_p0</math>. '''do'''
▲ '''Receive''' from processing element <math> y := i \text{ XOR } 2^k</math> :
<math>x := m_i</math>
''' all messages for''' my <math>0 \le k < d</math>-dimensional sub '''do'''cube
'''Send''' to processing element <math>y := i \text{ XOR } 2^k</math>:
'''Sende''' <math>x</math> '''an''' all messages for its <math>yk</math>-dimensional sub cube
'''Empfange''' <math>x'</math> '''von''' <math>y</math>
<math>x := x \cdot x'</math>
'''endfor'''
With each iteration a messages comes closer to its destination by one dimension, if it hasn't arrived yet. Hence, all messages have reached their target after at most <math>d = \log{p}</math> steps. In every step, <math>p / 2</math> messages are sent: in the first iteration, half of the messages aren't meant for the own sub cube. In every following step, the sub cube is only half the size as before, but in the previous step exactly the same number of messages arrived from another processing element.
InsgesamtThis bedeutetresults diesin einea Laufzeitrun-time von:of <math>T(n,p) \approx \log{p} (T_\text{start} + \frac{p}{2}nT_\text{byte}) </math> .▼
== ESBT- Broadcastbroadcast == ▼Der Ablauf folgt der Skizze. Man beachte, dass sich die Länge der übermittelelten Nachrichten in jedem Schritt verdoppelt. Dadurch ergibt sich folgende Laufzeit: <math>T(n,p) \approx \sum_{j=0}^{d-1}(T_\text{start} + n \cdot 2^jT_\text{byte})= \log(p) T_\text{start} + (p-1)nT_\text{byte}</math>.
The ESBT-broadcast (Edge-disjoint Spanning Binomial Tree) algorithm<ref>{{cite journal|last1=Johnsson|first1=S.L.|last2=Ho|first2=C.-T.|title=Optimum broadcasting and personalized communication in hypercubes|journal=IEEE Transactions on Computers|volume=38|issue=9|year=1989|pages=1249–1268|issn=0018-9340|doi=10.1109/12.29465}}</ref> is a pipelined broadcast algorithm with optimal runtime for clusters with hypercube network topology. The algorithm embeds <math>d</math> edge-disjoint binomial trees in the hypercube, such that each neighbor of processing element <math>0</math> is the root of a spanning binomial tree on <math>2^d - 1</math> nodes. To broadcast a message, the source node splits its message into <math>k</math> chunks of equal size and cyclically sends them to the roots of the binomial trees. Upon receiving a chunk, the binomial trees broadcast it.
=== Runtime ===
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.
VerteiltIn dieeach Quellestep, inthe jedemsource Schrittnode eine Teilnachricht,sends hatone sieof nachits <math>k</math> Schrittenchunks alleto Teilnachrichtena verteiltbinomial tree. DerBroadcasting Broadcastthe inchunk within the einembinomial Binomialbaumtree benötigttakes <math>d</math> Schrittesteps. InsgesamtThus, werdenit somittakes <math>k </math> +steps to distribute all chunks and additionally <math>d</math> Schrittesteps benötigtuntil the last binomial tree broadcast has finished, bisresulting derin Broadcast<math>k für+ died</math> letztesteps Nachrichtoverall. abgeschlossenTherefore, istthe undruntime diefor Laufzeita ergibtmessage sichof length <math>n</math> zuis <math>T(n, p, k) = \left(\frac{n}{k} T_\text{byte} + T_\text{start} \right ) (k + d)</math>. DasWith optimalethe optimal chunk size <math>k^* = \sqrt{\frac{nd \cdot T_\text{byte}}{T_\text{start}}}</math> , the optimal runtime minimiertof diethe Laufzeitalgorithm zuis <math>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}}</math>. ▼
=== Construction of the binomial trees ===
[[File:HypergraphESBT.png|thumb|A <math>3</math>-dimensional hypercubes with three ESBT embedded.]] ▼Bei der All-to-All Kommunikation hat jeder Prozessor eine eigene Nachricht für alle anderen Prozessoren.
This section describes how to construct the binomial trees systematically. First, construct a single binomial spanning tree von <math>2^d</math> nodes as follows. Number the nodes from <math>0</math> to <math>2^d - 1</math> and consider their binary representation. Then the children of each nodes are obtained by negating single leading zeroes. This results in a single binomial spanning tree. To obtain <math>d</math> edge-disjoint copies of the tree, translate and rotate the nodes: for the <math>k</math>-th copy of the tree, apply a XOR operation with <math>2^k</math> to each node. Subsequently, right-rotate all nodes by <math>k</math> digits. The resulting binomial trees are edge-disjoint and therefore fulfill the requirements for the ESBT-broadcasting algorithm.
'''Eingabe:''' Nachrichten <math>m_{ij}</math> auf Prozessor <math>i</math> an Prozessor <math>j</math>.
'''for''' <math>d > k \geq 0</math> '''do'''
'''Erhalte''' von Prozessor <math>i \text{ XOR } 2^k</math>:
alle Nachrichte für meinen <math>k</math>-dimensionalen Teilwürfel
'''Sende''' an Prozessor <math>i \text{ XOR } 2^k</math>:
alle Nachrichte für seinen <math>k</math>-dimensionalen Teilwürfel
'''endfor'''
== See also ==
Eine Nachricht kommt in jedem Iterationsschritt eine Dimension näher an ihr Ziel, sollte sie es noch nicht erreicht haben. Demnach werden nur maximal <math>d = \log{p}</math> viele Schritte benötigt. In jedem Schritt werden <math>p / 2</math> 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 vorhergegangenem Schritt genauso viele Nachrichten von einem anderen Prozessor erhalten, die auch für diesen Teilwürfel bestimmt sind.
▲Insgesamt bedeutet dies eine Laufzeit von: <math>T(n,p) \approx \log{p} (T_\text{start} + \frac{p}{2}nT_\text{byte}) </math>
Der ESBT-Broadcast (Edge-disjoint Spanning Binomial Tree) Algorithmus<ref>{{cite journal|last1=Johnsson|first1=S.L.|last2=Ho|first2=C.-T.|title=Optimum broadcasting and personalized communication in hypercubes|journal=IEEE Transactions on Computers|volume=38|issue=9|year=1989|pages=1249–1268|issn=00189340|doi=10.1109/12.29465}}</ref> ist ein zeitoptimaler Broadcast für Rechnerbündel mit Hyperwürfel-Netztopologie. Dazu wird das Netz ausgehend von der Quelle (im Folgendem der <math>0</math>-Rechner) in <math>d</math> kantendisjunkte Binomialbäume aufgeteilt, so dass jeder Nachbar der Quelle die Wurzel eines Binomialbaums mit <math>2^d - 1</math> Rechnern ist. Die Quelle zerteilt ihre Nachricht nun in <math>k</math> 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 <math>k</math> Schritten alle Teilnachrichten verteilt. Der Broadcast in einem Binomialbaum benötigt <math>d</math> Schritte. Insgesamt werden somit <math>k + d</math> Schritte benötigt, bis der Broadcast für die letzte Nachricht abgeschlossen ist und die Laufzeit ergibt sich zu <math>T(n, p, k) = \left(\frac{n}{k} T_\text{byte} + T_\text{start} \right)</math>. Das optimale <math>k^* = \sqrt{\frac{nd \cdot T_\text{byte}}{T_\text{start}}}</math> minimiert die Laufzeit zu <math>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}}</math>.
=== Aufbau der Binomialbäume ===
▲[[File:HypergraphESBT.png|thumb|A <math>3</math>-dimensional hypercubes with three ESBT embedded.]]
* [[Hypercube internetwork topology]]
Die <math>d</math> Binomialbäume können systematisch nach der folgender Vorschrift konstruiert werden. Dazu wird zunächst ein Binomialbaum mit <math>2^d</math> Knoten definiert. Anschließend werden durch Translation und Rotation <math>d</math> kantendisjunkte Kopien des Binomialbaums in den Hyperwürfel eingebettet.
==References==
Ein einzelner Binomialbaum hat Knoten <math>0</math> 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 <math>k</math>-ten Binomialbaums im Hyperwürfel erhält man nun wie folgt: auf jeden Knoten wendet man eine XOR-Operation mit <math>2^k</math> an und verschiebt die Binärdarstellung der Knotennummer anschließend um <math>k</math> Stellen zyklisch nach rechts. Die so entstehenden <math>d</math> Kopien des ausgehenden Binomialbaums sind kantendisjunkt und erfüllen somit die Voraussetzungen des ESBT-Broadcast Algorithmus.
{{Reflist}}
[[Category:Parallel computing]]
== Referenzen ==
| 