并行程序设计

一、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定义为共享变量，用于标识是否该当前线程执行操作，此时这个while就是一个忙等待了：

此时加入的忙等待，就类似于一个互斥锁，让线程有序的进入对共享变量sum的操作处。

不同于互斥锁，如果采用互斥锁，可能会导致某些线程永远申请不到锁，造成饥饿。

忙等待

while循环是忙等待的一种实现。

线程会重复测试某个条件（标志变量flag的值），直到不满足某个条件才会跳出while循环。

忙等待通过加入一个空的while循环，可以实现临界区的互斥访问。

但是使用忙等待时，应该关闭编译器优化。编译器可能会自动将该忙等待优化掉

忙等待的性能

空循环造成了性能的降低。

线程有序的执行临界区。

临界区的互斥执行降低了代码的并行性，减少临界区执行次数的方法：同样是定义私有变量my_sum存储各自的计算结果，在循环的外面设置忙等待来计算总的结果sum。

Pthreads库的互斥锁

Pthreads线程库定义了互斥锁变量类型：pthread_mutex_t。

特殊类型的变量，通过某些特殊类型的函数，互斥锁可以用来限制每次只有一个线程能进入临界区使用pthread_mutex_t类型的变量前，必须初始化。

互斥锁调用

通过互斥锁，实现临界区的互斥访问：

互斥锁变量mutex是共享变量，通过系统的原子交换实现互斥锁变量的访问。

多个线程通过调用pthread_mutex_lock函数竞争互斥锁线程执行临界区的顺序是随机的，由操作系统决定。

信号量Semaphores

信号量可以认为是一种特殊类型的unsigned int 变量，可以赋值为0 、1 、2，只有0和1值的信号量称为二元信号量。

所有线程通过PV操作（sem_post【归还信号量】和sem_wait【申请信号量】函数更新信号量的值），P（申请信号量）V（归还信号量），信号量本质上是对临界资源的一种预定机制。只有申请到了信号量的线程，才有资格进入临界区。

线程在进入临界区之前，申请信号量，获取进入资格。

离开临界区后，归还信号量。

信号量一般配合锁来实现互斥，因为信号量只是对操作临界资源做了一个申请。

如果是二元信号量的话，可以单独使用二元信号量来实现互斥。

通过信号量（二元）实现临界区互斥访问：

同步

在计算pai的并行程序中，给每个线程配置私有变量my_sum存储各自的计算结果，再将所有线程的my_sum相加得到sum。为保证所有my_sum都计算结束后才进行sum的计算，需要加入同步语句。即可以设置路障。

忙等待+互斥锁实现路障

定义共享变量counter用于计算完成任务的线程数量，由于是共享变量，所以在外部进行加锁。

随后，设置忙等待条件，只有当counter = thread_count的时候，所有线程才会跳出循环，即所有线程都完成了计算任务。

信号量实现路障

其中：

count_sem信号量，用于保护计数共享变量counter的互斥访问，count_sem是二元的。

barrier_sem信号量，用于阻塞进入到路障位置的线程，当所有线程到达路障时，才会释放。

进入if条件时：如果counter == thread_count – 1，代表这是最后一个线程来了，该线程执行thread_count – 1次归还barrier_sem信号量的操作，达到唤醒其它所有阻塞在该信号量位置的线程。

如果进入else条件，代表不是最后一个线程，那么counter计数++，并且它也去申请barrier_sem信号量，但由于barrier_sem信号量的初始值为0，所有申请该信号量的线程都将阻塞。

至此，实现路障。

线程被阻塞在sem_wait 不会消耗CPU 周期，所以用信号量实现路障的方法比用忙等待和互斥锁实现的路障性能更好。

条件变量

条件变量是一种数据对象，允许线程在某个条件或事件发生前都处于挂起状态。

另一个线程可以通过信号来唤醒挂起的线程。

条件变量为共享变量，需要与互斥锁一起使用。

条件变量类似于一种“满足机制”，当条件不满足时，让A线程在条件变量处睡眠挂起，等待条件满足；当B线程执行某操作后，条件满足，B线程通过信号唤醒A线程。

条件变量实现路障

同样通过共享变量counter来记录完成任务的线程数量。

如果不是全部满足，将到达的线程睡眠挂起，即执行pthread_cond_wait（wait函数内部会自动释放已拥有的锁，直到被唤醒，唤醒时再去申请锁，申请成功后，才会执行后续操作）操作。

如果是最后一个线程到来，将所有睡眠的线程全部唤醒。

五、LoopTrans探索循环的并行性

数据依赖

如果两个存储访问操作访问相同的存储位置（同一个变量），其中一个访问是写（或更新）操作，则两个操作间存在数据依赖。

数据依赖关系体现了两个存储访问操作的执行顺序，必须按照该顺序执行两个操作才能得到正确的结果。

两个不同的程序语句之间可能存在数据依赖关系。

同一程序语句的两个不同的动态执行之间也可能存在数据依赖关系。（比如左侧a[i]，这次对它是写操作，下次循环对它是读操作，两次操作中有一次是写，就存在依赖关系。）

即：数据访问 a 和 A如果存在数据依赖（假设a在A之前执行），当且仅当：

1、a 和 A其中至少有一个为写操作。

2、a 和 A访问同一个变量（同一个存储位置）。

数据依赖关系

真依赖（真相关） — 写后读

即：后一个任务，需要前一个任务的计算结果。

a = b + c（写a）

