0

在我的并行算法书中，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 指令时？

4

1 回答 1

1

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

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

于 2014-06-04T11:33:57.857 回答