并行程序设计

目录

一、Introduction

Amdahl定理

二、FP

当代并行计算机体系结构

并行体系结构模型 

并行计算机访存模型

并行程序开发方法

并行层次与代码粒度

并行程序开发策略

并行编程模式

并行应用编程过程的四个阶段（PCAM）

划分

通信

组合（任务组合）

映射（处理器映射）

并行程序设计模型

数据并行模型

共享变量模型

消息传递模型

三、SMP（共享内存架构编程）

共享内存系统并行编程简介

共享内存系统

例子：n个数求和问题。

并行代码V1

临界区

共享数据访问

加上互斥锁V2

并行性

互斥锁降低并行性

提高并行度（定义私有变量）

私有变量+互斥锁V3

指定线程进行sum的结果累计（不加锁）V4

同步

路障（Barrier）

加入路障V5

例子：对pai的计算

四、Pthreads并行编程

Pthread

临界区

使用标志变量flag

忙等待

Pthreads库的互斥锁

信号量Semaphores

同步

忙等待+互斥锁实现路障

信号量实现路障

条件变量

条件变量实现路障

五、LoopTrans探索循环的并行性

数据依赖

数据依赖关系

可并行性定理

循环数据依赖

数据重用

数据局部性

循环中的数据依赖

判别循环数据依赖

距离向量（依赖向量）

方向向量

循环转换

循环交换

循环交换的安全性问题

根据方向向量判断循环转换的合法性（安全性）

循环分块

循环展开

循环融合

并行性分析

并行分析：一维循环

并行分析：n维循环

Quiz

六、OpenMP并行编程

OpenMP简介

OpenMP体系结构

Fork-Join模型

准备工作和编译制导

并行区域结构

OepnMP指令作用域

用于显示定义变量范围的子句

工作共享结构

合并结构

同步结构

 指令

for 指令

sections 指令

single 指令

parallel for 指令

master 指令（同步结构）

critical 指令 （同步结构）

atomic 指令（同步结构）

flush 指令（同步结构）

ordered 指令（同步结构）

threadprivate 指令

 子句

if 子句

num_threads 子句

reduction 子句

schedule 子句（搭配for）

ordered 子句（搭配for）

nowait 子句

collapse 子句（搭配for）

运行时库函数

环境变量

七、MPI 并行编程

MPI 简介

MPI基本函数

MPI消息

数据类型

预定义数据类型

派生数据类型

MPI_Type_vector

MPI_Type_struct

消息标签

通信域

消息状态

点对点通信

通信模式

同步通信模式

缓冲通信模式

标准通信模式

就绪通信模式

通信机制

阻塞通信

非阻塞通信

点对点通信函数

重叠计算与通信

Send-Recv函数

集合通信

集合通信函数

广播MPI_Bcast

收集MPI_Gather

散播MPI_Scatter

全局收集MPI_Allgather

全局交换MPI_Alltoall

集合同步函数

路障MPI_Barrier

集合聚集操作

归约MPI_Reduce

扫描MPI_scan

---

一、Introduction

并行计算：一个系统，具有多个处理器（CPU），所有CPU可以访问共享存储器，以交换信息，通信开销低。

分布式计算：每个系统具有自己的处理器，通过网络将多个系统连通，系统之间通过消息传递的方式交换信息，通信开销大。

并行编程：在开发过程中，用来表示哪些计算应该并行执行。

Amdahl定理

假设程序有一部分是可以并行的。

S：加速比。a：可并行部分的占比。n：并行处理节点个数（CPU个数）。

 

例子：如果希望在100个处理器上获得90的加速比，请问在原始计算负载中顺序执行部分最多占多少？

假设并行部分占比a。根据Amdahl定理：

S = 1/（1-a+a/n） --> 90 = 1/(1-a+a/100)

解的：a = 0.999

所以，顺序部分占比 = 1 - a = 0.001 = 0.1%。

二、FP

当代并行计算机体系结构

并行体系结构模型 

并行体系结构模型：

1、单指令多数据流机 SIMD

2、并行向量处理机 PVP

3、对称多处理机 SMP

4、大规模并行处理机 MPP

5、分布式共享存储 DSM

6、工作站机群 COW

并行计算机访存模型

均匀存储访问模型 UMA

物理存储器被所有处理器均匀共享。

所有处理器访问任何存储字取相同的时间。

每台处理器可带私有高速缓存。

外围设备也可以一定形式共享。

非均匀存储访问模型 NUMA

被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间。

处理器访问存储器的时间是不一样的。

访问本地存储器LM或群内共享存储器CSM较快，而访问外地的存储器或全局共享存储器GSM较慢(此即非均匀存储访问名称的由来)。

