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

(a) (b)

Figure 7.5 Completely balanced (a) and unbalanced (b) trees.

a message between processors. Its bisection width is a measure of the amount of information
that must be transmitted in the network for processors to communicate with their neighbors.
A large variety of networks have been investigated. The graph of a tree network is a tree.
Many simple tasks, such as computing sums and broadcasting (sending a message from one
processor to all other processors), can be done on tree networks. Trees are also naturally suited
to many recursive computations that are characterized by divide-and-conquer strategies ,in
which a problem is divided into a number of like problems of similar size to yield small results
that can be combined to produce a solution to the original problem. Trees can be completely
balanced or unbalanced. (See Fig. 7.5 .) Balanced trees of fixed degree have a root and bounded
number of edges associated with each vertex. The diameter of such trees is logarithmic in
the number of vertices. Unbalanced trees can have a diameter that is linear in the number of
vertices.
A mesh is a regular graph (see Section 7.5 ) in which each vertex has the same degree except
possibly for vertices on its boundary. Meshes are well suited to matrix operations and can be
used for a large variety of other problems as well. If, as some believe, speed-of-light limitations
will be an important consideration in constructing fast computers in the future [ 43 ], the one-,
two-, and three-dimensional mesh may very well become the computer organization of choice.
The diameter of a mesh of dimension d with n vertices is proportional to n 1 /d .Itisnotas
small as the diameter of a tree but acceptable for tasks for which the cost of communication
can be amortized over the cost of computation.
The hypercube (see Section 7.6 ) is a graph that has one vertex at each corner of a mul-
tidimensional cube. It is an important conceptual model because it has low (logarithmic)
diameter, large bisection width, and a connectivity for which it is easy to construct efficient
parallel algorithms for a large variety of problems. While the hypercube and the tree have sim-
ilar diameters, the superior connectivity of the hypercube leads to algorithms whose running
time is generally smaller than on trees. Fortunately, many hypercube-based algorithms can be
efficiently translated into algorithms for other network graphs, such as meshes.
We demonstrate the utility of each of the above models by providing algorithms that are
naturally suited to them. For example, linear arrays are good at performing matrix-vector
multiplications and sorting with bubble sort. Two-dimensional meshes are good at matrix-
matrix multiplication, and can also be used to sort in much less time than linear arrays. The
hypercube network is very good at solving a variety of problems quickly but is much more
expensive to realize than linear or two-dimensional meshes because each processor is connected
to many more other processors.