next up previous

3.4 Topology     continued...

Communication in a hypercube is based on the binary representation of node IDs. The nodes are numbered so that two nodes are adjacent if and only if the binary representations of their IDs differ by one bit. For example, nodes 0110 and 0100 are immediate neighbors but 0110 and 0101 are not. An easy way to label nodes is to assign node IDs as the cube is constructed. When you copy an (n-1)-dimensional cube, make sure the corresponding nodes in the two copies have the same IDs. Then extend all the IDs by one bit. Append a 0 to the IDs of nodes in the original cube, and append a 1 to the IDs of nodes in the copy. As an example the nodes in the 1D and 2D cubes in Figure 11 are labeled according to this scheme; the labeling of the 3D and 4D cubes is left for an exercise.

Node IDs are the basis for a simple algorithm for routing information in a hypercube. An n-dimensional cube will have n-bit node IDs. Sending a message from node A to node B can be done in n cycles, where on each cycle a node will either hold a message or forward it along one of its links. On cycle i the node that currently holds the message will compare bit i of its own ID with bit i of the destination ID. If the bits match, the node holds the message. If they don't match, it forwards the message along dimension i, where dimension i is the dimension that was added in the step of the construction of the cube (i.e. it is the same ``direction'' at all nodes). As an example, the path from node 2 to node 7 in a 4D cube is marked with a heavy gray line in Figure 11.