目录
PRAM模型（Parallel Random Access Machine，随机存取并行机器）
一、并行计算概念
基本思想：用多个处理器来协同求解同一问题。
并行计算系统形式：含有多个处理器的超级计算机or以某种方式互连的若干台独立计算构成的集群。
二、Flynn分类法
概念：Michael.J.Flynn提出的根据指令流/数据流的多倍性特性对计算机系统进行分类的方法。
- 指令流：机器执行的指令序列
- 数据流：由指令流调用的数据序列，包括输入数据和中间结果
4类：SISD，SIMD，MISD，MIMD
SISD 单指令流单数据流
传统的顺序执行的单处理器计算机
SIMD 单指令流多数据流
同时用相同的指令 对不同的数据进行操作。以并行处理机（阵列处理机）为代表，包括多个重复的处理单元。
对于数据并行类问题能达到很高的处理速度。
MISD
n个处理单元，按n条不同指令的要求对同一数据流进行不同的处理。
理论模型，没有投入实际应用。
MIMD
同时有多条指令对不同的数据进行操作。
每个处理机在各自唯一的数据流上执行各自的指令流。
MIMD分类
- 共享内存MIMD（SMP）
- 分布式共享内存MIMD（DSM）
- 分布式内存MIMD（MPP、COW）
- SPMD Single-Program 同时执行相同的程序对不同数据操作。
- MPMD Muitiple-Program 同时有多个程序对不同的数据进行操作。
指令：计算机能实现的基本操作
程序：为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合；一系列按一定顺序排列的指令。
三、并行算法
1. 定义和概念
并行算法：
一些可同时执行的进程的集合，这些进程互相作用协调动作从而达到给定问题的求解。
进程间通信：
-
同一台处理机中，读/写OS提供的
共享数据缓存区
实现。 -
不同处理机中，通过
网络
实现。
同步：
时间上强制各执行进程在某一点必须互相等待。
可用软件、硬件、固件的办法来实现。
通讯：
- 共享存储多处理器使用：global read(X, Y) & global write(X, Y)
- 分布存储多计算机使用：send(X, i) & receive(Y, j)
2. 并行计算模型
PRAM模型（Parallel Random Access Machine，随机存取并行机器）
-
又称
SIMD-SM
模型。 -
有一个
集中的共享存储器
和一个
指令控制器
。 -
通过
SM
的R/W交换数据。 -
隐式
同步计算。 -
优点
：适合并行算法表示和复杂性分析；易于使用；隐藏了并行机的通讯、同步等细节。 -
缺点
：不适合MIMD并行机；忽略了SM的竞争、通讯延迟等因素。
异步APRAM模型
-
又称分相（Phase）PRAM或
MIMD-SM
。 -
每个处理器有
局部存储器、局部时钟、局部程序
。 -
无全局时钟、各处理器
异步
执行。 -
处理器通过
SM
进行通讯。 -
在并行程序中显示地加入
同步路障
。 -
计算过程：
由同步路障分开的全局相组成
。
BSP模型
-
“块”同步
模型。 -
是一种
异步MIMD-DM
模型。 -
支持
消息传递系统
。 -
块内异步并行，块间显式同步。
-
计算过程：由若干全局同步分开的、周期为L的
超级步
组成；各超级步中处理器做
LM操作
并通过
选路器收发消息
；然后做一次
全局检查
，以确定该超级步是否已经完成。
logP模型
-
使用了l、o、g、p四个参数来描述模型。
-
是一种面向分布式存储器、
点对点通信
的多计算机系统的模型。 -
L：Latency 表示信息从源到目的地所需的时间。
-
O：Overhead 表示处理器接收或发送一条消息所需的额外开销，并且在此期间处理器不能做任何操作。
-
G：Gap 表示处理器连续两次发送或接收消息之间必须有的时间间隔。
-
P：Processor 表示处理器的数目。
3. 设计方法
（1）串行算法并行化
- 不是所有串行算法都可以并行化。
- 一个好的串行算法并不能并行化为一个好的并行算法。
（2）针对问题直接设计并行算法
挖掘问题的固有特性与并行的关系。
（3）借用已有算法求解新问题
- 找出求解问题和某个已解决问题之间的联系。
- 改造或利用已知算法应用到求解问题上。
4. 设计过程
PCAM设计方法学
设计并行算法的四个阶段：
- Partitioning 划分：分解成小的任务，开拓并发性；
- Communication 通讯：确定诸任务间的数据交换，检测划分的合理性；
- Agglomeration 组合：依据任务的局部性，组合成更大的任务；
- Mapping 映射：将每个任务分配到处理器上，提高算法的性能。
四、并行算法性能测评
加速比性能定律
并行系统加速比：并行算法的执行速度相对于串行算法的执行速度加快了多少倍。
参数定义：
- P：处理器数；
- W：问题规模；Ws，串行分量；f是串行分量比例；Wp：可并行化部分；Ws+Wp=W；
- Ts=T1:串行执行时间；Tp：并行执行时间；
- S：加速比。
Amdahl 阿姆达尔定律
应用于
实时性要求较高
的科学计算。
-
固定不变的计算负载
； - 固定的计算负载分布在多个处理器上；
-
增加处理器
加快执行速度，从而达到了加速的目的； - Tp随处理器个数增多而减少，T1不变。
考虑额外开销W0时：
Gustafson 古斯塔夫森定律
-
应用于
精度要求较高
的科学计算。 -
很多大型计算，精度要求较高，而
计算时间固定不变
； -
为了提高精度，必须
加大计算量
，因此必须
相应增加处理器数量
才能维持时间不变。
考虑额外并行开销时：
Sun Ni 孙-倪定律
-
提出了
存储受限
的加速定律。 - 只要存储空间许可，应尽可能增大问题规模以产生更好和更精确的解。（执行时间可能增加）
- G(p)：存储容量增加到p倍时并行工作负载的增加情况。W‘ = G(p)
- 扩大存储容量后的工作负载W = fW+(1-f)G(p)W。
