Go backward to Ring Algorithm Go up to Top Go forward to Ring Successor

Hypercube Algorithm

• Simple solution $H(i)\; =\; i$:
  • Ring processor $i$ is mapped to hypercube processor $H(i)$.
  • Massive non-neighbor communication!
• How to preserve neighbor-to-neighbor communication? (see Quinn, Figure 5-13)
• Requirements for $H(i)$:
  • $H$ must be a 1-to-1 mapping.
  • $H(i)$ and $H(i+1)$ must differ in 1 bit.
  • $H(0)$ and $H(N-1)$ must differ in 1 bit.