PRAM模型

概述

PRAM模型（Parallel Random Access Machine）是并行计算的经典理论模型，由多个处理器共享全局内存，各处理器可同时读取或写入共享内存单元。根据对内存访问冲突的不同处理策略，PRAM 分为 EREW（互斥读写）、CREW（并发读互斥写）、CRCW（并发读写）等变体。PRAM 是并行算法设计与分析的基础模型。

定义

形式化定义

一个 PRAM（Parallel Random Access Machine）由以下组件构成：

• $p$ 个处理器 $P_1,P_2,\dots ,P_p$：每个处理器可执行算术和逻辑运算
• 共享全局内存：由 $M$ 个可寻址单元组成，所有处理器均可访问
• 同步执行：所有处理器在每个时钟周期同步执行，共享统一时钟
• 通信方式：处理器之间通过读写共享内存单元进行通信

在每个时钟周期中，每个处理器可以：

1. 从共享内存读取一个字
2. 执行一次局部计算
3. 向共享内存写入一个字

PRAM 的四种变体

根据对共享内存并发访问冲突的处理策略，PRAM 分为以下变体：

变体	全称	并发读	并发写	说明
EREW	Exclusive-Read Exclusive-Write	禁止	禁止	最严格，同一内存单元每周期只能被一个处理器访问
CREW	Concurrent-Read Exclusive-Write	允许	禁止	允许同时读，但写必须互斥
CRCW	Concurrent-Read Concurrent-Write	允许	允许	允许同时读写，需定义冲突解决策略
ERCW	Exclusive-Read Concurrent-Write	禁止	允许	较少使用

CRCW 的冲突解决策略：

• Common CRCW：所有写入相同值时允许，否则报错
• Arbitrary CRCW：任意选择一个写入值生效
• Priority CRCW：编号最小的处理器写入值生效
• Combining CRCW：将所有写入值按某种运算（如求和、取最大值）合并

核心性质

性质	描述
计算能力排序	EREW $\subseteq$ CREW $\subseteq$ CRCW，更宽松的模型可模拟更严格的模型
多项式加速	许多问题在 PRAM 上可实现从 $O(n)$ 到 $O(\log n)$ 的加速
同步假设	所有处理器同步执行，忽略实际系统中的通信延迟和同步开销
理想化模型	不考虑内存竞争、缓存一致性等实际硬件问题

变体间的模拟关系：

• CREW 可用 EREW 模拟，代价为 $O(\log p)$ 倍时间（通过广播树实现并发读）
• CRCW 可用 CREW 模拟，代价为 $O(\log p)$ 倍时间（通过树结构合并并发写）
• 因此 EREW 与 CRCW 之间最多相差 $O({\log }^{2}p)$ 倍时间

应用场景

PRAM 模型是并行算法设计与分析的基础，经典应用包括：

• 并行前缀和：$n$ 个元素的前缀和在 CREW PRAM 上可在 $O(\log n)$ 时间内完成（使用 $n$ 个处理器）
• 并行排序：基于比较的排序在 CRCW PRAM 上可在 $O(\log n)$ 时间内完成
• 并行矩阵运算：两个 $n\times n$ 矩阵乘法可在 $O(\log n)$ 时间内完成（使用 $O(n^3)$ 个处理器）
• 并行图算法：BFS、连通分量等图算法的并行化分析
• 计算复杂性理论：NC 类（Nick’s Class）的定义基于 PRAM 上的多项式处理器对数时间算法

参见

• 并行计算模型 — PRAM 是并行计算模型的一种
• Brent定理 — 有限处理器下并行执行时间的上界
• BLAS — 实际并行线性代数计算的标准接口
• 缓存优化 — 实际并行系统中缓存层次结构的影响