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]; 

当与偶数编号的处理器上执行的一个（例如）NOP指令？

Answer 1

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

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