每台处理器可拥有私有高速缓存，外设也可以某种形式共享。

全高速缓存访问模型 COMA

各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间。

利用分布的告诉缓存目录D，进行远程高速缓存的访问。

COMA中的高速缓存容量一般都大于二级高速缓存容量。

使用COMA时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用它们的地方。

高速缓存一致性非均匀存储访问模型 CC-NUMA

大多数使用基于目录的高速缓存一致性协议。

保留SMP结构易于编程的优点，也改善常规SMP的可扩放性。

CC-NUMA实际上是一个分布共享存储的DSM多处理机系统。

它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各节点分配数据。

在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。

非远程存储访问模型 NORMA

所有存储器是私有的。

绝大数NUMA都不支持远程存储器的访问。

在DSM中，NORMA就消失了。

并行程序开发方法

并行层次与代码粒度

并行级别越低，代码粒度就越细。

并行程序开发策略

并行编程模式

主-从式

将一个待求解的任务分成一个主任务（主进程）和一些从任务（子进程）。

主进程负责将任务的分解、派发和收集诸各子任务的求解结果并最后汇总得到问题的最终解。

各子进程接收主进程发来的消息；并行进行各自计算；向主进程发回各自的计算结果。

单程序多数据流

并行运行的进程均执行相同的代码段，但处理的数据不同。

首先将应用程序的数据预先分配给各个计算进程（处理器）。

然后计算进程并行的完成各自的计算任务，包括计算过程中各进程间的数据交换（进行通信同步）。

最后将计算结果汇集起来。

数据流水线

将计算进程组织成一条流水线，每个进程执行特定的计算任务（相当于流水线的一个阶段）。

将任务在功能上划分成一些子任务（进程），这些子任务完成某种特定功能的计算工作。

一旦前一个子任务完成，后继的子任务就可立即开始（此时前一个子任务就可以并行执行另一个任务了）。

整个计算过程中各进程之间的通信仅发生在相邻的阶段之间，且通信可以完全异步地进行。 

分治策略

将一个大而复杂的问题分解成若干个特性相同的子问题分而治之。

若所得的子问题规模仍嫌过大，则可反复使用分治策略，直至很容易求解的子问题为止。

问题求解可分为三步：①将输入分解成若干个规模近似相等的子问题；②同时递归地求解子问题；③归并各子问题的解成为原问题的解。

并行应用编程过程的四个阶段（PCAM）

划分：P（Partitioning）	分解成小的任务，开拓并发性。
通信：C（Communication）	确定诸任务间的数据交换，监测划分的合理性。
组合：A（Agglomeration）	依据任务的局部性，组合成更大的任务。
映射：M（Mapping）	将每个任务分配到处理器上，提高并行性能。

划分

充分开拓算法的并发性和可扩放性。

先进行数据分解(称域分解)，再进行计算功能的分解(称功能分解)。

使数据集和计算集互不相交。

划分阶段忽略处理器数目和目标机器的体系结构。

域分解

划分的对象是数据，可以是程序中的输入数据、中间处理数据和输出数据。

将数据分解成大致相等的小数据片。

划分时考虑数据上的相应操作。

如果一个任务需要别的任务中的数据，则会产生任务间的通信。

功能分解

划分的对象是计算（亦称为任务分解或计算划分），将计算划分为不同的任务，其出发点不同于域分解。

划分后，研究不同任务所需的数据。如果这些数据不相交的，则划分是成功的。

如果数据有相当的重叠， 意味着存在大量的通信开销，要重新进行域分解和功能分解。

功能分解是一种更深层次的分解。

划分的判据：

划分是否具有灵活性？

划分是否避免了冗余计算和存储？

划分任务尺寸是否大致相当？

任务数与问题尺寸是否成比例？

功能分解是一种更深层次的分解，是否合理？

通信

划分产生的各任务，一般不能完全独立执行，需要在任务间进行数据交流，从而产生了通信。

功能分解确定了各任务间的数据流。

各任务是并发执行的，通信则限制了这种并发性。

有四种通信模式：局部/全局通信、结构化/非结构化通信、静态/动态通信、同步/异步通信。

局部/全局通信

通信限制在一个邻域内，即局部内通信。

通信是全局的，例如All to All，Master-Worker

结构化/非结构化通信

每个任务的通信模式是相同的，就是结构化通信（即：以某种特定的结构进行通信）。

比如下面每个任务都采取的局部通信策略，那么整体上就是一种结构化通信。

那么，非结构化通信，就是没有一个同一的通信模式，比如：无结构化网格。

静态/动态通信

静态通信中，通信伙伴的身份不随时间改变。（固定通信对象）

