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

Hypercube Algorithm

Problem: How to embed ring into hypercube?

• 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.

Can we construct such a function H?