d = 2 * a（读a）

并行问题：任务2必须等待任务1完成，否则读到的是未更新的值。

反依赖（反相关）— 读后写

即：前一个任务需要读取后一个任务即将写入的数据。

b = a + c（读a）

a = 2 * c（写a）

并行问题：若任务2先执行，任务1会读到错误的a的值。

输出依赖（输出相关）— 写后写

即：两个任务对同一变量先后写入。

a = b + c（写a）

a = 2 * b（写a）

并行问题：两个任务执行的顺序不同时，最终a的值也不同。

可并行性定理

判断语句是否可以并行执行的定理：

如果 I(Pi)是任务Pi需要读取的数据集合，O(Pi)是任务Pi需要写入的数据集合，根据数据依赖的条件：

如果 I(P1) ∩ O(P2) = I(P2) ∩ O(P1) = O(P1) ∩ O(P2) = ϕ（空集）

则P1和P2可以并行执行。

（即两个任务不存在对同一存储位置同时写，或者一个读一个写的情况，则这两个任务可以并行执行）。

即：两个任务之间，必须是不存在数据依赖的情况，才可以并行执行。

如果存在数据依赖（真依赖、反依赖、输出依赖），都无法并行，只能串行，或者同步。

循环数据依赖

数据重用

相同的数据或者相邻的数据，被多次使用。

数据重用是计算固有的性质。

A[j] 在第i次和第i+1次重复使用。

时间上的重用：A[j] 在外从循环（for(i=1;i<N;++i)）上，在不同的迭代（不同的时间）被重复使用。

空间上的重用：A[j] 所在的缓存行（空间）在内存循环（for(j=1;j<N;++j)）上被反复使用。

这与多维数组如何存储相关：行存储和列存储。

数据局部性

被重用的数据，存储在较快的存储器中（缓存或寄存器）。

这样的话，该数据被重用时，直接在缓存或CPU寄存器中拿到，效率很快。

局部性优化（探索重用）

循环转换会重排存储访问序列，从而提升局部性。

这些转换对于并行也是非常有用的。

但是，要考虑两个问题：

安全：循环转换是否保持了数据依赖。

收益：循环转换是否能带来性能上的收益。

循环中的数据依赖

如果循环中，不存在数据依赖，那么并行循环就是安全的。

for(i=1;i<=n;i++)
    A[i] = B[i] + C[i];

这种情况可以并行按照任意顺序执行循环，任务分配后，哪个线程先后执行不影响结果。

并且，也可以i–的方式进行循环。

循环体依赖，不同的迭代之间存在数据依赖。（也叫循环迭代依赖）

for(i=2;i<5;i++)
    A[i] = A[i-2] + 1;

循环无关依赖，迭代的内部存在数据依赖。即与循环无关，只是内部存在数据依赖。这种依赖，不影响循环并行。

for(i=1;i<=3;i++)
{
    A[i] = B[i] + 1;
    C[i] = A[i] * 2;
}

判别循环数据依赖

利用迭代空间，以空间形式，显示的表示循环迭代。

迭代实例：用迭代空间中的坐标来表示，例如[1,1] 表示i=1，j=1时的迭代实例。

字典序：迭代的串行执行顺序（即迭代展开的序列），例如：[0,0], [0,1], [0,2] … [0.6],[1,1], … [1,6], …. [5,6]。

字典序小于：即两个迭代实例A和B，和字符串比较一样，遇到第一个不相同的坐标，如果A的那个坐标小于B的那个坐标，则A < B，例如[1,2,4] < [1,1,6]。

迭代间的依赖关系可以通过循环内语句的数据依赖获得：

如图（结合循环语句），由于数据A[2,2]的写后读，存在不同迭代之间的依赖，因此具有循环体依赖。

根据循环语句和迭代空间，红色实线箭头，由循环语句的右侧指向左侧；即从读操作，指向，写操作。如图就是从 I 指向 I`。即若 I 到 I` 存在依赖，箭头就从 I 指向 I`。

距离向量（依赖向量）

简明地描述一个迭代空间的迭代之间的依赖关系。

从迭代 I 到迭代 I` 存在数据依赖，那么该循环存在距离向量 D = I` – I。

注意：第一个一定是外层循环的值，第二个是内层循环的值。

比如这个循环，从 A[i,j] 到 A[i+1,j+1]存在数据依赖，那么D = [1,1] 。

for (int i = 1; i < N; i++)
    for (int j = 1; j < M; j++)
        A[i][j] = A[i-1][j] + A[i][j-1];

再比如这循环，存在两个数据依赖。

从A[i-1,j] 到 A[i,j] 有依赖，D1 = [1,0]。

从A[i,j-1] 到 A[i,j] 有依赖，D2 = [0,1]。

距离向量与数据依赖的合法性

要使循环转换合理，必须保证数据依赖保持不变。

字典序非负：距离向量的最左边值为正数。或者距离向量的所有值都为0时。满足字典序非负。

当字典排序非负时，循环依赖关系是合法的。

方向向量

和距离向量一样，用来表示循环体依赖。

有三个符号： < 、 > 、=

< : 从I 到 I` 存在循环体依赖，且 I < I`。

> : 从I 到 I` 存在循环体依赖，且 I > I`。

=：循环无关依赖。

例如：距离向量D = [1,1] ，即表示从I[i,j] 到 I[i+1, j+1] 有循环体依赖，距离向量D才会是[1,1]，又I < I`，所以方向向量为 [<,<]。

