Hypercube (communication pattern)
formula_1-dimensional hypercube is a network topology for parallel computers with formula_2 processing elements. The topology allows for an efficient implementation of some basic communication primitives such as Broadcast, All-Reduce, and Prefix sum. The processing elements are numbered formula_3 through formula_4. Each processing element is adjacent to processing elements whose numbers differ in one and only one bit. The algorithms described in this page utilize this structure efficiently. Algorithm outline. Most of the communication primitives presented in this article share a common template. 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). Each processing element iterates over its neighbors (the expression formula_14 negates the formula_15-th bit in formula_16's binary representation, therefore obtaining the numbers of its neighbors). In each iteration, each processing element exchanges a message with the neighbor and processes the received message afterwards. The processing operation depends on the communication primitive. Communication primitives. Prefix sum. In the beginning of a prefix sum operation, each processing  element formula_16 owns a message formula_18. The goal is to compute formula_19, where formula_20 is an associative operation. The following pseudo code describes the algorithm. The algorithm works as follows. Observe that hypercubes of dimension formula_1 can be split into two hypercubes of dimension formula_38. 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 formula_39 and the sum over all nodes in a sub cube in variable formula_29. This makes it possible for all nodes in 1-sub cube to receive the sum over the 0-sub cube in every step. This results in a factor of formula_41 for formula_42 and a factor of formula_43 for formula_44: formula_45. All-gather / all-reduce. All-gather operations  start with each processing element having a message formula_18. The goal of the operation is for each processing element to know the messages of all other processing elements, i.e. formula_47 where formula_48 is concatenation. The operation can be implemented following the algorithm template. With each iteration, the transferred message doubles in length. This leads to a runtime of formula_60. 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-to-all. Here every processing element has a unique message for all other processing elements. 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 formula_69 steps. In every step, formula_70 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. This results in a run-time of formula_71. ESBT-broadcast. The ESBT-broadcast (Edge-disjoint Spanning Binomial Tree) algorithm is a pipelined broadcast algorithm with optimal runtime for clusters with hypercube network topology. The algorithm embeds formula_1 edge-disjoint binomial trees in the hypercube, such that each neighbor of processing element formula_3 is the root of a spanning binomial tree on formula_4 nodes. To broadcast a message, the source node splits its message into formula_15 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. In each step, the source node sends one of its formula_15 chunks to a binomial tree. Broadcasting the chunk within the binomial tree takes formula_1 steps. Thus, it takes formula_15 steps to distribute all chunks and additionally formula_1 steps until the last binomial tree broadcast has finished, resulting in formula_80 steps overall. Therefore, the runtime for a message of length formula_81 is formula_82. With the optimal chunk size formula_83, the optimal runtime of the algorithm is formula_84. Construction of the binomial trees . This section describes how to construct the binomial trees systematically. First, construct a single binomial spanning tree von formula_2 nodes as follows. Number the nodes from formula_3 to formula_4 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 formula_1 edge-disjoint copies of the tree, translate and rotate the nodes: for the formula_15-th copy of the tree, apply a XOR operation with formula_90 to each node. Subsequently, right-rotate all nodes by formula_15 digits. The resulting binomial trees are edge -disjoint and therefore fulfill the requirements for the ESBT-broadcasting algorithm.