动态通信中，通信伙伴的身份则可能由运行时所计算的数据决定且是可变的。（通信对象不固定）

同步/异步通信

同步通信时，接收方和发送方协同操作。

异步通信中，接收方获取数据无需与发送方协同。

通信的判据

所有任务是否执行大致相当的通信？

是否尽可能的局部通信？

通信操作是否能并行执行？

同步任务的计算能否并行执行？

组合（任务组合）

组合是由抽象到具体的过程，是组合的任务能在一类并行机上有效的执行。

合并小尺寸任务，减少任务数。如果任务数恰好等于处理器数，则完成了映射过程。

通过增加任务的粒度和重复计算，可以减少通信成本。

保持映射和扩展的灵活性，降低软件工程成本。

重复计算

可以减少通信量，但增加了计算量，应保持恰当的平衡。

重复计算的目标应减少算法的总运算时间。

示例：二叉树上N个处理器求N个数的全和，要求每个处理器均保持全和。

蝶式结构求和，使用了重复计算，共需logN步。

组合的判据

增加粒度是否减少了通信成本？

重复计算是否已权衡了其得益？

是否保持了灵活性和可扩放性？

组合的任务数是否与问题尺寸成比例?

是否保持了类似的计算和通信？

有没有减少并行执行的机会？

映射（处理器映射）

每个任务要映射到具体的处理器，定位到运行机器上。

任务数大于处理器数时，存在负载平衡和任务调度问题。

映射的目标：减少算法的执行时间。

        并发的任务：映射到不同处理器。

        任务之间存在高通信的：映射到同一处理器。

映射实际是一种权衡，属于NP完全问题。

负载平衡

静态的：事先确定。

概率的：随机确定。

动态的：执行期间动态负载。 

基于域分解的：递归对剖、局部算法、概率方法、循环映射。

任务分配与调度

负载平衡与任务分配/调度密切相关，任务分配通常有静态的和动态的两种方法。

静态分配一般是任务到进程的算术映射。

        优点是没有运行时任务管理的开销。

        要求任务的工作量和处理器的性能是可以预测的，并且拥有足够的可供分配的任务。

静态调度方案一般是静态地为每个处理器分配多个连续的循环迭代。也可以采用轮转（Round-robin）的方式来给处理器分配任务，即将第i个循环迭代分配给第i mod p个处理器。

动态分配与调度相对灵活，可以运行时在不同处理器间动态地进行负载的调整。

动态调度技术是并行计算研究的热点，包括基本自调度SS、块自调度BSS、 指导自调度GSS、因子分解调度FS、梯形自调度TSS、 耦合调度AS、安全自调度SSS和自适应耦合调度AAS。

经理/雇员模式任务调度

任务放在集中的或分散的任务池中，使用任务调度算法将池中的任务分配给特定的处理器。

映射的判据

采用集中式负载平衡方案，是否存在通信瓶颈？

采用动态负载平衡方案，调度策略的成本如何？

并行程序设计模型

数据并行模型

单线程

并行操作于聚合数据结构（数组）

松散同步

全局命名空间

隐式相互作用

隐式/半隐式数据分布

概况：

SIMD的自然模型，也可运行于SPMD、MIMD机器上。

局部计算和数据选路操作。

适合于使用规则网络，模板和多维信号及图像数据集来求解细粒度的应用问题 。

数据并行操作的同步是在编译时而不是在运行时完成的。

计算pai的数据并行代码：

每个部分分别求一段结果，存储进temp中，最后求和。

共享变量模型

多线程：SPMD, MPMD

异步

单一共享地址空间

显式同步

隐式/隐式数据分布

隐式通信（共享变量的读/写）

概况：

PVP、SMP、DSM的自然模型。

计算pai的共享变量代码

每个线程都对共享变量pi进行计算求和。

消息传递模型

多线程

异步并行性

分开的地址空间

显式相互作用

显式数据映射和负载分配

常采用SPMD形式编码

概况：

MPP, COW的自然模型，也可应用于共享变量多机系统，适合开发大粒度的并行性。

广泛使用的标准消息传递库MPI和PVM。

计算pi的消息传递代码（MPI代码），各计算单元之间通过显示的Send和Recv消息来交换数据。

三、SMP（共享内存架构编程）

共享内存系统并行编程简介

共享内存系统

每个处理器拥有私有存储（缓存）。

所有处理器共享内存空间。

处理器可以并行进行计算。

例子：n个数求和问题。

其中串行代码：

如何进行并行编程呢？

那么首先得进行PCAM步骤（划分、通信、组合、映射）：

