Parallel Computation - Models of Computation: Exploring the Power of Computing - page 299

0111 1111

110 111

10 11

010 011

100 101

00 01 000 001

Figure 7.12 Hypercubes in two, three, and four dimensions.

hypercube is a square, the 3D hypercube is the traditional 3-cube, and the four-dimensional
hypercube consists of two 3-cubes with edges between corresponding pairs of vertices. (See
Fig. 7.12 .) The d -dimensional hypercube is composed of two ( d 1 ) -dimensional hypercubes

in which each vertex in one hypercube has an edge to the corresponding vertex in the other.
The degree of each vertex in a d -dimensional hypercube is d and its diameter is d as well.
While the hypercube is a very useful model for algorithm development, the construction
of hypercube-based networks can be costly due to the high degree of the vertices. For example,
each vertex in a hypercube with 4,096 vertices has degree 12; that is, each vertex is connected to
12 other vertices, and a total of 49,152 connections are necessary among the 4,096 processors.
By contrast, a 2 6

−

2 6 2D mesh has the same number of processors but at most 16,384 wires.
The ratio between the number of wires in a d -dimensional hypercube and a square mesh with
the same number of vertices is d/ 4. This makes it considerably more difficult to realize a
hypercube of high dimensionality than a 2D mesh with a comparable number of vertices.

×

7.6.1 Embedding Arrays in Hypercubes
Given an algorithm designed for an array, we ask whether it can be efficiently realized on
a hypercube network. The answer is positive. We show by induction that if d is even, a
2 d/ 2

2 d/ 2 array can be embedded into a d -dimensional, 2 d -vertex hypercube and if d is odd,
a2 ( d + 1 ) / 2

×

2 ( d− 1 ) / 2 array can be embedded into a d -dimensional hypercube. The base cases
are d = 2and d = 3.

×

00 01 000 001 0000 0001 1001 1000

10 11 010 011 0010 0011 1011 1010

110 111 0110 0111 1111 1110

100 101 0100 0101 1101 1100

Figure 7.13 Mappings of 2 × 2, 4 × 2, and 4 × 4 arrays to two-, three-, and four-dimensional
hypercubes. The binary tuples identify vertices of a hypercube.