第二章 - I - MPI简介：消息传输接口
并行计算抽象模型
- 向量超级计算机：基于单指令多数据(SIMD)*编程模型，使用流水线操作优化代码
SIMD指一类能够在单个指令周期内同时处理多个数据元素的指令集，利用的是数据级并行来提高运行效率，典型的代表由Intel的MMX和SSE指令系列。这类指令的使用环境是对多个数据进行同一种处理，因此典型的应用场景就是多媒体领域，特别是在其中的编解码流程中。
- 多核计算机：共享内存，多线程编程。程序容易崩溃，且有时会在并发访问共享资源出现冲突而难以调试
- 计算机集群：多计算机的分布式内存 + 高速网络互联
关注最后一种并行计算模型
MPI介绍
MPI中文为“消息传递接口”，是一种应用程序编程接口(API)，通过发送和接收封装了数据的消息，MPI可以用于编写可交换数据的并行程序。
MPI编程接口不依赖底层编程语言，故可以通过常用的串行编程语言（C/C++, Fortran, Java, Python等）使用MPI命令，有多种MPI绑定语言可用。目前最新版本的MPI标准为第4版(2021.6发布)
并行编程模型
- 目前的操作系统都是多任务的，但是一个核上一次只能执行一个程序指令，而其他进程被阻塞（暂停/等待唤醒），任务调度程序的作用是将进程动态分配给CPU
- 现代CPU拥有多个核，每个核都是独立处理单元(PU)，可以并行地在每个核上执行一个线程
进程(Process)：是并发执行的程序在执行过程中分配和管理资源的基本单位，是一个动态概念，竞争计算机系统资源的基本单位。
线程(Thread)：进程中的一个执行任务（控制单元），负责当前进程中程序的执行。一个进程至少有一个线程，一个进程可以运行多个线程，多个线程可共享数据。
并发(Concurrency)：在操作系统中，并发是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行。（在一个处理器上排队很多个进程，处理器将时间划分成很多小段，这一段给A处理，下一段给B处理，处理某个进程时别的进程处于休眠状态）
并行(Parallel)：当系统有一个以上CPU时，当一个CPU执行一个进程时，另一个CPU可以执行另一个进程，两个进程互不抢占CPU资源，即在同一时刻，有多条指令在多个处理器上同时执行。
- 多核构架产生了允许并发的多线程编程范式，分配给同一进程的资源在不同线程之间共享，且至少一个线程具有main调用函数
- 多线程编程模型非常适合多核处理器，可让应用程序运行更快
- 进程有非重叠的内存区域，故而进程之间的通信必须谨慎，尤其是使用MPI标准时
线程的特点
同一进程的线程共享相同内存区域，包括数据区域与代码区域，故同一进程下的线程之间可以互相访问数据，但这时也会出现一些问题，严重时会导致系统崩溃。
在并行随机存取机模型(PRAM)中，同时对本地内存进行读写操作可能发生三类冲突：
- 互斥读互斥写
- 同时读互斥写
- 同时读同时写
可以在同一处理器（多核时并行处理）或在同一网络下互联的一组处理器上运行多个进程，也可以编写程序来使用若干多核处理器（同时使用MPI和OpenMP标准）
进程之间的全局通信
通过在一组机器上执行一个MPI程序，我们启动一组进程，每个进程都有类似于通常的串行程序的本地计算，同时还会执行下列操作：
- 数据传输：如一些数据通过消息传送到所有其他进程
- 同步屏障：导致所有进程在运行前都需要等待
- 全局计算：例如，一种归约操作，用储存在每个进程本地内存中的本地值计算属于所有进程的分布式变量的最小值或者和。全局计算依赖于互联集群计算机的底层拓扑
全局通信原语由属于同一个通信组的所有进程执行。默认MPI初始化后所有进程都属于一个名为MPI_COMM_WORLD的通信组。
基本MPI原语
- 广播
MPI_Bcast：从根进程（通信组当前调用MPI的进程）向同一通信组内所有其他进程发送信息
- 归约/聚合
MPI_Reduce：将变量的所有对应值汇集到一个值中并返回给当前调用进程。MPI中，MPI_Reduce可以通过归约一个使用可交换二元运算符的变量执行全局计算操作。预定义的MPI归约二元运算符有：
MPI_MAX 最大值\quad MPI_SUM 求和 \quad MPI_LAND 逻辑与\quad MPI_LOR 逻辑或 \quad MPI_LXOR 逻辑异或
MPI_MIN 最小值 \quadMPI_PROD 求积\quadMPI_BAND 按位与\quad MPI_BOR 按位或 \quad MPI_BXOR 按位异或
MPI_MAXLOC 最大值和相应位置
MPI_MINLOC 最小值和相应位置
- 散播
MPI_Scatter：将不同的个性化信息发到其他每个进程中
- 收集：散播的逆过程，根进程从所有其他进程中接收个性化消息
- 全交换
MPI_ALL-toall：每个进程向其他所有进程发送个性化消息
阻塞与非阻塞
MPI有多种发送模式，这取决于数据是否被缓冲，以及是否需要同步。我们从最基本的两个通信原语开始：
Send(&data, n, Pdest)：把内存地址&data开始的含有n个数据的数组发送到进程Pdestreceive(&data, n, Psrc)：从进程Psrc接收n个数据，并将它们存储在一个从本地内存地址&data开始的数组中
举一个例子：
//Process P0
...
a = 442;
send(&a, 1, P1);
a = 0;
//Process P1
...
receive(&A, 1, P0);
cout << A << endl; //输出A后换行
阻塞通信（非缓冲）产生了等待时间(空闲时间)：发送进程和接收进程需要互相等待对方——这种通信模式称为“握手”
握手模式允许执行同步通信，有三种情况
- 发送进程发送请求后等待接收进程确认，发送进程进入等待时间(阻塞send操作)
- 接收进程运行到接收指令时发送进程还未发送请求，接收进程进入等待时间(阻塞receive操作)
- 发送进程发送请求时接收进程恰好运行到接收指令，即刻确认通过，没有等待时间（最理想的情况）
显然，对于阻塞通信，要尽量减少总等待时间。
使用阻塞通信会正确地匹配发送和接收语句，但有时候也会发生“死锁”，如下面这个例子
//Process P0
...
send(&a, 1, P1);
receive(&b, 1, P1);
//Process P1
...
send(&a, 1, P0);
receive(&b, 1, P0);
进程P0发送一个消息，然后等待P1返回“同意发送”的指令，但此时P1的发送语句也在等待P0的“同意发送”指令，这便是一个“死锁”情况。
实际上，MPI中每个发送/接收操作涉及一组通信，并有一个标签属性（一个整形数据）。
阻塞通信可以确保程序一致性（避免让消息以错误的顺序到达），但是难以检测死锁。
为减少死锁情况，可以预先给每个进程在内存上分配一个专用的数据缓冲区(Data Buffer, DB)，然后分两步发送：
- 发送进程在数据缓存区发送消息
- 接收进程在地址&data指向的本地内存区域上复制上述数据缓存区的信息
但是，当缓冲区变满（缓冲区溢出异常）时仍然存在潜在的死锁情况。
上述操作是针对send原语阻塞的改进。同样的如果receive原语阻塞，仍然存在死锁的情况，如下例所示：
//Process P0
...
receive(&b, 1, P1);
send(&a, 1, P1);
//Process P1
...
receive(&b, 1, P0);
send(&a, 1, P0);
这个例子中，每个进程在发送消息前需要等待一个指令，也是一个死锁状态。
当考虑像Bcast这种全局通信，为保证消息以正确顺序到达，阻塞通信非常有用；但是实现算法时必须注意潜在的死锁。
解决死锁的一个方案是让send和receive原语成为非阻塞的——引入非阻塞通信，即异步通信：
由Isend和Ireceive表示，其运行模式如下：
- 发送进程发布一条“发送授权请求”（挂起）的消息，并继续其程序的执行
- 接受进程发布“同意发送”许可指令，开始传输数据
- 数据传输完成时，检查状态并指示进程是否可以安全地进行读/写操作
并发性
处理单元可以在同一时间内运行多个任务，如在进行非阻塞通信操作时也可以做据不计算。我们要求MPI_IRcev MPI_ISend和局部计算互不干涉，可以用双竖线表示这些并发计算，如
IRecv || ISend || Local_Computation
单向与双向通信
顾名思义
- 单向通信：通信信道中消息只能单个方向进行通信，即要么发送
MPI_Send，要么接收MPI_Rcev，不能同时进行
- 双向通信：进程间可以同时接收和发送信息，用
MPI_Sendrecv完成
全局计算
归约：MPI中可以进行类似于累加V=\sum_{i=0}^{P-1}v_i和累乘V=\prod_{i=0}^{P-1}v_i的全局计算，其中v_i为储存在进程P_i中的局部变量。这个全局计算结果V可以从调用了该归约原语的进程（当前调用进程/根进程）的本地内存中获得。归约原语的使用方法如下
#include <mpi.h>
int MPI_Reduce(
void* sendBuffer, //指向发送消息的内存块的指针
void* recvBuffer, //指向接收（输出）消息的内存块的指针
int count //数据量(数组元素个数)
MPI_Datatype datatype //MPI数据类型（如MPI_INT等）
MPI_OP op //MPI规约操作（如MPI_SUM等）
int root, //提取结果进程（根进程）的进程号
MPI_Comm comm //MPI通信域（指定通信范围，如默认的MPI_COMM_WORLD）
);
归约操作是预定义的，有现成的关键词供选用。
MPI中，也可以给归约操作建立数据类型并定义关联和交换二元运算符。
并行前缀/扫描：扫描Scan操作计算存储在进程中的本地数据的所有部分归约操作。可以将扫描看作是一种特殊的归约，即每一个进程都对排在它前面的进程进行归约操作。这种操作能够减小求和复杂度(O(n)\rightarrow O(\log n))
前缀和(prefix sum)：若给定数组a[n]，定义其前缀和为另一个数组S[n]，其中
S[i]=\sum_{j=0}^{i-1}a[j]，\qquad i=0,1,...,n-1
int MPI_Scan(
void* sendBuffer, //发送消息缓冲区的起始地址(可选)
void* recvBuffer, //接收消息缓冲区的起始地址(可选)
int count,
MPI_Datatype datatype,
MPI_Op op,
MPI_Comm comm)
举个例子：假定有3个进程P_0\sim P_2，其中有一个名为vals的长度为4的整型数组，将扫描操作储存在每个进程的cumsum对应的数组中，则指令为
int MPI_Scan(&vals, &cumsum, 4, MPI_INT, MPI_SUM, MPI_COMM_WORLD)
记进程P_i中的vals = [a_i, b_i, c_i, d_i]，则
P_0：cumsum = [a_0, b_0, c_0, d_0]
P_1：cumsum = [a_0+a_1, b_0+b_1, c_0+c_1, d_0+d_1]
P_2：cumsum = [a_0+a_1+a_2, b_0+b_1+b_2, c_0+c_1+c_2, d_0+d_1+d_2]
通信域与通信组
MPI中，通信域（通信器，communicator）可以将金成分为不同通信组，每个进程都在一个通信组中，并通过通信组内部的进程标识号索引。默认情况下，MPI_COMM_WORLD包含标识号为0\sim P-1的整型数字的所有进程。
使用原语int MPI_Comm_size(MPI_Comm comm, int *size)和int MPI_Comm_Rank(MPI_Comm comm, int *size)来获取通信组内部进程数量和通信组内部进程标识号——MPI中rank表示进程标识号
同步屏障
粗粒度并行模式中，进城之间独立执行大量计算块，然后在同步屏障MPI_Barrier处互相等待，执行接收、发送消息，消息传递后继续各自的程序执行——可以理解成人为为不同进程设置一个交换站，所有相关进程都到达后才一起交换消息，而后各自继续运行。
整体同步并行计算模型(BSP)：引入由三个基本步骤组成的“超步骤”，促进并行算法设计：
- 并发计算步骤：进程进行局部异步计算，且局部计算可以与通信重叠
- 通信步骤：进程间互相交换数据
- 同步屏障步骤：进程达到同步屏障后，等待其他所有进程到达该屏障，然后再一同进入另一个超步骤
