PRAM 模型

同步机器状态 ​

PRAM 有 $P$ 个处理器、共享随机存取内存公理库数组Array以连续整数下标支持随机访问的有限序列结构。和每处理器局部寄存器。计算按同步轮进行；一轮中每个处理器可读取常数个单元、做常数本地运算并写常数个单元，所有读取得到轮开始时的值，写入在轮末统一生效。

时间是同步轮数 $T_P$，work 常按处理器—轮总操作数计，而不是机械写成 $P{T}_P$：空闲处理器不应被算作有效工作。算法还要给所需处理器数 $P(n)$ 与共享空间。

EREW、CREW 与 CRCW ​

三个标准子模型按同一轮对同一地址的访问限制区分：

• EREW：exclusive read, exclusive write；读与写都不能冲突；
• CREW：concurrent read, exclusive write；允许多人读同一单元，写仍唯一；
• CRCW：concurrent read, concurrent write；读写都可并发，但写冲突必须定义结果。

能力包含关系是 EREW $\subseteq$ CREW $\subseteq$ CRCW。同一算法声称在哪个模型运行，是正确性条件而不只是性能标签；EREW 程序当然能在更强模型运行，反向模拟则可能增加轮数或工作。

CRCW 的写冲突规则 ​

CRCW 不是一个唯一模型。常见规则包括：

• common：只有所有写者写同一值时才合法；
• arbitrary：任取一个写入值胜出，算法不能依赖具体写者；
• priority：处理器编号最小或最高优先级者胜出；
• combining：用 min、max、sum 等固定结合操作合并写值。

例如一轮把所有满足谓词的下标写到同一单元：priority CRCW 可直接得到最小下标；common CRCW 不允许写不同下标；combining-min 可以得到相同结果，但已经把 min 作为硬件原语。省略规则会把模型能力说得过强。

八项求和的 EREW 轨迹 ​

输入 $A[0..8)$ 放在共享数组，另备互不重叠的输出槽。第一轮四个处理器分别读 $(A[0],A[1])$、$(A[2],A[3])$、$(A[4],A[5])$、$(A[6],A[7])$，写四个部分和；第二轮两个处理器读四个不同部分和，写两个结果；第三轮一个处理器写总和。

每一轮任意输入槽只被一个处理器读，输出槽也只有一个写者，所以满足 EREW。总工作为 $7$ 次加法，一般规模为 $\mathrm{\Theta }(n)$；深度为 $\lceil {\log }_{2}n\rceil$，同时活跃处理器逐层减半。把每轮都预留 $n/2$ 个处理器不等于做了 $\mathrm{\Theta }(n\log n)$ 有效工作。

广播体现模型差异 ​

若 $P$ 个处理器都要读取同一值 $x$，CREW 可在一轮完成。EREW 必须先把 $x$ 复制到一棵二叉广播树：第 $i$ 轮已有副本各复制一次，$O(\log P)$ 轮后得到 $P$ 份，并花 $O(P)$ work。

这个差异说明并发读也属于资源。现实缓存可能把只读共享值广播得很快，但一致性流量不是零；PRAM 的 CREW 一轮只是一种抽象。

冲突检测与数组更新 ​

并行写数组时，若每个处理器的目标下标由输入计算，证明“下标互异”才能在 EREW/CREW 合法。若下标可能相同，可先排序、分组或用原子 combining；这些步骤的成本要进入算法界。

同一轮读写同一单元的语义也需固定。标准同步写在轮末可让本轮读见旧值，但 EREW 通常连这种读写并发也禁止；依赖不同约定的 in-place 算法必须用双缓冲消除歧义。

与现实机器的边界 ​

PRAM 假设任意共享地址常数时间、处理器同步且通信拓扑免费，不模拟 cache、bank conflict、NUMA 或内存带宽。它适合比较算法的并行结构，不直接预测 wall-clock speedup。

处理器数若为多项式甚至指数，也必须显式报告；只有低时间没有 work-efficient 结论不够。把 CRCW 的 combining-sum 当现实原子加法，还要考虑热点序列化和数值溢出。

参考资料

• Steven Fortune, James Wyllie, Parallelism in Random Access Machines, STOC, 1978.
• Joseph JáJá, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
• Richard Karp, Vijaya Ramachandran, Parallel Algorithms for Shared-Memory Machines, in Handbook of Theoretical Computer Science, 1990.