如果距离向量D = [1,0], 那么方向向量为为 [<.=]。

合法的循环体依赖的方向向量：[<,<] [<,=] [<, >] [=,<] [=,=]。

不合法的循环体依赖的方向向量：[=,>] [>,<] [>,=] [>,>]。

即：对应的距离向量D，如果首元素的值为负，则对应的方向向量不合法。如果首元素的值为0，且后续元素的值为负，则对应的方向向量不合法。

总结：

方向向量的首元素为正，合法。

方向向量的全部元素都为0，合法。

方向向量的首元素为负，不合法。

方向向量的前面的元素为0，然后出现负的，不合法。

循环转换

用于组织计算序列和内存访问序列，以更好地适应多核处理器的内部结构以及指令级并行。

循环交换

交换循环的顺序来改变数据遍历的顺序。

注意距离向量的第一个值是外层循环，第二个值是内层循环。

所以这里两个距离向量和方向向量都会改变。

通过循环交换，探索数组A的数据局部性

原循环：读A[0][0], 写A[1][0], 读A[0][1],写 A[1][1], 读A[0][2], 写A[1][2],……

交换后：读A[0][0], 写A[1][0], 读A[1][0],写 A[2][0], 读A[2][0], 写A[3][0] …….

通过循环交换，在适当的循环层级获得合适的并行粒度：

原循环并行粒度：内层循环内可以并行：

把内循环并行出去，因为内循环对j作循环，而式子中j与j之间没有依赖，可以并行。

交换后并行粒度：外层循环内可以并行：

把外循环并行出去，因为外循环对j作循环，而式子中j与j之间没有依赖，可以并行。

循环交换的安全性问题

[<,=]：循环体依赖由i循环携带。

[=,<]仍由i循环携带，因此依赖关系不会改变。

因此，此类循环转换是安全的。

循环转换后，保持数据依赖，则循环转换是安全的（合法的）。

比如上述例子：

D = [1,0]

对于条件1：子向量（0）不严格 > 0，不满足。

对于条件2：对j >= 1，d1 = 1 >= 0，d2 = 0 >= 0 ,满足，所以交换i和j层循环安全。

for (int i = 1; i < N; i++)
    for (int j = 1; j < M; j++)
        A[i][j] = A[i-1][j+1] + B[i][j]; // 依赖向量 (1, -1)

D = [1,-1]

对于条件1：子向量（-1）不严格 > 0，不满足。

对于条件2：对 j >= 1，d2 = -1 < 0，不满足。所以交换i和j层循环不安全。

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

[=,=]: 循环无关依赖，循环转换是安全的。

[=,<]：循环体依赖由内层j循环携带，循环交换后方向向量为[<,=]仍由j循环携带，依赖关系不改变。此类循环转换是安全的。

[<,=]：循环体依赖由外层i循环携带，循环交换后方向向量为[=,<]仍由i循环携带，依赖关系不改变。此类循环转换是安全的。

[<,<]: 两层循环都携带循环体依赖，方向向量为正，循环转换后方向向量仍为正，依赖关系不改变。此类循环转换是安全的。

[<,>]：循环体依赖由外层i循环携带，循环交换后方向向量为[>,<] 是不合法的方向向量，改变了依赖关系。此类循环转换是不安全的。

[>,*][=,>]：原循环不可能存在该类方向向量。

不合法循环体依赖的方向向量：([=,>],[>,<], [>,=], [>,>])。

即：若循环转换后的方向向量不合法，则该循环转换不合法。

反之合法，也得确保转换前的方向向量也是合法的。

循环分块

重排循环迭代，让有数据重用的迭代相继执行优化缓存、寄存器等容量有限的存储设备的数据重用。

如上，把i循环分成左右两块执行。

循环分块方法：采用strip-mine-and-interchange分块法首先进行strip-mine（分块执行），增加循环层次，然后进行interchange，使循环分块执行。

Tilling从最内层循环开始，因为需要考虑cache大小。

探索数据局部性

循环展开

简单的将多个循环展开到一个循环内。

如上，简单的将j层循环的j++改为j+=2，从而循环体由一个式子变为两个式子。

此时，原本外层循环i=0时，内层循环执行：

现在变为

并行探索

展开后，不超过原始循环的迭代次数就是安全的。

展开，增加了循环内部的并行度。

减少了循环次数即减少了控制语句，提升性能。

因为内层循环的条件变为j+=2，而循环体的j与j之间，只是相邻的j数据之间的依赖（j 和 j+1，j+1和j+2），不存在j和j+2之间的依赖，因此内层循环可以并行。

探索数据局部性

B[j+1][i+1]和b[j+2][i+1]重用，数组B在寄存器的时间上重用。

循环展开越多，数据重用越多，数据局部性越好。

循环融合

就是将多个循环融合在一起。

这里C[i] 只依赖对应的A[i]，只要保证A[i]比C[i]先写入就能保证安全。

保持循环间数据依赖的数据融合才是安全的。

这里C[i] 依赖 A[i+1]，如果采用第一种融合的的话，即数组A写后读，但是写了A[i]，并没有写A[i+1]，因此是不安全的融合。

采用第二种，逆序遍历（提前把A[n]写好），写A[i]时，相当于把下一次循环C[i]所需要的A[i+1]写好了，是安全的循环融合。

探索数据局部性

循环融合后优化了数据局部性：数组A的访问。

减少了循环次数即减少了控制语句，提升性能。

