next up previous

Exercise 13: A cosideration of a parallel machine with a hypercube topology.

Each vertex of a d-dimensional hypercube is connected to d other vertices. In a parallel machine with a hypercube topology, there is a single processor at each node, and it is linked to d other processors. An alternative design is to place a ring of d processors at each vertex, linking the i processor to the neighboring vertex along dimension i. The result is a topology known as a cube-connected cycle (CCC) (Figure 22). Every node in a CCC is connected to 3 other nodes: its two neighbors in the ring plus the node in the neighboring vertex. Thus a CCC has a constant degree, no matter how many nodes are in the topology.

(a) What is the diameter of a CCC (assume bidirectional communication).

(b) How many nodes are in a general n-dimensional CCC?

(c) Draw a picture of a 4-dimensional CCC.