7.5 PARALLEL SORTING 193The outer for loop has the two parallel blocks nested inside it because at each
pass of this loop, a new processor joins the sort, and the first block primes this
processor with the read of its first value, while the second loop involves it in
the comparing process. At the very end, the values are all written back into
memory.
Figure 7.4(a), (b), and (c) show this process in action for the input list of 15,
18, 13, 12, 17, 11, 19, 16, and 14. We see in Step A that the first value has been
put into memory and will be read into the first processor. In Step B, the sec-
ond value has been put into memory, it is compared with P 1 ’s current value,
and the larger is written to M 2. In Step C, the third value has been put into M 1
so that it can be compared to P 1 ’s current value, while P 2 is reading its first
value out of M 2. In Step D, both P 1 and P 2 can now do a comparison. If you
look at the “odd” steps, you will notice that in each one, a new processor is
about to read its first value. If you look at the “even” steps, you will notice that
all of the processors that are active are making comparisons.A15P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9B18P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9C13 18P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9D121315151815P 1 P 2 P 3 P 4 P 5 P 6 P 7 P 8 P 9
■FIGURE 7.4A
A linear parallel
network sort