192 PARALLEL ALGORITHMS
each of the processors will keep the smaller value and then pass on the larger of
the values to the next processor in line. This is expressed more formally in the
following algorithm:
for j = 1 to N-1 do
put next value into M 1
Parallel Start
Pj reads Mj into Current
for k = 1 to j-1 do
Pk reads Mk into New
if Current > New then
Pk writes Current to Mk+1
Current = New
else
Pk writes New to Mk+1
end if
end for k
Parallel End
put next value into M 1
Parallel Start
for k = 1 to j do
Pk reads Mk into New
if Current > New then
Pk writes Current to Mk+1
Current = New
else
Pk writes New to Mk+1
end if
end for k
Parallel End
end for j
Parallel Start
for j = 1 to N-1 do
Pj writes Current to Mj
end for j
Parallel End
Before each parallel step, the next value of the list, if there is another, is
placed into the first memory location. At the very start, this value is just read
into the first processor. On succeeding steps, this first processor will then read
the next value into its New variable, compare it to the processor’s Current
value, and then write the larger of the two to the second memory location.