182 PARALLEL ALGORITHMS
intermediate nodes, whereas in the ring network of Fig. 7.2, that message
could now get there by passing through just node 6.
In a mesh network (see Fig. 7.3), the processors are laid out in a two-
dimensional grid, and connections are made to those nodes that are adjacent
either horizontally or vertically. Information now has even more ways to travel
through the network, and the network is more reliable, but this is achieved at
the cost of more complicated wiring.
There are other possible configurations that are not important to our discus-
sion. Those include a tree network, where the processors are connected like a
binary tree, and a hypercube, which is an expansion of a mesh network to
three or more dimensions.■ 7.1.3 Principles for Parallelism Analysis
There are two new concepts that we encounter when dealing with the analysis
of a parallel algorithm: speed up and cost. The speed up of a parallel algorithm
is the factor by which it is faster than an equivalent optimal sequential algo-
rithm. For example, we saw that the optimal time for a sorting algorithm was
O(N lg N). If we have a parallel sorting algorithm that is of order O(N), we
have achieved a speed up of O(lgN).12546 3
■FIGURE 7.2
A ring network
configuration852741963■FIGURE 7.3
A mesh network