问题的基本求解过程
1）建立实际应用问题的理论模型（物理模型或数学模型）；
2）理论模型的并行算法设计（在并行机上为该模型设计高效算法）；
3）算法程序的实现
并行算法研究的目的：探索在并行计算机上解决应用问题的高效算法。
并行计算机模型
冯-诺依曼计算机是一个理想的通用串行计算机模型，但是对并行计算来说，到目前为止，没有一个类似的通用并行计算模型。在过去几十年中，人们针对不同类型的并行计算机提出了多种并行计算模型： 1) PRAM模型；2 )异步APRAM模型；3) BSP模型；4) logP模型。
并行计算模型：从并行算法的设计和分析出发，将各种并行计算机（至少是某一类）的基本特征抽象出来，形成一个抽象的并行计算模型。
并行计算模型为并行计算提供了硬件和软件系统的设计界面，在该界面的约定下，并行系统的硬件和软件设计者可以开发硬件结构和软件（算法、操作系统、语音等）。并行计算模型只是并行计算的理论模型，无须估计实现细节和物理约束条件；并行计算模型不同于某一类并行机。
并行计算模型的作用
1）是并行算法实现的基础
2）给并行算法设计与分析提供了一个简单方便的框架
3）使并行算法的设计具有一定的生命力
我们知道，并行算法的设计依赖于并行计算模型，由于并行计算模型与具体并行系统的差异性，一个并行算法在不同计算系统上运行的效率是不同的。因此，研究并行计算模型在具体并行计算系统上实现的规律对开发高性能的并行计算软件具有重要意义。
一、PRAM模型
（Parallel Random Access Machine并行随机存取机器）
基本概念
由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。（SIMD——单指令流，多数据流；SM——共享内存）
结构图
（p表示处理器，LM表示局地内存）
PRAM（Parallel Random Access Machine）模型是单指令流多数据流（SIMD）并行机中的一种具有共享存储的模型。它假设有一个无限大容量的共享存储器，并且有多个功能相同的处理器，在任意时刻处理器可以访问共享存储单元。
根据是否可以同时读写，它又分为以下三类：
PRAM-EREW，PRAM-CREW，PRAM-CRCW（其中C代表Cuncurrent，意为允许并发操作，E-代表Exclusive，意味排斥并发操作）。在PRAM中有一个同步时钟，所有的操作都是同步进行的。
PRAM模型优缺点
优点
适合并行算法表示和复杂性分析，易于使用，隐藏了并行机的通讯、同步等细节。
缺点
不适合MIMD（多指令流，多数据流）并行机，忽略了SM的竞争、通讯延迟等因素
不现实，首先容量无限大的存储器是不存在的，而且由于各方面的原因，全局访存通常要比预想的慢。其次，他忽略了通信带宽的影响。
共享存储模型-SM模型
共享存储模型特别适合于并行算法的表达、分析和比较；使用简单，很多诸如处理器间通信、存储管理和进程同步等并行机的低级细节均隐含于模型中；易于设计算法和稍加修改便可运行于不同的并行机上。由于本模型是一个同步模型，意味着指令按照锁步方式执行，共享单一存储器的假定，显然不适合于分布存储的异步 ＭＩＭＤ机器。
二、异步APRAM(Asynchrinize)模型
基本概念
又称分相（Phase）PRAM或MIMD-SM。每个处理器有其局部存储器、局部时钟、局部程序；无全局时钟，各处理器异步执行；处理器通过SM进行通讯；处理器间依赖关系，需在并行程序中显式地加入同步(路)障(Synchronization Barrier)。
指令类型
(1)全局读 (3)全局写
(2)局部操作 (4)同步
APRAM模型中的指令类型：
全局读：将全局存储单元中的内容读入局存单元中。
局部操作：对局存中的数执行操作，其结果存入局存中。
全局写：将局存单元中的内容写入全局存储单元中。
同步：是计算中的一个逻辑点，在该点各处理器均需等待别的处理器到达后才能继续执行其局部程序。
计算过程
由同步障分开的全局相组成
(处理器1到处理器p通过分项来实现各个操作，在每一个分项中以读（read）开始，以写（write）结束；*表示局部操作，局部操作可以是不同的，也就是异步实现；当分项中完成最后一个写的操作，把该写操作当成一个同步障；然后执行下一个分项中的内容.)
APRAM模型中的计算：
计算由一系列用同步障分开的全局项所组成。
如上图，在各全局相内，每个处理器异步地运行其局部程序。
每个局部程序中最后一条指令是一条同步障指令。
各处理器均可异步地读取和写入全局存储器，但在同一相内不允许两个处理器访问同一单元。
优缺点
易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。
三、LogP模型
基本概念
由Culler(1993)年提出的，是一种分布存储的、点到点通讯的多处理机模型，其中通讯由一组参数描述，实行隐式同步。
该计算模型能够作为设计和分析快速、可移植并行算法的基础，并使得这样设计出的并行算法在现在和未来大部分并行计算机上能高效实现。
【发送信息的照片，来源于网络】
（如果一个用户A给一个用户B发送信息，A编辑完之后将信息发送给B，B在接受的时候，实际上信息传递有一个延迟，并不是A发送的时候，B就能够立刻接受到；另外当A编辑的信息比较长的时候，会把信息合成多段去发送，在B接受信息的时候，每段信息都有一段很短的时间间隔。）
LogP模型中的参数
L（Latency）：源处理机与目标处理机之间进行消息通信（一个或几个字）所需等待的延迟时间的上限。
o（overhead）：处理机用于发送或者接受每个消息的时间开销。
g（gap）：一台处理机连续进行消息发送或接收时的最小时间间隔。
P（Processor）：处理机或处理模块的数量
LogP模型是异步的，假设所有消息都很短。
优缺点
捕捉了MPC的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。
四、BSP模型
BSP模型以三个参数描述分布式存储的多计算模型。
三个参数：
处理机（P）
处理机之间的点对点通信的选路器（g）
执行以时间间隔L为周期的路障同步器（L）
在BSP模型中，计算由一系列用全局同步器分开的周期为L的超级步组成。
LogP模型和BSP模型在效率上是等效的。
BSP vs LogP
BSP
LogP：BSP块同步BSP子集同步BSP进程对同步＝LogP
BSP可以常数因子模拟LogP，LogP可以对数因子模拟BSP
BSP＝LogP+Barriers－Overhead
BSP提供了更方便的程设环境，LogP更好地利用了机器资源
BSP似乎更简单、方便和符合结构化编程
转载：https://blog.csdn.net/qq_44762986/article/details/104891501