并行性分析

比如这个循环展开：

减少了循环次数即减少了控制语句，提升性能。

一次迭代内，指令级并行性提升。

一次循环执行了四个指令。

并行分析：一维循环

一维循环，如果所有的距离向量D = 0，那么此循环可以并行执行。

即：数据间没有依赖关系，可以并行。

这个相邻数据间存在依赖关系，D = 1，不可以并行。

并行分析：n维循环

这个循环，可以将外层 i 并行，因为循环体内，只有j之间存在数据依赖关系。

这个循环，无法并行出去，因为i和i之间与j和j之间都存在数据依赖关系。

定理1：

假设循环的距离向量为D = [d1, … dn] ，如果在 i层循环存在循环体依赖，那么di 就是D中第一个非零的值。

比如这个，在 j层循环存在循环体依赖，所以 dj = 1是第一个非零的值。

比如这个，在 i层循环存在循环体依赖，所以 di = 1是第一个非零的值。

如果某层循环不存在循环体依赖，那么该层循环的迭代可以并行执行。

定理2：

N维循环的距离向量为D = (d1, … dn)，当 [d1, …, dj-1] > 0（前j-1维分量全为正）或者 [d1, ….. , dj] = 0 （前j维分量全为0）时，第j层循环迭代可以并行。

for (int i = 1; i < N; i++)         // 第1层循环（i）
    for (int j = 1; j < M; j++)     // 第2层循环（j）
        A[i][j] = A[i-1][j] + B[i][j];  // 依赖向量 (1, 0)

这个循环的距离向量D = [1,0] ，根据定理2，[ d1 = 1] > 0，前1维分量全为正，则第 2层循环，即循环层 j 可以并行。

这个D = [0,1] ，根据定理2，[ d1 = 0 ] = 0，前1维分量全为0，则第 1层循环，即循环层 i可以并行。

Quiz

找出循环迭代的所有数据依赖关系

从循环式子可知依赖关系：

读操作（A[i-1][j-1] ） –> 写操作（A[i][j]），距离向量D1 = [1,1]

读操作（A[i+2][j-1]） –> 写操作（A[i][j]），距离向量D2 = [-2,1]

画出该循环的迭代空间，并在迭代空间中给出所有循环体依赖（用箭头表示）

判断该循环是否可以并行？如果可以，请给出能够在那层循环并行

根据定理2：

定理2：

N维循环的距离向量为D = (d1, … dn)，当 [d1, …, dj-1] > 0（前j-1维分量全为正）或者 [d1, ….. , dj] = 0 （前j维分量全为0）时，第j层循环迭代可以并行。

距离向量D1 = [1,1] , D2 = [-2,1]

检查外层循环（i）的并行性：

需要前 i – 1 = 0 维分量全为正（i – 1 = 0没了）或者前 i 维分量全为0（D1d1 = 1, D2d1 = -2），都不满足条件，所以外层循环i 不能并行。

检查内层循环（j）的并行性：

需要前 j – 1 = 1 维分量全为正（D1d1 = 1, D2d1 = -2不满足）或者前 j 维分量全为0（不满足）都不满足条件，所以内层循环j 不能并行。

因此，该循环不能并行。

六、OpenMP并行编程

OpenMP简介

是Open Multi-Processing的缩写，被大多数计算机硬件和软件厂家所标准化。

是针对共享内存的应用编程接口(API)，可用于显式地指导多线程、共享内存的并行编程。

OpenMP体系结构

由三个主要API组件构成：编译器指令、运行时库函数、环境变量。

支持以增量方式并行化串行程序。

基于线程的并行编程模型。

需要编译器的支持。

Fork-Join模型

OpenMP使用并行执行的Fork-Join模型

OpenMP程序开始于一个主线程，主线程串行执行直到遇到第一个并行区域。

Fork：主线程创建一组并行线程。

并行区域的程序由这组线程并行执行。

Join：执行完并行区域，线程进行同步并终止，只留下主线程继续执行。

并行区域的数量和线程数量是任意的。

准备工作和编译制导

头文件：<omp.h>

#pragma omp parallel private(nthreads, tid)

#pragma omp：制导指令前缀，所有的OpenMP都需要。

parallel：在制导指令前缀和子句之间必须要有一个正确的OpenMP制导指令。

private(nthreads, tid)：OepnMP子句，在没有其它约束的条件下，子句可以无序。

并行区域结构

基本的OpenMP并行结构，Fork-Join模型。

格式：

例子：

并行区域是多线程执行的代码块，是基本的OpenMP并行结构。

一个线程执行到一个并行指令时，Fork一组线程并成为该线程组的主线程（线程号为0）。

从并行区域开始，代码被复制，一组线程都执行该代码。

并行区域出口隐含barrier，只有主线程继续执行。

OepnMP指令作用域

三个函数都用了OpenMP指令，存在指令的嵌套，OpenMP指令有作用域：

静态范围

文本代码在一个编译制导语句之后，被封装到一个结构块中：#pragma omp parallel后面的结构快{}。这样的指令不能跨越程序或者文件。

fun()中do指令出现在parallel的并行块中，就属于静态范围的指令。

孤立指令

一个不依赖于其它语句的编译制导语句。

会跨函数或文件。

critical和section是孤立指令。

动态范围

包括静态范围和孤立指令的范围。

fun()调用了sub1()和sub2()，critical和section就出现在了parallel的动态范围内。

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

