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$
?
Author:
Wolfgang Schreiner
Last modification: November 15, 1996