并行计算模型是指从并行算法的设计和分析出发，将各种并行计算机的基本特征抽象出来的计算模型。这些模型不仅为并行计算提供了硬件和软件界面，还使得并行系统硬件设计者和软件设计者能够开发出对并行性的支持机制，从而提升系统的性能。
PRAM模型
类型
PRAM（Parallel Random Access Machine，随机存取并行机器）模型，也被称为共享存储的SIMD模型，是从串行的RAM模型直接发展而来的一种抽象的并行计算模型。在这个模型中，有一个容量无限大的共享存储器，有限个或无限个功能相同的处理器，它们都能进行简单的算术运算和逻辑判断，并能在任何时候通过共享存储单元互相交流数据。根据处理器对共享存储单元同时读、同时写的限制，PRAM模型可分为以下类型：
独占读写（EREW）的PRAM模型
不允许同时读和同时写，简称PRAM-EREW。
同时读独占写（CREW）的PRAM模型
允许同时读但不允许同时写，简称PRAM-CREW。
同时读写（CRCW）的PRAM模型
允许同时读和同时写，简称PRAM-CRCW。
共同CRCW（CPRAM-CRCW）模型
只允许所有处理器同时写相同的数。
优先CRCW（PPRAM-CRCW）模型
只允许最优先的处理器先写。
随意CRCW（APRAM-CRCW）模型
允许任意处理器自由写。
求和CRCW（SPRAM-CRCW）模型
往存储器中写的实际内容是所有处理器写的数的和。
在这些模型中，PRAM-EREW是最弱的功能模型，而PRAM-CRCW则是最强的功能模型。具体地说，一个具有时间复杂度为TCREW或TCRCW的算法，在PRAM-EREW模型上要花费logp倍的时间去模拟实现。
PRAM模型的优点
PRAM模型特别适合于并行算法的表达、分析和比较，使用简单，许多关于并行计算机的底层细节，如处理器间通信、存储系统管理和进程同步都被隐含在模型中。此外，该模型易于设计算法，并且经过适当修改后，可以在不同的并行计算机系统上运行。根据需要，还可以在PRAM模型中添加诸如同步和通信等内容。
PRAM模型的缺点
PRAM模型有一些局限性和挑战，其中包括：
1. 模型中使用了一个全局共享存储器，且局存容量较小，不足以描述分布主存多处理机的性能瓶颈。此外，共享单一存储器的假定，显然不适合于分布存储结构的MIMD机器。
2. PRAM模型是同步的，这意味着所有的指令都按锁步方式进行操作。尽管用户感觉不到同步的存在，但它确实会消耗时间，并且无法反映现实中很多系统的异步性。
3. PRAM模型假设每个处理器均可在单位时间内访问共享存储器的任一单元，这一假设忽略了实际存在的细节，如资源竞争和有限带宽，这是不现实的。
4. PRAM模型假设处理机有限或无限，对并行任务的增大无开销。
5. 未能描述所线程技术和流水线预取技术，这两种技术是当今并行体系结构中最常用的技术。
BSP模型
特点
BSP模型（Bulk Synchronous Parallel model）是一种分布存储的MIMD计算模型，其特点包括：
1. 将处理器和路由器分开，强调了计算任务和通信任务的分离，而路由器仅负责点到点的消息传递，不提供组合、复制和广播等功能。这种方法既掩盖了具体的互连网络拓扑，又简化了通信协议。
2. 采用障碍同步的方式，以硬件实现的全局同步是在可控的粗粒度级别，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员无需承担过多的负担。
3. 分析BSP模型的性能时，假设局部操作可以在一个时间步内完成，而在每个超级步中，一个处理器最多发送或接收h条消息（称为h-relation）。假定s是传输建立时间，所以传送h条消息的时间为gh+s。如果，则L至少应大于等于gh。很明显，硬件可以将L设置得尽可能小（例如使用流水线或大的通信带宽使g尽可能小），而软件可以设置L的上限（因为L越大，并行粒度越大）。在实际使用中，g可以定义为每秒处理器所能完成的局部计算数目与每秒路由器所能传输的数据量之比。如果能够适当地平衡计算和通信，则BSP模型在可编程性方面具有显著的优势，而直接在BSP模型上执行算法（而不是自动编译它们），这一优势将随着g的增加而变得更加明显。
4. 为PRAM模型所设计的算法，都可以采用在每个BSP处理器上模拟一些PRAM处理器的方法来实现。理论分析表明，这种模拟在常数因子范围内是最佳的，只要并行松弛度（Parallel Slackness），即每个BSP处理器所能模拟的PRAM处理器的数量足够大。在并发情况下，多个处理器同时访问分布式的存储器可能会引发一些问题，但使用哈希方法可以使程序均匀地访问分布式存储器。在PRAM-EREW情况下，如果所选择的哈希函数足够有效，则L至少是对数级别的，因此模拟可以达到最佳状态。这是因为我们希望在p个物理处理器的BSP模型上，模拟个虚拟处理器，可将个虚拟处理器分配给每个物理处理器。在一个超级步内，v次存取请求可以均匀分布，每个处理器大约v/p次，因此计算机执行本次超级步的最佳时间为O(v/p)，且概率是高的。同样，在v个处理器的PRAM-CRCW模型中，能够在p个处理器（如果），和的BSP模型上用O(v/p)的时间也可以达到最佳模拟。
评价
BSP模型尝试为软件和硬件之间搭建一座类似于冯·诺依曼机的桥梁，Valiant论证了BSP模型可以起到这样的作用，因此BSP模型也常被称为桥模型。一般来说，分布存储的MIMD模型的可编程性较差，但在BSP模型中，如果计算和通信可以适当地平衡（例如g=1），则它在可编程方面展现出显著的优点。在BSP模型上，已经直接实现了若干重要算法（如矩阵乘法、并行前缀运算、快速傅里叶变换和排序等），这些算法都避免了自动存储管理的额外开销。BSP模型可以在超立方体网络和光交叉开关互连技术上有效地实现，显示出了该模型与特定技术实现无关，只要路由器具有一定的通信吞吐率。然而，BSP模型也有一些局限性，包括：
1. 超级步的长度必须能够充分适应任意的h-relation，这是人们不太喜欢的一点。
2. 在BSP模型中，在超级步开始发送的消息，即使网络延迟时间比超级步的长度短，它也只能在下一个超级步才能使用。
3. BSP模型中的全局障碍同步假定是用特殊硬件支持的，这在很多并行机中可能没有相应的硬件。
4. Valiant提出的编程模拟环境，在算法模拟时的常数可能并不很小，如果考虑到进程间的切换（可能不仅要设置寄存器，而且还可能涉及部分高速缓存），则这个常数可能很大。
LogP模型
描述
LogP模型（Logarithmic in the Product of Parameters model）是由D.Culer等人在1993年提出的，旨在捕捉分布式存储计算机的特点，并充分说明互联网络的性能特性，而不涉及具体的网络结构，也不假定算法必须用现实的消息传递操作进行描述。LogP模型是一种分布存储的、点到点通信的多处理机模型，其中通信网络由四个主要参数描述：
1. L（Latency）表示源处理机与目标处理机进行消息（一个或几个字）通信所需的等待或延迟时间的上限，表示网络中消息的延迟。
2. o（Overhead）表示处理机准备发送或接收每个消息的时间开销（包括操作系统核心开销和网络软件开销），在此期间处理机不能执行其他操作。
3. g（Gap）表示一台处理机连续两次发送或接收消息时的最小时间间隔，其倒数即微处理机的通信带宽。
4. P（Processor）处理机/存储器模块数量。
假定一个周期完成一次局部操作，并定义为一个时间单位，那么，L，o和g都可以表示成处理器周期的整数倍。
特点
LogP模型的特点包括：
1. 抓住了网络与处理机之间的性能瓶颈。g反映了通信带宽，单位时间内最多有L/g个消息能进行处理机间传送。
2. 处理机之间异步工作，并通过处理机间的消息传送来完成同步。
3. 对多线程技术有所体现。每个物理处理机可以模拟多个虚拟处理机（VP），当某个VP有访问请求时，计算不会终止，但VP的个数受限于通信带宽和上下文交换的开销。VP受限于网络容量，至多有L/g个VP。
4. 消息延迟不确定，但延迟不大于L。消息经历的等待时间是不可预测的，但在没有阻塞的情况下，最大不超过L。
5. LogP模型鼓励编程人员采用一些良好的策略，如作业分配、计算与通信重叠以及平衡的通信模式等。
6. 可以估算算法的实际运行时间。
不足之处
LogP模型也有其局限性，主要包括：
1. 对网络中的通信模式描述不够深入。如重发消息可能占满带宽、中间路由器缓存饱和等未加描述。
2. LogP模型主要适用于消息传递算法设计，对于共享存储模式，则简单地认为远地读操作相当于两次消息传递，未考虑流水线预取技术、Cache引起的数据不一致性以及Cache命中率对计算的影响。
3. 未考虑多线程技术的上下文开销。
4. LogP模型假设用点对点消息路由器进行通信，这增加了编程者考虑路由器上相关通信操作的负担。
C3模型
C3模型（Communication Complexity model）由J.F.JaJa等人在1996年提出，这是一种块分布存储模型（Block Distributed Model），也是共享存储编程模式与基于消息传递的分布存储系统之间的桥梁模型。C3模型的主要参数包括：
1. P 处理器个数。
2. τ 处理机从发出访问请求到得到远程数据的最大延迟时间（包括准备请求时间、请求包在网络中路由的时间、目的处理机接收请求的时间以及将包中M个连续字返回给原处理机的时间）。
3. M 局部存储器中连续的M个字。
4. σ 处理机发送数据到网络或从网络接收数据的时间。
特点
C3模型的特点包括：
1. 使用Cl和Cp来衡量网络的拥挤对算法性能的影响。
2. 考虑了不同路由和不同发送或接收原语对通信的影响。
3. 不需要用户指定调度细节，即可评估超步的时间复杂性。
4. 类似于H-PRAM模型的层次结构，C3模型为编程者提供了K级路由算法的思路，即将系统划分为K级子系统，各级子系统的操作相互独立，用超步代替了H-PRAM中的Sub PRAM进行分割。
不足之处
C3模型的不足之处包括：
1. Cl度量的前提假设为同一通信对中的两个处理机要分别位于网络划分后的不同子网络内。
2. 模型假设了网络带宽等于处理机带宽，这影响了正确描述可扩展系统。
3. 在K级算法中，处理机间的顺序可以由多种排列，但C3模型不能区分不同排列的难易程度。
BDM模型
BDM模型（Block Distributed Model）由J.F.JaJa等人在1996年提出，这是一种块分布存储模型，也是共享存储编程模式与基于消息传递的分布存储系统之间的桥梁模型。BDM模型的主要参数包括：
1. P 处理器个数。
2. τ 处理机从发出访问请求到得到远程数据的最大延迟时间（包括准备请求时间、请求包在网络中路由的时间、目的处理机接收请求的时间以及将包中M个连续字返回给原处理机的时间）。
3. M 局部存储器中连续的M个字。
4. σ 处理机发送数据到网络或从网络接收数据的时间。
特点
BDM模型的特点包括：
1. 使用M反映出空间局部性特点，提供了一种评价共享主存算法的性能方法，度量了因远程访问引起的处理间的通信。
2. BDM认可流水线技术。某个处理机的K次预取所需的时间为τ+KMσ （否则为K(τ+Mσ))。
3. 可编程型好。
4. 考虑了共享主存中的存储竞争问题。
5. 可以用来分析网络路由情况。
不足
BDM模型的不足之处包括：
1. 假设初始数据置于局存中，对于共享主存程序的编程者来说，需要额外增加数据移动操作。
2. 未考虑网络中影响延迟的因素（如处理机的本地性、网络重拥挤等）。
3. 未考虑系统开销。
参考资料 >
并行计算模型.CSDN博客.2024-10-29
一篇文章搞懂并行计算模型.一篇文章搞懂并行计算模型.2024-10-29