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

Figure 7.6 A crossbar connection network. Any two processors can be connected.
In designing parallel algorithms it is often helpful to devise an algorithm for a particular
parallel machine model, such as a hypercube, and then map the hypercube and the algo-
rithm with it to the model of the machine on which it will be executed. In doing this, the
question arises of how efficiently one graph can be embedded into another. This is the graph-
embedding problem. We provide an introduction to this important question by discussing
embeddings of one type of machine into another.
A connection network is a network computer in which all vertices except for peripheral
vertices are used to route messages. The peripheral vertices are the computers that are con-
nected by the network. One of the simplest such networks is the crossbar network ,inwhich
a row of processors is connected to a column of processors via a two-dimensional array of
switches. (See Fig. 7.6 .) The crossbar switch with 2 n computational processors has n 2 routing
vertices. The butterfly network (see Fig. 7.15 ) provides a connectivity similar to that of the
crossbar but with many fewer routing vertices. However, not all permutations of the inputs to
a butterfly can be mapped to its outputs. For this purpose the Benes network (see Fig. 7.20 )
is better suited. It consists of two butterfly graphs with the outputs of one graph connected to
the outputs of the second and the order of edges of the second reversed. Many other permuta-
tion networks exist. Designers of connection networks are very concerned with the variety of
connections that can be made among computational processors, the time to make these con-
nections, and the number of vertices in the network for the given number of computational
processors. (See Section 7.8 .)
7.4 The Performance of Parallel Algorithms
We now examine measures of performance of parallel algorithms. Of these, computation time
is the most important. Since parallel computation time T p is a function of p ,thenumberof
processors used for a computation, we seek a relationship among p , T p ,andothermeasuresof
the complexity of a problem.
Given a p -processor parallel machine that executes T p steps, in the spirit of Chapter 3 ,we
can construct a circuit to simulate it. Its size is proportional to pT p , which plays the role of