Hypercube (communication pattern)

The ${\displaystyle d}$-dimensional hypercube is a network topology for parallel computers with ${\displaystyle 2^{d}}$ processing elements. The topology allows for an efficient implementation of some basic communication primitives such as Broadcast, All-Reduce and Prefix sum.^[1] The processing elements are numbered from ${\displaystyle 0}$ to ${\displaystyle 2^{d}-1}$. Each processing elements is then adjacent to processing elements whose numbers differ in exactly one bit. The algorithms described on this page utilize this structure efficiently.

Algorithm Outline

Most of the communication primitives presented in this article share a common template.^[2] 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 placeholders that depend on the given communication primitive (see next section).

Input: message ${\displaystyle m}$ .
Output: depends on initialization, operation und output.
Initialization
${\displaystyle s:=m}$ 
for ${\displaystyle 0\leq k<d}$  do
    ${\displaystyle y:=i{\text{ XOR }}2^{k}}$ 
    Send ${\displaystyle s}$  to ${\displaystyle y}$ 
    Recieve ${\displaystyle m}$  from ${\displaystyle y}$ 
    Operation${\displaystyle (s,m)}$ 
endfor
Output

Each processing element iterates over its neighbors (the expression ${\displaystyle i\oplus 2^{k}}$  negates the ${\displaystyle k}$ -th bit in ${\displaystyle i}$ 's binary representation, therefore obtaining the numbers of its neighbors). During an iteration, each processing element exchanges a message with the neighbor and processes the received message afterwards. The processing operation depends on the communication primitive.

 

Algorithm outline applied to the ${\displaystyle 3}$ -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 Primitives

Prefixsum

At the beginng of a prefixsum operation each processing unit ${\displaystyle i}$  owns a message ${\displaystyle m_{i}}$ . At the end each processing unit ${\displaystyle i}$  should recieve ${\displaystyle \bigoplus _{0\leq j\leq i}}$ , where ${\displaystyle \oplus }$  is an associative operation. The following pseudo code describes the algorithmn.

input: message ${\displaystyle m_{i}}$  of processor ${\displaystyle i}$ .
output: prefixsum ${\displaystyle \bigoplus _{0\leq j\leq i}}$  of processor ${\displaystyle i}$ .
${\displaystyle x:=m_{i}}$  
${\displaystyle \sigma :=m_{i}}$ 
for ${\displaystyle 0\leq k\leq d-1}$  do
    ${\displaystyle y:=i{\text{ XOR }}2^{k}}$ 
    Send ${\displaystyle \sigma }$  to ${\displaystyle y}$ 
    Recieve ${\displaystyle m}$  from ${\displaystyle y}$ 
    ${\displaystyle \sigma :=\sigma \oplus m}$ 
    if bit ${\displaystyle k}$  in ${\displaystyle i}$  is set then ${\displaystyle x:=x\oplus m}$ 
endfor

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

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

Ein Hyperwürfel der Dimension ${\displaystyle d}$  kann in zwei Hyperwürfel der Dimension ${\displaystyle 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 ${\displaystyle x}$ ) außerdem die Summe über alle Elemente im Teilwürfel (Variable ${\displaystyle \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 ${\displaystyle \log p}$  für ${\displaystyle T_{\text{start}}}$  und ein Faktor von ${\displaystyle n\log p}$  für ${\displaystyle T_{\text{byte}}}$ : ${\displaystyle T(n,p)=(T_{\text{start}}+nT_{\text{byte}})\log p}$ .

Hypercubes of dimension ${\displaystyle d}$  can be split into two hypercubes of dimension ${\displaystyle d-1}$ .

 

Example for a prefix sum calculation. Upper number: number ${\displaystyle m_{i}}$  that each processing element contributes to the prefix sum. Lower number: prefix sum (at the end of the computation).

Gossip / All-Reduce

Gossip operations start with each processing element having a message ${\displaystyle m_{i}}$ . After the operation is finished each processing unit knows the messages of all other processing elements, with message ${\displaystyle x:=m_{0}\cdot m_{1}\dots m_{p}}$ . The operation can be implemented following the algorithmn template.

input: message ${\displaystyle x:=m_{i}}$  at processing unit${\displaystyle i}$ .
output: all messages ${\displaystyle m_{1}\cdot m_{2}\dots m_{p}}$ .
${\displaystyle x:=m_{i}}$ 
for ${\displaystyle 0\leq k<d}$  do
    ${\displaystyle y:=i{\text{ XOR }}2^{k}}$ 
    Send ${\displaystyle x}$  to ${\displaystyle y}$ 
    Recieve ${\displaystyle x'}$  from ${\displaystyle y}$ 
    ${\displaystyle x:=x\cdot x'}$ 
endfor

With each iteration the transfered message doubles in length. This leads to a run-time of ${\displaystyle 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}}}$ .

The same principle can be applied to the All-Reduce operations, but instead of concancating the messages, it performs an operation on the two messages. So it is a Reduce operation, where all processing units know the result. In Hypercubes a modified Gossip reduces the number of communications compared to Reduce and Broadcast.

All-to-All

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

Eingabe: Nachrichten ${\displaystyle m_{ij}}$  auf Prozessor ${\displaystyle i}$  an Prozessor ${\displaystyle j}$ .
for ${\displaystyle d>k\geq 0}$  do
   Erhalte von Prozessor ${\displaystyle i{\text{ XOR }}2^{k}}$ :
       alle Nachrichte für meinen ${\displaystyle k}$ -dimensionalen Teilwürfel
   Sende an Prozessor ${\displaystyle i{\text{ XOR }}2^{k}}$ :
       alle Nachrichte für seinen ${\displaystyle 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 ${\displaystyle d=\log {p}}$  viele Schritte benötigt. In jedem Schritt werden ${\displaystyle 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 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: ${\displaystyle T(n,p)\approx \log {p}(T_{\text{start}}+{\frac {p}{2}}nT_{\text{byte}})}$ 

ESBT-Broadcast

The ESBT-broadcast (Edge-disjoint Spanning Binomial Tree) algorithm^[3] is a pipelined broadcast algorithm with optimal runtime for clusters with hypercube network topology. The algorithm embeds ${\displaystyle d}$  edge-disjoint binomial trees in the hypercube, such that each neighbor of processing element ${\displaystyle 0}$  is the root of a spanning binomial tree on ${\displaystyle 2^{d}-1}$  nodes. To broadcast a message, the source node splits its message into ${\displaystyle k}$  chunks of equal size and cyclically sends them to the roots of the binomial trees. Upon receiving a chunk, the binomial trees broadcast it.

The runtime of this algorithm is as follows. In each step, the source node sends one of its ${\displaystyle k}$  chunks to a binomial tree. Broadcasting the chunk within the binomial tree takes ${\displaystyle d}$  steps. Thus, it takes ${\displaystyle k}$  steps to distribute all chunks and additionally ${\displaystyle d}$  steps until the last binomial tree broadcast has finished, resulting in ${\displaystyle k+d}$  steps overall. Therefore, the runtime for a message of length ${\displaystyle n}$  is ${\displaystyle T(n,p,k)=\left({\frac {n}{k}}T_{\text{byte}}+T_{\text{start}}\right)(k+d)}$ . With the optimal chunk size ${\displaystyle k^{*}={\sqrt {\frac {nd\cdot T_{\text{byte}}}{T_{\text{start}}}}}}$ , the optimal runtime of the algorithm is ${\displaystyle 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}}}}}$ .

Construction of the Binomial Trees

 

A ${\displaystyle 3}$ -dimensional hypercubes with three ESBT embedded.

This section describes how to construct the binomial trees systematically. First, construct a single binomial spanning tree von ${\displaystyle 2^{d}}$  nodes as follows. Number the nodes from ${\displaystyle 0}$  to ${\displaystyle 2^{d}-1}$  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 ${\displaystyle d}$  edge-disjoint copies of the tree, translate and rotate the nodes: for the ${\displaystyle k}$ -th copy of the tree, apply a XOR operation with ${\displaystyle 2^{k}}$  to each node. Afterwards, right rotate all nodes by ${\displaystyle k}$  digits. The resulting binomial trees are edge-disjoint and therefore, fulfill the requirements for the ESBT-broadcasting algorithm.

Referenzen

1. Grama, A.(2003). Introduction to Parallel Computing. Addison Wesley; Auflage: 2 ed. ISBN: 978-0201648652.
2. Foster, I.(1995). Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Addison Wesley; ISBN: 0201575949.
3. Johnsson, S.L.; Ho, C.-T. (1989). "Optimum broadcasting and personalized communication in hypercubes". IEEE Transactions on Computers. 38 (9): 1249–1268. doi:10.1109/12.29465. ISSN 0018-9340.