algorithm - PRAM if-then-else CREW/EREW

Question

在我的并行算法书中，有以下 PRAM 模型的伪代码:

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

但是...PRAM 指定所有处理器必须对不同的数据执行相同的指令。

所以这个程序只能在 CREW PRAM 模型上执行？

或者在 EREW 模型上可执行，则 ID 为奇数的处理器将执行

b[procID]:=b[procID/2];

当具有偶数 id 的处理器执行(例如)NOP 指令时？

Answer 1

在 PRAM 模型中，有无限数量的处理器和单个内存。尽管处理器通过每个时间步执行一条指令以锁步方式运行，但每个处理器都保持自己的状态，因此可以根据控制流以任意方式执行程序。

在 CREW PRAM 中，两个处理器可以在同一时间步长中从相同的内存位置读取数据，但只有一个处理器可以在一个步骤中写入任何内存位置。在 EREW PRAM 中，读取也不能同时发生。