Hypercube (communication pattern)

d -dimensional hypercube is a network topology for parallel computers with 2^d processing elements.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

d -dimensional hypercube is a network topology for parallel computers with 2^d 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 0 through 2^d - 1 .

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. s := m for 0 \leq k do y := i \text{ XOR } 2^k Send s to y Receive m from y Operation (s, m) endfor Output Each processing element iterates over its neighbors (the expression i \text{ XOR } 2^k negates the k -th bit in i '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. x := m_i \sigma := m_i for 0 \le k \le d - 1 do y := i \text{ XOR } 2^k Send \sigma to y Receive m from y \sigma := \sigma \oplus m if bit k in i is set then x := x \oplus m endfor The algorithm works as follows.

Observe that hypercubes of dimension d can be split into two hypercubes of dimension d - 1 . 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 x and the sum over all nodes in a sub cube in variable \sigma .

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 \log p for T_\text{start} and a factor of n\log p for T_\text{byte} : T(n,p) = (T_\text{start} + nT_\text{byte})\log p . All-gather operations start with each processing element having a message m_i . The goal of the operation is for each processing element to know the messages of all other processing elements, i.e. x := m_0 \cdot m_1 \dots m_p where \cdot is concatenation.

The operation can be implemented following the algorithm template. Input: message x := m_i at processing unit i . Output: all messages m_1 \cdot m_2 \dots m_p . x := m_i for 0 \le k do y := i \text{ XOR } 2^k Send x to y Receive x' from y x := x \cdot x' endfor With each iteration, the transferred message doubles in length.

This leads to a runtime of 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} . 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. 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 d = \log{p} steps.

In every step, p / 2 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 T(n,p) \approx \log{p} (T_\text{start} + \frac{p}{2}nT_\text{byte}) . In each step, the source node sends one of its k chunks to a binomial tree. Broadcasting the chunk within the binomial tree takes d steps.

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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353036110 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001353036110 · captured 1778175959.0 · version history

Cite this page as: encyclopegia.org, “Hypercube (communication pattern)”, snapshot enwiki-001353036110. https://encyclopegia.org/a/hypercube-communication-pattern

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.