并行计算模型

引言

所谓计算模型实际上是软件和硬件之间的一种桥梁，使用它能够设计、分析算法，在其上高级语言能被有效的编译且能够用硬件来实现。 串行计算时，典型的，被公认的，通用的计算模型是冯▪诺依曼机。但是并行计算时，没有一个类似冯▪诺依曼机被公认的，通用的计算模型。 现在流行的并行计算模型要么过于简单、抽象（如 PRAM），要么过于专用（如 互联网络模型）。在这里，我们先介绍一些常用的并行计算模型：PRAM模型，异步PRAM模型，BSP模型和LogP模型。

PRAM模型

基本概念

由Fortune和Wyllie 1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。

结构图

分类

• PRAM-CRCW并发读并发写
  • CPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据
  • PPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入
  • APRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入
• PRAM-CREW并发读互斥写
• PRAM-EREW互斥读互斥写

计算能力比较

PRAM-CRCW是最强的计算模型，PRAM-EREW可logp倍模拟PRAM-CREW和PRAM-CRCW。

优缺点

优点：适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。 缺点：不适合MIMD并行机，忽略了SM的竞争、通讯延迟等因素

异步PRAM模型

基本概念

又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步路障。

指令类型

• 全局读：将全局存储单元中的内容读入局存单元中
• 局部操作：对局存中的数执行操作，其结果存入局存中。
• 全局写：将局存单元中内容写入全局存储单元中。
• 同步：同步是计算中的一个逻辑点，在该点各个处理器均需等待别的处理器操作完成后才能继续执行其局部程序。

计算过程

计算时间

优缺点

易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。

BSP模型

基本概念

由Valiant(1990)提出的，“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。

模型参数

• p：处理器数(带有存储器)
• l：同步障时间(Barrier synchronization time)
• g：带宽因子(time steps/packet)=1/bandwidth)

计算过程

由若干超级步组成，每个超级步计算模式如下图所示：

优缺点

强调了计算和通讯的分离，提供了一个编程环境，易于程序复杂性分析。但需要显式同步机制，限制至多h条消息的传递等。

LogP模型

基本概念

由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。

模型参数

• L：network latency
• o：communication overhead
• g：gap=1/bandwidth
• P：#processors 注：L和g反映了通讯网络的容量

优缺点

捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。

BSP模型 vs LogP模型

• BSP -> LogP：BSP块同步BSP子集同步BSP进程对同步＝LogP
• BSP可以常数因子模拟LogP，LogP可以对数因子模拟BSP
• BSP＝LogP+Barriers－Overhead
• BSP提供了更方便的程设环境，LogP更好地利用了机器资源
• BSP似乎更简单、方便和符合结构化编程

参考

[并行计算——结构·算法·编程].陈国良