[comp.hypercube] T or routing

Wen-King@hubcap.UUCP (07/14/87)

In article <282@hubcap.UUCP> gdburns@TCGOULD.TN.CORNELL.EDU (Greg Burns) writes:
 >I have a semi-interesting problem with routing on a loop that is actually
 >threaded through a hypercube.  Let's say that a loop is mapped onto
 >a hypercube in the following way:
 >
 >000 001 011 010 110 111 101 100

Given that:

    NODE = node number of this node.
    MASK = (2**(dimension of cube)) - 1.

Using these routines:

    bin_grey(n) int n; { return(n ^ (n >> 1)); }
    grey_bin(n) int n; { int i; for(i = n; n >>= 1; i ^= n); return(i); }

To make a ring:

    preceeding node = bin_grey( ( grey_bin(NODE) - 1 ) & MASK );
    suceeding node  = bin_grey( ( grey_bin(NODE) + 1 ) & MASK );

+--------------------------------------------------------------------------+
| Wen-King Su  wen-king@vlsi.caltech.edu  Caltech Corp of Cosmic Engineers |
+--------------------------------------------------------------------------+