private(list)	将list中的变量，声明为每个线程的私有变量。
shared(list)	将list中的变量，声明为每个线程的共享变量。
default(shared \| none)	指定并行区域内变量的属性是shared. none作为默认值要求程序员必须显式地限定所有变量的作用域.
firstprivate(list)	在进入并行区域之前进行一次初始化，让并行区域的list中变量的值初始化为同名共享变量的值.
lastprivate(list)	在退出并行区域时，将并行区域的list中变量的值赋值给同名的共享变量.
copyin(list)	将主线程中threadprivate变量的值拷贝到执行并行区域的各个线程的threadprivate变量中，list包含要复制的变量的名称.
copyprivate(list)	将单个线程私有list变量的值广播到其他线程的私有list变量.
reduction(reduction-identifier: list)	对list中的变量进行约简操作. 为每个线程创建并初始化list中变量的私有副本（list中变量为共享变量）。对所有线程的私有副本进行约简操作，并将最终结果写入共享变量。约简操作符和初始值：

reduction子句例子：

设定变量为共享变量，i 为私有变量，将最终的result（私有），通过reduction(+:result)子句，加到总的result中。

工作共享结构

工作共享结构不会启动新线程，为了使指令能够并行执行，必须将工作共享结构封装在一个并行区域中。

工作共享结构将所包含的代码划分给线程组的成员来执行。

进入工作共享结构没有barrier，但在出口隐含barrier。

并行do/for loop：线程组并行执行代码，实现数据并行。

并行sections：计算任务分成单独的、不连续的部分，每个线程执行一部分，可以实现函数并行。

single：串行执行代码。

合并结构

合并了并行区域结构与共享任务结构的指令。

parallel for指令：合并parallel和for两个指令。

（除了nowait子句外，所有parallel和for适用的子句和规范也都适用于parallel for指令)。

parallel sections指令:合并parallel和sections两个指令。

（除了nowait子句外，所有parallel和for适用的子句和规范也都适用于parallel for指令）。

同步结构

实现多线程间互斥访问和同步的指令。

master指令：指定一个代码区域由主线程执行，其他线程跳过这个区域。

critical指令：指定一个代码区域每次只能由一个线程执行（互斥访问），可以实现临界区访问。

barrier指令：指定线程组所有的线程在此指令处同步。

atomic指令：指定以原子方式访问特定的存储位置，该指令仅适用于其后的单个语句，可以实现一个最小临界区的访问。

flush指令：标识一个数据同步点，将线程的变量写回内存，实现内存数据更新。

ordered指令：指定循环迭代以串行执行顺序执行。

指令

for 指令

for指令指定循环语句必须由线程组并行执行，假设已经启动了并行区域，否则将串行执行。

使用限制：

不能是while循环，或者任何循环迭代次数不确定的循环。

循环迭代变量（i）必须是整数，并且对于所有线程，循环控制参数（i++）必须相同。

跳转或跳出循环是非法的。

块大小必须为整数次迭代。

schedule、ordered和collapse子句只可以出现一次。

sections 指令

sections指令指定所包含的代码段被分配给各个线程执行。

不同section部分可以由不同线程执行，如果一个线程运行的快，也可以执行多个部分。

使用限制

sections指令的末尾有隐含的barrier，可以使用nowait子句忽略。

不能跳转或跳出section代码块。

section指令必须在封闭的sections指令的词法范围内。

single 指令

single指令指定所包含的代码仅由一个线程执行，通常用于处理非线程安全的代码段，例如I/O。

使用限制

不能跳转或跳出一个single代码块。

parallel for 指令

Parallel for指令表明一个并行域包含一个独立的for语句。

master 指令（同步结构）

指定一个代码区域由主线程执行，其他线程跳过这个区域。

critical 指令（同步结构）

指定一个代码区域每次只能由一个线程执行（互斥访问），可以实现临界区访问。

如果一条线程正在一个critical区域执行而另一个线程到达这个区域，并企图执行，那么它将会被阻塞，直到第一个线程离开这个区域。

name是可选项，使不同的cirtical区域共存，具有相同命名的不同的critical区域被当作同一个区域，所有未命名critical区域被当作同一个区域。

atomic 指令（同步结构）

指定以原子方式访问特定的存储位置，该指令仅适用于其后的单个语句，可以实现一个最小临界区的访问。

flush 指令（同步结构）

标识一个数据同步点，将线程的变量写回内存，实现内存数据更新。

用于明确的表明程序点处需要进行内存更新。

某些指令隐含flush指令，不过如果有nowait子句，则flush指令失效。

ordered 指令（同步结构）

指定循环迭代以串行执行顺序执行。

如果前面的迭代没有完成，则执行后面迭代的线程需要等待。

ordered指令只能出现在出现在for或者parallel for的动态范围内。

threadprivate 指令

指定全局变量被所有线程各自产生一个私有的副本，对于不同并行区域之间的同一个线程，该副本变量是共享的。

子句

if 子句

if(scalar-expression)：

如果有if子句，那么只有表达式为真（非0）才会创建一个线程组，否则该区域由主线程串行执行。

即：当if（true）时才会fork出线程进入并行区域，否则只有主线程执行。

num_threads 子句

num_threads(integer-expression)：

用于设置运行并行区域的线程数量，integer-expression表示线程数量。

并行区域的线程数量由以下因素决定，优先级从高到低：

1、 if子句的结果。

2、num_threads子句的设置。

3、omp_set_num_threads() 库函数的设置。

