3.1.3 Hypercube Topology and Embedding

Hypercube Topology

In a Hypercube interconnection topology, the number of processors is always an exact power of 2. Here , the d is defined the dimension of the hypercube with 2d processors.

The processors can be numbered as binary digital numbers as 000, 001, 010, ......


Figure 3.10 shows the hypercube with dimension of 3, it is similar to the 3-D Mesh topology.

FIGURE 3.10 Hypercube topology with dimesion 3.


Following is the hypercube topology with 16 processors and of dimension 4.

FIUGRE 3.11 Hypercube topology with dimension 4.

The distance between processors in Hypercube topology is equal to the number of bit positions in which their processor numbers differ.

The connectivity for a n dimension Hypercube is n, and the diameter is also n.

A Hypercube can be constructed by following recursive procedure:

  1. Create an exact duplicate of the Hypercube with dimension d, including processor numbers.
  2. Create a direct connection between processors with the same number in the original and duplicate.
  3. Append a binary 1 to the left of each processor number in the duplicate, and a binary 0 to left of each processor number in the original.

Figure 3.12 shows the construction for hypercube of dimension 1-3:


FIGURE 3.12 Recursive hypercube construction.

The following chart summarizes the characteristics of each of topologies. The topologies are listed in order of increasing cost and improving performance.:

Topology / Connectivity / Diameter
Line / 2 / n-1
Ring / 2 / n/2
2D-Mesh / 2-4 / 2(n1/2 -1)
Torus / 4 / n1/2
3D-Mesh / 3-6 / 3(n1/3-1)
Hypercube / Log n / Log n

Hypercube Embedding

If the logical communication structure matchsthe physical communication structure of the multicomputer topology, then performance of the program will be enhanced.

For example,

the logical pipeline process structure is mapped onto a physical Line multicomputer topology.

The Ring topology is also equally suitable for executing pipeline algorithms.

A topology X can be embedded in a topology Y if there is some specific mapping of processors in X to processors in Y, such that every communication link in topology X has a corresponding communication link in Y.

Therefore, we can use the snake-like ordering to embed the pipeline in the 2-D Mesh as follows:


FIGURE 3.13 Line embedded in a mesh.

Any of the topologies discussed here can be embedded in a Hypercube, provided that the number of processors is an exact power of two.

Gray Code can be used for embedding a Line topology into a Hypercube.

Gray Code is defined as a sequence of numbers such that each successive number differs from the previous one in only one binary digit.

Here is an example of Gray Code form 0-7:

000 001 011 010 110 111 101 100

In general, the k-bit Gray Code Gk is defined recursively as follows:

G1 is the sequence : 0 1

For all k>1, Gk is the sequence constructed by the following rules:

  1. Construct a new sequence by appending a 0 to the left of all members of Gk-1.
  2. Construct a new sequence by reversing Gk-1 and then appending a 1 to the left of all members of the sequence.
  3. Gk is the concatenation of the sequences defined in step 1 and 2.

For an m by m Mesh, the number of processors is m2, and therefore the dimension of required Hypercube is 2 log m. Figure 3.14 shows the 4 by 4 mesh in a Hypercube.


AFIGURE 3.14 Embedding 4 by 4 mesh in a Hyercube.

A Gray Code sequence p1, p2, ... , pn will define the next Gray Code sequence with twice the length as follows:

0p1, 0p2, ... , 0pn, 1pn-1, ... , 1p1

If this sequence is folded over on itself with an snake-like pattern, the following is the result:

0p1 ---- 0p2 ---- 0p3 ---- . . . ----0pn

|

1p1 ---- 1p2 ---- 1p3 ---- . . . ----1pn

This snake-like Gray Code ordering can also be used to embed any 3-D Mesh into a Hypercube with the same number of processors. Following is an example:


FIGURE 3.15 3-D mesh embedded in Hypercube.

Line, Ring, 2-D Mesh, Torus, and 3-D Mesh topology can all be embedded in the Hypercube topology. The disadvantage of the Hypercube is that the cost of the communication network grows as the logarithm of the number of processors, whereas in all the other topologies, the cost grows linearly with the number of processors.

Section 3.1 Multi-Computer MIMD Architecture