next up previous

3.4 Topology     continued...

When a node is not connected to every other node, messages may have to go through intervening nodes to reach their final destination. The diameter of a network is the longest path between any two nodes. Again the ring and fully connected network show two extremes. A ring of n nodes has diameter , but a fully connected network has a fixed diameter (1) no matter how many nodes there are.

Figure 11: Hypercubes.

The diameter of a ring grows as more nodes are added, but the diameter of a fully connected network remains the same. On the other hand, a ring can expand indefinitely without changing the degree, but each time a new node is added to a fully connected network a link has to be added to each existing node. Scalability refers to the increase in the complexity of communication as more nodes are added. In a highly scalable topology more nodes can be added without severely increasing the amount of logic required to implement the topology and without increasing the diameter.

A scalable topology that has been used in several parallel processors is the hypercube, shown in Figure 11. A line connecting two nodes defines a 1-dimensional ``cube.'' A square with four nodes is a 2-dimensional cube, and a 3D cube has eight nodes. This pattern reveals a rule for constructing an n-dimensional cube: begin with an (n-1)-dimensional cube, make an identical copy, and add links from each node in the original to the corresponding node in the copy. Doubling the number of nodes in a hypercube increases the degree by only 1 link per node, and likewise increases the diameter by only 1 path. It is left as an exercise to prove that an n-dimensional hypercube has nodes, diameter n, and degree n.