所谓计算模型实际上是软件和硬件之间的一种桥梁,使用它能够设计、分析算法,在其上高级语言能被有效的编译且能够用硬件来实现。
串行计算时,典型的,被公认的,通用的计算模型是冯▪诺依曼机。但是并行计算时,没有一个类似冯▪诺依曼机被公认的,通用的计算模型。
现在流行的并行计算模型要么过于简单、抽象(如 PRAM
),要么过于专用(如 互联网络模型)。在这里,我们先介绍一些常用的并行计算模型:PRAM
模型,异步PRAM
模型,BSP
模型和LogP
模型。
由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的竞争、通讯延迟等因素
又称分相(Phase
)PRAM
或MIMD-SM
。每个处理器有其局部存储器、局部时钟、局部程序;无全局时钟,各处理器异步执行;处理器通过SM进行通讯;处理器间依赖关系,需在并行程序中显式地加入同步路障。
易编程和分析算法的复杂度,但与现实相差较远,其上并行算法非常有限,也不适合MIMD-DM
模型。
由Valiant(1990)提出的,“块”同步模型,是一种异步MIMD-DM
模型,支持消息传递系统,块内异步并行,块间显式同步。
由若干超级步组成,每个超级步计算模式如下图所示:
强调了计算和通讯的分离,提供了一个编程环境,易于程序复杂性分析。但需要显式同步机制,限制至多h条消息的传递等。
由Culler(1993)年提出的,是一种分布存储的、点到点通讯的多处理机模型,其中通讯由一组参数描述,实行隐式同步。
捕捉了MPC的通讯瓶颈,隐藏了并行机的网络拓扑、路由、协议,可以应用到共享存储、消息传递、数据并行的编程模型中;但难以进行算法描述、设计和分析。
[并行计算——结构·算法·编程].陈国良