4、OMP_NUM_THREADS 环境变量的设置。

5、编译器默认实现（一般是处理器的核心数）。

reduction 子句

reduction（规约）是 OpenMP 的关键子句，用于合并多个线程的计算结果。

reduction(reduction-identifier: list)：

为每个线程创建并初始化list中变量的私有副本（list中变量为共享变量）。

对所有线程的私有副本进行约简操作，并将最终结果写入共享变量。

#pragma omp parallel num_threads(thread_count) reduction(+ : global_result)
    {
        global_result += Local_trap(a, b, n);
        /*
        reduction（规约）是 OpenMP 的关键子句，用于合并多个线程的计算结果。
        + 表示规约操作是求和（其他操作如 *, max, min 等也可用）。
        global_result 是共享变量，但通过 reduction，每个线程会拥有它的私有副本，
        计算完成后自动合并到主线程的 global_result。
        */
    }

即为每个线程创建global_result副本，各自计算自己的结果。

然后由于reduction子句（+：global_result），在离开并行区域后，自动相加各副本global_result的值，得到总的结果。

schedule 子句（搭配for）

schedule(kind[,chunk_size])：（主要和for 指令搭配）

描述循环迭代如何划分给多个线程。

kind：可以为static（静态）、dynamic（动态）、guided（引导）、runtime（运行时）、auto（自动）五种模式，表示划分的方式。

chunk_size：表示划分给线程的块的大小。

ordered 子句（搭配for）

ordered[ (n) ]：（ordered子句只能用在for或parallel for中）

指定区域的循环迭代将按串行顺序执行，与单个处理器处理结果顺序一致。

nowait 子句

忽略并行区域隐含barrier的同步等待。

collapse 子句（搭配for）

collapse(n)：

指定嵌套循环中的n个循环折叠到一个大的迭代空间中，并根据调度子句划分并行执行。

能够解决线程间负载均衡或线程负载太小的问题。

所有相关循环的顺序执行决定了折叠迭代空间中迭代的顺序。

运行时库函数

环境变量

OpenMP提供了环境变量来控制并行代码的执行。

所有环境变量名都是大写的。

常用环境变量：

七、MPI 并行编程

MPI 简介

分布式内存系统

每个处理器有私有内存，处理器只能访问自己的内存。

运行在处理器-内存对上的程序称为进程。

进程间采用显式的消息传递进行通信：一个进程调用消息发送函数，另一个进程调用消息接收函数。

什么是MPI（只是一个消息传递的接口标准）

使用消息传递的方式实现称为消息传递接口（Message-Passing Interface，MPI）。

MPI是一个消息传递接口标准，而不是编程语言。

MPI标准定义了一组具有可移植性的编程接口。

MPI以语言独立的形式存在，可运行在不同的操作系统和硬件平台上。

共有上百个函数调用接口，C/C++和Fortran语言中可以直接对这些函数进行调用。

简单MPI程序：

MPI基本函数

int MPI_Init( int* argc, char*** argv )	MPI初始化，通过MPI_Init函数进入MPI环境，并完成所有的初始化工作。
int MPI_Finalize(void)	MPI结束，从MPI环境中退出。
int MPI_Comm_rank(MPI_Comm comm, int* rank)	获取进程的编号，通过MPI_Comm_rank函数，获取当前进程在指定通信域中的编号，将自身与其它程序区分。
int MPI_Comm_size(MPI_Comm comm, int* size)	获取指定通信域的进程数，调用MPI_Comm_size函数获取指定通信域的进程个数，确定自身完成任务比例。
int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)	消息发送：MPI_Send函数用于发送一个消息到目标进程。
int MPI_Recv(void* buf, int count, MPI_Datatype, int source, int tag, MPI_Comm comm, MPI_Status* status)	消息接收:MPI_Recv函数用于从指定进程接收一个消息。

MPI消息

一个消息好比一封信。

消息的内容即信的内容，在MPI中称为消息缓冲(Message Buffer)。

消息缓冲由三元组<起始地址，数据个数，数据类型>标识。

消息的接收/发送者及信的地址，在MPI中称为消息信封(Message Envelop)。

消息信封由三元组<源/目标进程，消息标签，通信域>标识。

三元组的方式使得MPI可以表达更为丰富的信息，功能更强大。

数据类型

MPI的消息类型分为两种：预定义类型和派生数据类型。

预定义数据类型

MPI支持异构计算。

异构计算指在不同计算机系统上运行程序，每台计算可能有不同生产厂商，不同操作系统。。

MPI通过提供预定义数据类型来解决异构计算中的互操作性问题，建立它与具体语言的对应关系。

MPI_BYTE：表示一个字节，所有的计算系统中一个字节都代表8个二进制位。

MPI_PACKED：预定义数据类型被用来实现传输地址空间不连续的数据项。

MPI_PACKED

MPI_Pack_size函数来决定用于存放50个MPI_DOUBLE数据项的临时缓冲区的大小。

调用malloc函数为这个临时缓冲区分配内存。

for循环中将数组A的50个偶序数元素打包成一个消息并存放在临时缓冲区。

将临时缓冲区的数据类型为MPI_PACKED的消息发送。

派生数据类型

MPI引入派生数据类型来定义由数据类型不同且地址空间不连续的数据项组成的消息。

派生数据类型可以用类型图来描述，这是一种通用的类型描述方法，它是一系列二元组<基类型，偏移>的集合，可以表示成如下格式：

