PRAM模型

Parallel Random Access Machine 并行随机存储模型，也称为共享存储器的SIMD模型。

• 假定存在一个容量无限大的共享存储器

• 有有限个或无限个功能相同的处理器，均具有简单的算术运算和逻辑判断能力

• 任何时刻各处理器均可以通过共享存储单元相互交换数据

根据读写方式，PRAM模型可以分为以下几类：

1. PRAM-EREW 互斥读互斥写
2. PRAM-CREW 并发读互斥写
3. PRAM-CRCW 并发读并发写（计算能力最强）
   • Common：仅允许写入相同数据
   • Priority：仅允许优先级最高的写
   • Arbitrary：允许任意处理器任意写

例子：

并行加法

int sum = 0
    for (int i = 0; i < N; i++)
        sum += A[i]

PRAM模型的并行加法算法

for j := 1 to log_2(n) do
    for all k in parallel do
        if ((k + 1) mod 2^j = 0) then
			X[k] := X[k - 2^(j - 1)] + X[k]
		fi

如下图所示：

使用Prefix Scan做加法：

prefixScan[0] = A[0];
    for (int i = 1; i < N; i++)
        prefixScan[i] = prefixScan[i - 1] + A[i];

如图：

PRAM模型使用prefixScan做并行加法

for j := 1 to log_2(n) do
    for all k in parallel do 
        if (k >= 2^(j - 1)) then
            X[k] := X[k - 2^(j - 1)] + X[k]
		fi
	od
od

如图：

异步PRAM模型

又称分相（Phase）PRAM

• 由p个处理器构成，每个处理器有其局部存储器、局部时钟、局部程序
• 无全局时钟，各处理器异步执行
• 处理器通过SM进行通讯
• 处理器之间的依赖关系，需要在并行程序中显示地加入同步路障
• 一条指令可以在非确定（无界）但有限的时间内完成

异步PRAM根据读写方式将指令分为以下类型：

1. 全局读：将全局存储单元中的内容读入局部存储单元中
2. 全局写：将局部存储单元中的内容写回全局存储单元中
3. 局部操作：对句存储数据进行读写
4. 同步：计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序

在各全局相中，每个处理器异步地进行其局部计算，每个局部程序中的最后一条指令是同步障指令；各处理器均可以异步地读取和写入全局存储器，但在同一相内不允许两个处理器访问同一单元。

例子：

BSP模型

Bulk Synchronous Parallel 块同步模型，相对的APRAM为轻量同步模型

计算过程

LogP模型

MPC：Massively Parallel Computers，数千个功能强大的处理器/存储器节点，由带宽受限的、延迟可观的互连网络组成。

LogP是一种分布存储的、点到点通信的多处理机模型。

​