Hypercube (communication pattern): Difference between revisions

Revision as of 16:08, 24 February 2020

Latest revision as of 05:47, 17 February 2025

(One intermediate revision by one other user not shown)

Line 1:

<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 (networking)|Broadcast]], All-[[Reduce (parallel 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 <math>0</math> through <math>2^d - 1</math>. 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 ==

Line 86:

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.

== See also ==

* [[Hypercube internetwork topology]]

==References==