2.5.3.4CubeConnectedCycles
A cube-connected cycles topology is shown in Figure 2.18. This topology is easily formed from
the hypercube topology by replacing each hypercube node with a cycle of nodes. As a result, the
new topology has nodes, each of which, has degree 3. This has the look and feel of a hypercube
yet without the high degree. The cube-connected cycles topology has nlog n nodes.

Figure 2.18 Cube-Connected Cycles
2.6 The Hypercube Topology
This section presents algorithms and issues related to the hypercube topology. The hypercube is
important due to its flexibility to efficiently simulate topologies of a similar size.
2.6.1Definitions
Processors in a hypercube are numbered 0, , n - 1. The dimension, d, of a hypercube, is given
as

where at this point it is assumed that n is a power of 2. A processor, x, in a hypercube has a
representation of

For a simple example of the enumeration scheme see Section 2.5.3.3 on page 75. The distance, d
(x, y), between two nodes x and y in a hypercube is given as

The distance between two nodes is the length of the shortest path connecting the nodes. Two
processors, x and y are neighbors if d (x, y) = 1. The hypercubes of dimension two and three are
shown in Figure 2.19.
2.6.2MessagePassing
A common requirement of a parallel processing topology is the ability to support broadcast and
message passing algorithms between processors. A broadcast operation is an operation which
supports a single processor communicating information to all other processors. A message
passing algorithm supports a single message transfer from one processor to the next. In all cases
the messages are required to traverse the edges of the topology.
To illustrate message passing consider the case of determining the path to send a message from
processor 0 to processor 7 in a 3-dimensional hypercube as shown in Figure 2.19. If the message

000 111 111 001
001 111 110 011
011 111 100111
The message passing algorithm still works under certain circumstances even when the hypercube
has nodes that are faulty. This is discussed in the next section.
2.6.3EfficientHypercubes
This section presents the analysis of the class of hypercubes for which the message passing
routines of the previous section are valid. Examples are presented in detail for an 8-node
hypercube.
2.6.3.1TransitiveClosure
Definition 2.23
The adjacency matrix, A, of a graph, G, is the matrix with elements a
ij
such that a
ij
= 1 implies
there is an edge from i to j. If there is no edge then a
ij
= 0.

The adjacency matrix, A, of the transitive closure of the 8-node hypercube is simply the matrix

For a hypercube with all functional nodes every processor is reachable.

Previous TableofContents Next

Copyright © CRC Press LLC

Algorithms and Data Structures in C++
by Alan Parker

A tree is an acyclic connected graph.

Examples of trees are shown in Figure 2.10.
Definition 2.18
An edge, e, in a connected graph, G = (V, E), is a bridge if G′ = (V, E′) is disconnected where Figure 2.10
Trees

If the edge, e, is removed, the graph, G, is divided into two separate connected graphs. Notice
that every edge in a tree is a bridge.
Definition 2.19
A planar graph is a graph that can be drawn in the plane without any edges intersecting.

An example of a planar graph is shown in Figure 2.11. Notice that it is possible to draw the
graph in the plane with edges that cross although it is still planar.
Definition 2.20
The transitive closure of a directed graph, G = (V
1
, E
1
) is a graph, H = (V
2
, E
2
), such that, Figure 2.11 Planar Graph