划分：将n个数的求和问题进行划分，假设t 是处理器或线程数量，则可以划分成t个n/t 个数据的求和问题，最后把结果再相加。

通信：t个部分的和进行通信，计算出全部数据的和。

组合：划分步骤的任务数量，恰好等于CPU数量，不需要组合。

映射：直接进行映射，每个任务映射到一个CPU上。

例如：n = 24， t = 8，线程编号从0 到 7

并行代码V1

临界区

变量sum的访问竞争

两个线程同时更新sum变量时，发生错误。

此时sum的数据就出现了冲突，因为sum的临界资源。

共享数据访问

共享内存系统并行编程最基本的挑战是：当多个线程需要更新共享资源时，结果可能是不可预知的。

竞争条件：当执行的结果取决于两个或多个事件的执行时间时，就存在竞争条件。

临界区：对共享存储区域进行更新的代码段，或会造成竞争条件的代码段。

如何解决临界区问题

在循环内和线程之间，变量sum存在依赖关系。

读 -> 加锁 -> 写回，必须是原子操作，才能保证程序的正确性。

原子性：指事务的不可分割性，一个事务的所有操作要么不间断地全部被执行，要么一个也没有执行。

互斥锁：在编程中，引入了对象互斥锁的概念，来保证共享数据操作的完整性。某段代码被标记了互斥锁，那么在任何情况下，最多只能有一个线程可以执行该段代码。

加上互斥锁V2

对临界区加入互斥锁，保证在任何情况下，最多只能有一个线程可以执行该段代码。

还是有问题，仔细看这个代码，实际上来看，该代码还是个串行代码。

因为，在sum += my_x的时候加锁，那么实际上所有进入for循环的线程，都会阻塞，每次只有一个线程执行该逻辑。

那么这样来看，该代码其实是有多个线程，每次有一个线程在进行 sum += my_x逻辑，这和一个线程对n个数求和来看逻辑上是一致的，本质上是个串行程序。

并行性

互斥锁降低并行性

互斥访问的结果是串行访问。

互斥锁变量是共享数据，锁变量为1表示锁占用，为0表示空闲。

线程为了获得互斥锁，至少需要经过几个层次的cache。

提高并行度（定义私有变量）

为每个线程定义私有变量 my_sum，每个线程只需要把自己的求和结果放入my_sum即可。

那么对my_sum += my_x，就不在是临界区了，各线程可以并行访问。

私有变量+互斥锁V3

每个线程定义私有变量my_sum，各线程计算完毕后，在将my_sum 加到 sum的时候，对该逻辑加锁。

指定线程进行sum的结果累计（不加锁）V4

此时又有一个问题，指定了线程后，怎么拿到其它线程的计算结果呢？

此时采用数据并行模型，定义一个共享变量数组my_sum[t]，每个线程将自己的计算结果放入my_sum[tid]内，这个数组是一个全局变量，所有线程都能看到。

最后再指定一个线程，对sum进行累加，就可以不加锁了。

此时还有一个问题：

如何得知，各个线程都完成了自己的计算任务呢？

如果没有完成，那么指定线程对sum的累计计算任务的结果就是错的！

同步

如果其它线程还没结束，主线程就开始计算累加结果了，那么结果就是错的。

那么如何让主线程等待其它线程都执行结束呢？

路障（Barrier）

路障，又称为同步点，只有当所有线程都抵达此处，线程才能继续运行下去，否则就会阻塞在路障处。

加入路障V5

在V4版本的基础上，加入路障，确保所有线程计算完成。

例子：对pai的计算

其中串行代码如下：

进行并行编程：

计算pai，实际就是对求和。

首先进行PCAM操作：

划分：假定N取值10000，本机CPU个数为5，那么分为5个计算任务，每个计算任务处理2000个数据求和。

通信：定义全局变量数组sum[tid]，线程之间通过该数组进行通信，最终主线程通过该数组求和。

组合：无需组合，任务个数 = 处理器个数。

映射：每个处理器映射一个任务。

然后进行编程：

明确每个线程的计算任务的始终index：start_i和end_i。

各线程内部通过始终index对式子求和。

随后在循环结束位置，设置路障。

最终，指定主线程，对sum[]数组求和，得到最终的pai。

四、Pthreads并行编程

Pthread

Pthreads 不是编程语言，而是POSIX 线程库，也经常称为Pthreads 线程库。

Pthreads线程库支持：创建并行环境、同步、隐式通信。

通过Pthreads并行计算pai：

其中factor：表示计算式中，该位置应该是正还是负。

临界区

使用标志变量flag

使用一个标志变量flag，定义为共享int 型，主线程将其初始化为0。

该flag定义为共享变