在派生数据类型中，基类型可以是任何MPI预定义数据类型，也可以是其它的派生数据类型，即支持数据类型的嵌套定义。

先声明一个类型为MPI_Data_type的变量EvenElements 。

调用构造函数MPI_Type_vector(count, blocklength, stride, oldtype, &newtype)来定义派生数据类型。

新的派生数据类型必须先调用函数MPI_Type_commit获得MPI系统的确认后才能调用MPI_Send进行消息发送。

MPI_Type_vector

count：派生数据类型newtype由count个数据块构成

blocklength和oldtype：每个数据块由blocklength个oldtype类型的连续数据项组成。

stride：两个连续数据块的起始位置之间的oldtype类型元素的个数。因此，两个块之间的间隔可以由(stride-blocklength)来表示。

MPI_Type_struct

消息标签

当发送者连续发送两个相同类型消息给同一个接收者，如果没有消息标签，接收者将无法区分这两个消息。

消息标签使得服务进程可以对两个不同的用户进程分别处理，提高灵活性。

MPI_ANY_TAG：通配符，表示与任何tag都可以匹配。

通信域

通信域(Communicator)包括进程组(Process Group)和通信上下文(Communication Context)等内容，用于描述通信进程间的通信关系。

通信域分为组内通信域和组间通信域，分别用来实现MPI的组内通信(Intra-communication)和组间通信(Inter-communication)。

进程组是进程的有限、有序集。

有限：在一个进程组中，进程的个数n是有限的，这里的n称为进程组大小(Group Size)。

有序：进程的编号是按0，1，…，n-1排列的。

一个进程用它在一个通信域(组)中的编号进行标识。组的大小和进程编号可以通过调用以下的MPI函数获得：

通信上下文：安全的区别不同的通信以免相互干扰

通信上下文不是显式的对象，只是作为通信域的一部分出现。

通信域：进程组和通信上下文结合形成了通信域

一个在MPI中创建新通信域的例子

MPI_Comm_dup和MPI_Comm_split函数

组间通信域

组间通信域是一种特殊的通信域，该通信域包括了两个进程组，分属于两个进程组的进程之间通过组间通信域实现通信。

一般把调用进程所在的进程组称为本地进程组，而把另外一个称为远程进程组。

消息状态

消息状态(MPI_Status类型)存放接收消息的状态信息。

是消息接收函数MPI_Recv的最后一个参数。

其中包括：

当一个接收者从不同进程接收不同大小和不同标签的消息时，消息的状态信息非常有用。

假设多个客户进程发送消息给服务进程请求服务，通过消息标签来标识客户进程，从而服务进程采取不同的服务：

点对点通信

MPI的点对点通信(Point-to-Point Communication )同时支持多种通信模式。

通信模式

指的是缓冲管理，以及发送方和接收方之间的同步方式。

同步模式、缓冲模式、标准模式、就绪模式。

也提供了阻塞和非阻塞两种通信机制。

通信模式和通信机制相结合，就产生了非常丰富的点对点通信函数。

通信模式

同步通信模式

只有相应的接收过程已经启动，发送过程才正确返回。

同步发送返回后，表示发送缓冲区中的数据已经全部被系统缓冲区缓存，并且已经开始发送。

同步发送返回后，发送缓冲区可以被释放或者重新使用。

缓冲通信模式

缓冲通信模式的发送不管接收操作是否已经启动都可以执行。

（即存在大块缓冲区，不是很害怕上次发送的数据丢包）

但是需要用户程序事先申请一块足够大的缓冲区，通过MPI_Buffer_attch实现，通过MPI_Buffer_detach来回收申请的缓冲区。

标准通信模式

是否对发送的数据进行缓冲由MPI的实现来决定，而不是由用户程序来控制。

发送可以是同步的或缓冲的，取决于实现。

就绪通信模式

发送操作只有在接收进程相应的接收操作已经开始才进行发送。

当发送操作启动而相应的接收还没有启动，发送操作将出错。就绪通信模式的特殊之处就是接收操作必须先于发送操作启动。

通信机制

阻塞和非阻塞通信的主要区别在于返回后的资源可用性。

阻塞通信

阻塞通信返回的条件：

1、通信操作已经完成，即消息已经发送或接收。

2、调用的缓冲区可用。若是发送操作，则该缓冲区可以被其它的操作更新；若是接收操作，该缓冲区的数据已经完整，可以被正确引用。

非阻塞通信

非阻塞通信返回后并不意味着通信操作的完成。

MPI还提供了对非阻塞通信完成的检测，主要的有两种MPI_Wait函数和MPI_Test函数。

而MPI的接收操作只有两种：阻塞接收和非阻塞接收。

点对点通信函数

重叠计算与通信

在阻塞通信的情况下，通信还没有结束的时候，处理器只能等待，浪费了计算资源。

一种常见的技术就是设法使计算与通信重叠，非阻塞通信可以用来实现这一目的。

非阻塞通信中，双缓冲是一种常用的方法。

例如：一条三进程的流水线，中间的进程连续地从左边的进程接收输入数据流，计算出结果，然后将结果发送给右边的进程。

需要为X和Y各自准备两个单独的缓冲，当接收进程向缓冲中放下一个X时，计算进程可能从另一个缓冲中读当前的X。

需要确信缓冲中的数据在缓冲被更新之前使用。

send_handle和revc_handle分别用于检查发送接收是否完成。

