In my book of parallel algorithms there is the following pseudo-code for the PRAM model:
procedure PrefixSumPRAM( A, n ):
BEGIN
b := new Array(2*n-1);
b[1] := SumPRAM(A, n); //this will load A with the computation tree and return the sum
for i := 1 to ( log2(n) - 1 ) do
BEGIN
for all procID where (2^i) <= procID <= ((2^(i+1))-1) do in parallel
BEGIN
if odd(procID) then
b[ procID ] := b[ procID/2 ];
else
b[ procID ] := b[ procID/2 ] - a[ procID+1 ];
END
END
END
but...PRAM specify that all processors must execute the same instruction on different data.
So this program is executable only on a CREW PRAM model?
or is executable on an EREW model then the processors with odd ID will execute
b[procID]:=b[procID/2];
when the processors with even id execute a (for example) NOP instruction?
In the PRAM model, there are an unbounded number of processors and a single memory. Although the processors operate in lock-step by executing one instruction per time step, each processor maintains its own state and can therefore execute the program in an arbitrary way according to the control flow.
In a CREW PRAM, two processors can read from the same memory location in the same time step, but only one processor can write to any memory location in one step. In an EREW PRAM, reads can also not occur concurrently.