186 PARALLEL ALGORITHMS
is one set of operations that are to be done in parallel and on their completion
another set is to be performed, this will be expressed by placing these into two
separate parallel blocks.■ 7.3.1 Broadcasting Data in a CREW PRAM Model
You will recall that in a CREW model we have the ability for more than one
processor to read from a single memory location at one time. This allows for a
very rapid transfer of the data value to the other processors:
P 1 writes the data value into M 1
Parallel Start
for k = 2 to p do
Pk reads the data value from M 1
end for
Parallel End
This broadcast operation takes two cycles. The first writes the data into
memory and the second has all of the processors read the value. This speed is
only possible because of the concurrent read capability. Now we consider how
the process must differ for a model with exclusive read.■ 7.3.2 Broadcasting Data in an EREW PRAM Model
In an exclusive read model, only one processor can read the data that was writ-
ten by P 1. If we were to just loop through the rest of the processors, we would
have a sequential algorithm and would lose all of the power that we added with
parallelism. If we use the read/process/write cycle of the second processor to
write the data value into a second memory location, on the next pass two
more processors can read the data value. If they then write the data value into
new locations, four processors can read on the next pass. This gives us the fol-
lowing algorithm:
P 1 writes the data value into M 1
procLoc = 1
for j = 1 to lg p do
Parallel Start
for k = procLoc + 1 to 2 * procLoc do
Pk reads Mk-procLoc
Pk writes to Mk
end for k
Parallel End
procLoc = procLoc * 2
end for j