通过调用MPI_Wait(Handle, Status)来实现，该函数直到Handle指示的发送或接收操作已经完成才返回。

MPI_Test(Handle, Flag, Status)只测试由Handle指示的发送或接收操作是否完成，如果完成，就对Flag赋值True，这个函数不像MPI_Wait，它不会被阻塞。

Send-Recv函数

给一个进程发送消息，从另一个进程接收消息；

特别适用于在进程链（环）中进行“移位”操作，而避免在通讯为阻塞方式时出现死锁。

集合通信

集合通信：是一个进程组中的所有进程都参加的全局通信操作。

集合通信一般实现三个功能：通信、聚集和同步。

通信功能主要完成组内数据的传输。

聚集功能在通信的基础上对给定的数据完成一定的操作。

同步功能实现组内所有进程在执行进度上取得一致。

按照通信方向的不同，又可以分为三种：

一对多通信：一个进程向其它所有的进程发送消息，这个负责发送消息的进程叫做Root进程。

多对一通信：一个进程从其它所有的进程接收消息，这个接收的进程也叫做Root进程。

多对多通信：每个进程都向其它所有的进程发送或者接收消息。

集合通信函数

广播MPI_Bcast

广播是一对多通信的典型例子，其调用格式如下：

Root进程发送相同的消息给通信域Comm中的所有进程。

消息的内容如同点对点通信一样由三元组<Address, Count, Datatype>标识。

对Root进程来说，这个三元组既定义了发送缓冲也定义了接收缓冲。对其它进程来说，这个三元组只定义了接收缓冲。

收集MPI_Gather

收集是多对一通信的典型例子，其调用格式下:

Root进程从进程域Comm的所有进程(包括它自已)接收消息。

消息按照进程的标识rank排序并进行拼接，然后存放在Root进程的接收缓冲中。

接收缓冲由三元组<RecvAddress, RecvCount, RecvDatatype>标识，发送缓冲由三元组<SendAddress, SendCount, SendDatatype>标识，所有非Root进程忽略接收缓冲。

散播MPI_Scatter

散播也是一个一对多操作，其调用格式如下:

Scatter执行与Gather相反的操作。

Root进程给所有进程(包括它自已)发送不同的消息，这n (n为进程域comm包括的进程个数)个消息在Root进程的发送缓冲区中按进程标识的顺序有序地存放。

接收缓冲由三元组<RecvAddress, RecvCount, RecvDatatype>标识，非Root进程忽略发送缓冲。Root进程的发送缓冲由三元组<SendAddress, SendCount, SendDatatype>标识。

全局收集MPI_Allgather

全局收集多对多通信的典型例子，其调用格式如下：

Allgather操作相当于每个进程都作为Root进程执行了一次Gather调用，即每一个进程都按照Gather的方式收集来自所有进程(包括自己)的数据。

全局交换MPI_Alltoall

全局交换也是一个多对多操作，其调用格式如下：

每个进程发送一个消息给所有进程(包括它自已)。

n (n为进程域comm包括的进程个数)个消息在发送缓冲中以进程标识的顺序有序地存放。从接收角度看，每个进程都从所有进程接收一个消息，这n个消息以标号的顺序被连接起来，存放在接收缓冲中。

全局交换等价于每个进程作为Root进程执行了一次散播操作。

集合同步函数

路障MPI_Barrier

同步功能用来协调各个进程之间的进度和步伐。目前MPI的实现中支持一个同步操作，即路障同步(Barrier)。

路障同步的调用格式如下:

在路障同步操作MPI_Barrier(Comm)中，通信域Comm中的所有进程相互同步。

在该操作调用返回后，可以保证组内所有的进程都已经执行完了调用之前的所有操作，可以开始该调用后的操作。

集合聚集操作

集合通信的聚集功能使得MPI进行通信的同时完成一定的计算。

MPI聚合的功能分三步实现：

首先是通信的功能，即消息根据要求发送到目标进程，目标进程也已经收到了各自需要的消息；

然后是对消息的处理，即执行计算功能；

最后把处理结果放入指定的接收缓冲区。

MPI提供了两种类型的聚集操作: 归约和扫描。

归约MPI_Reduce

归约的调用格式如下:

归约操作取每个进程的发送缓冲区(SendAddress)中的对应位置数据按给定的操作进行运算，并将最终结果存放在Root进程的对应接收缓冲区位置(RecvAddress)中。

（原话：归约操作对每个进程的发送缓冲区(SendAddress)中的数据按给定的操作进行运算，并将最终结果存放在Root进程的接收缓冲区(RecvAddress)中。）

参与计算操作的数据项的数据类型在Datatype中定义，归约操作由Op定义。

归约操作可以是MPI预定义的,也可以是用户自定义的。

归约操作允许每个进程提供向量值，而不只是标量值，向量的长度由Count定义。

int MPI_Reduce(
    const void* SendAddress,  // 发送缓冲区的起始地址
    void* RecvAddress,        // 接收缓冲区的起始地址（仅根进程有效）
    int Count,               // 每个进程参与归约的元素数量
    MPI_Datatype Datatype,    // 数据类型（如 MPI_INT, MPI_FLOAT）
    MPI_Op Op,               // 归约操作（如 MPI_SUM, MPI_MAX）
    int Root,                // 根进程的秩（Rank）
    MPI_Comm Comm            // 通信子（如 MPI_COMM_WORLD）
);

Count：表示每个进程发送到归约操作中的数据元素的数量。