并行处理及分布式系统

1 为什么要并行计算

1.1 为什么需要不断提升性能

• 随着计算能力的增加，我们所面临的计算问题和需求也在增加
• 随着技术的进步，我们从未想过的技术得到了解决，比如：人类基因解码、更准确的医疗成像、更快速准确的网络搜索…
• 更复杂的问题仍有待解决，比如：气候模拟、蛋白质折叠、药物发现、能源研究、数据分析…

1.2 为什么要构建并行系统

单处理器性能大幅度提升的主要方法是增加集成电路晶体管密度。但是随着晶体管尺寸的减小，晶体管的传递速度增快，它们的能耗也在增加，大多数的能量是以热能的形式消耗，当一块集成电路变得太热的时候，就会变得不可靠。在 21 世纪的第一个 10 年中，使用空气冷却集成电路的散热能力已达到极限。也就是说，只通过增加集成电路的速度来提升处理器的性能的方法不可取。在这种条件下，集成电路制造商提出多核处理器的思路。

1.3 为什么要编写并行程序

大多数为传统单核系统编写的程序无法利用多核处理器，为了使程序能够更快地运行，有更加逼真的图像，就需要将串行程序改写为并行程序。

1.4 如何编写并行程序

想要解决某个问题，需要编写其对应的并行程序，首先需要对任务进行划分，确定其属于任务并行还是数据并行。

• 任务并行：当许多任务或函数可以独立地、大规模地并行执行时，这就是任务并行。任务并行的重点在于利用多核系统对任务进行分配，将待解决的问题所需要的执行的各个任务分配到各个核上执行。
• 数据并行：当可以同时处理许多数据时，这就是数据并行。数据并行的重点在于利用多核系统对数据进行分配，每个核在分配到的数据集上执行大致相似的数据操作

1.5 接下来做什么

首先我会参考《并行程序设计导论》所讲的 C 语言的三种拓展：消息传递接口(Message-Passing Interface，MPI)、POSIX 线程(POSIX threads，Pthreads) 和 OpenMP 来编写基本的并行程序。

选择并行程序实现框架的时候应该根据计算机的架构来选择，即根据硬件选择软件。Pthreads 和 OpenMP 是为 共享内存系统 的编程而设计的，它们提过访问共享内存的机制；而 MPI 是为 分布式内存系统 的编程而设计的，它提供发送消息的机制。

图中(a)表示共享内存系统，(b)表示分布式内存系统。

1.6 并发、并行、分布式

• 并发计算：一个程序的多个任务再同一个时段内可以同时执行
• 并行计算：一个程序通过多个任务紧密协作来解决某个问题
• 分布式计算：一个程序需要与其他程序写作来解决某个问题

2 并行硬件和并行软件

2.1 背景知识

并行计算涉及到两个不同的技术领域：

• 计算机架构(硬件)
• 并行程序设计(软件)

硬件主要的目标就是为软件提供更快的计算速度，更低的性能功耗比，硬件结构上支持更快的并行。
软件的主要目的是使用当前的硬件压榨出最高的性能，给应用提供更稳定快速的计算结果。

2.1.1 冯 · 洛依曼结构

经典的冯 · 洛依曼结构包括存储器、运算器、控制器、输入设备、输出设备，其中运算器和控制器都在 CPU 之中，CPU 和主存通过总线连接。当数据或指令从主存传送到 CPU 时，称为数据或指令从内存中取出或者读出；当数据或指令从 CPU 传送到主存时，称为数据或指令写入或者存入内存中。这样主存和 CPU 之间的分离称为 冯 · 洛依曼瓶颈。

2.1.2 进程、多任务及线程

• 进程：正在运行的程序的一个实例。

• 多任务：通过时间片轮转的方式使人产生多个任务同时执行的错觉。

• 线程：线程包含在进程中，同一个进程内的线程共享内存和 I/O 设备，利用线程程序员可以将程序划分为多个大致独立的任务。

2.2 对冯 · 洛依曼模型的改进

《并行程序设计导论》介绍了三种对冯 · 洛依曼模型的改进措施：缓存、虚拟内存、低层次并行

2.2.1 缓存(Cache)

基于访存局部性而设计的 CPU 缓存(CPU Cache)有着比其他存储器更小的访问开销，CPU Cache 通常和 CPU 位于同一块芯片上，访存开销比普通内存小很多。

局部性原理

• 访问一个位置之后，接着访问其附近的位置
• 空间局部性：访问临近的位置
• 时间局部性：最近访问的位置，在不久的将来还会访问

CPU Cache 一般分为不同的层(level)，第一层(L1)最小但是访问速度最快，更高层的 Cache (L2, L3, …)更大但访问速度较慢。大多数系统采用 3 层 Cache，每层 Cache 中的数据不重合，且都会存放在主存中。

当 CPU 需要访问数据或指令时，它会沿着 L1 Cache -> L2 Cache -> L3 Cache -> 主存 这条路径查询，若从 Cache 中查询到数据或指令时，则称为 Cache 命中 或 命中；若没有从 Cache 中查询到则称为 Cache 缺失 或 缺失。

当 CPU 向 Cache 写数据时，会出现 Cache 中的值与主存中的值不一致的情况，为了解决这个问题，数中介绍了两种方法：

• 写直达：当 CPU 向 Cache 写数据时，更新主存中的数据。
• 写回：将 Cache 中的数据标记为 脏数据，当 Cache line 被主存中的新的 Cache line 替换时，脏的 Cache line 会被写入主存。

在 Cache 设计中，另一个问题是 Cache line 应该存储在什么位置。当从主存中取出一个 Cache line 时，应该把这个 Cache line 放到 Cache 中的什么位置，不同的系统采用不同的方式，这些方式分别为：

• 全相联：一个新的 Cache line 可以放在 Cache 中的任意位置
• 直接映射：每一个 Cache line 在 Cache 中都有唯一的位置
• n路组相联：每个 Cache line 可以被放在 n 个不同的位置中的一个

当主存中的行能被映射到不同到 Cache 中的不同位置时，需要决定替换或者驱逐 Cache 中的某一行。常用的方案是最近最少使用。

2.2.2 虚拟内存

如果一个大型的程序或者程序需要访问大型数据集，那么所有的指令或者数据可能在主存中放不下。采用 虚拟内存，使得主存可以作为辅存的缓存。利用时空局部性的原理，只把正在运行程序的活动部分保存在主存中。

2.2.3 低层次并行

指令级并行

指令级并行通过让多个处理器部件或者功能单元同时执行指令来提高处理器的性能。有两种主要方法来实现指令级并行：

• 流水线：将功能单元分阶段安排。
• 多发射：让多条指令同时启动。
  • 静态多发射：功能单元在编译时调度
  • 动态多发射：功能单元在运行时调度

硬件多线程

硬件多线程为系统提供了一种机制，使得当前执行的任务被阻塞时，系统能够继续其他有用的工作。

• 细粒度多线程：处理器在每条指令执行完后切换线程，从而跳过被阻塞的线程。
• 粗粒度多线程：只切换那些需要等待较长时间才能完成操作而被阻塞的线程。
• 同步多线程：通过允许多个县城同时使用多个功能单元来利用超标量处理器的性能。

2.3 并行硬件

利用 Flynn 分类法 对计算机体系结构进行划分：

分别以数据和指令进行分析：

• 单指令单数据 SISD (传统串行计算机，386)
• 单指令多数据 SIMD (并行架构，比如向量机，所有核心指令唯一，但是数据不同，现在 CPU 基本都有这类的向量指令)
• 多指令单数据 MISD (少见，多个指令围殴一个数据)
• 多指令多数据 MIMD (并行架构，多核心，多指令，异步处理多个数据流，从而实现空间上的并行，MIMD 多数情况下包含 SIMD，就是 MIMD 有很多计算核，计算核支持 SIMD)

注：GPU 属于 SPMD，但是其可以使用 SIMD 并行

计算机架构也可以 根据内存划分：

• 共享内存系统
  
• 分布式内存系统
  

2.4 并行软件

负载均衡：将任务在线程或进程之间分配，并使得每个进程或线程获得大致相等的工作量。

将串行程序或者算法转换为并行程序的过程称为 并行化。某些程序，如果能够通过简单地将会任务分配给进程或线程来实现并行化，我们称该程序是 易并行的。

动态线程：

• 主线程等待工作请求，当一个请求到达时，它会派生出一个新线程来执行该请求。当新线程完成任务后，就会终止执行再合并到主线程中。
• 资源的有效使用，但是线程的创建和终止非常耗时。

静态线程：

• 创建线程池并分配任务，但线程不被终止直到被清理。

• 性能更好，但可能会浪费系统资源。

非确定性：在任何一个 MIMD 系统中，如果处理器异步执行，那么很可能会引发 非确定性。给定的输入能产生不同的输出，这种计算称为非确定性。

临界区：一次只能被一个线程执行的代码块。访问临界区的行为应该是 互斥的。

保证互斥执行的最常用机制是 互斥锁 或者 互斥量。

2.5 输入和输出

为了解决多个进程或线程直接输入或输出的矛盾，需要遵循以下规则：

• 在分布式内存程序中，只有进程 0 能够访问 stdin。在共享内存程序中，只有主线程或线程 0 能够访问 stdin。
• 在分布式内存和共享内存系统中，所有进程或线程都能够访问 stdout 和 stderr。
• 但是，因为输出到 stdout 的非确定性顺序，大多数情况下，只有一个进程或线程会将结果输出到 stdout。但输出调试程序的结果是一个里外，在这种情况下，允许多个进程或线程写 stdout
• 只有一个进程或线程会尝试访问一个除 stdin、stdout 或者 stderr 外的文件。
• 调试程序输出在生成输出结果时，应该包括进程或线程的序号或者进程标识符。

2.6 性能

线性加速比：$T_{并行}=T_{串行}/p$，其中 $p$ 表示程序运行所运行的系统的核数。

加速比：
$$S=\frac{T_{并行}}{T_{串行}}$$
并行程序的效率：
$$E=\frac{S}{P}=\frac{T_{串行}}{p\cdot T_{并行}}$$
并行开销的影响：
$$T_{并行}=T_{串行}/p+T_{开销}$$

阿姆达尔定律：

除非一个串行程序的执行几乎全都并行化，否则，不论有多少可以利用的核，通过并行化所产生的加速比都会是受限的。

假设原串行程序所需时间为 $T_{串行}$，其中的 $\alpha$ 的比例能够并行化，假设并行化的这一部分使用 $p$ 个核，则程序中可以并行化的部分的加速比为 $p$。当 $p$ 趋于无穷大时，该程序的加速比为：
$$S_{\infty }=\frac{1}{1-\alpha }$$
假设该程序可并行化部分并行化之后，其整体的加速比为：
$$S=\frac{T_{串行}}{\alpha \times T_{串行}/p+(1-\alpha )\times T_{串行}}=\frac{1}{\alpha /p+(1-\alpha )}$$
所以可得：
$$S\le \frac{1}{1-\alpha }$$

可扩展性

假设我们运行一个拥有固定进程或线程数目的并行程序，并且它的输入规模也是固定的，那么我们可以得到一个效率值 $E$。现在，我们增加该程序所用的进程或线程数，如果在输入规模也以相应增长率增加的情况下，该程序的效率一直都是 $E$，那么我们就称该程序是 可拓展的。

如果在增加进程或线程的个数时，可以维持固定的效率，却不增加问题的规模，那么程序称为 强可拓展性的。

如果在增加进程或线程个数的同时，只有以相同倍率增加问题的规模才能使效率值保持不变，那么程序就称为 弱可拓展的。

2.7 并行程序设计

Foster 方法

• 划分 问题并识别任务：将要执行的指令和数据按照计算拆分为多个小任务。这一步的关键在于识别出可以并行执行的任务。
• 在任务中识别要执行的 通信：确定前一步所识别出来的任务之间需要执行哪些通信。
• 凝聚 或 聚合 任务使之变成较大的组任务：将第一步中确定的任务和通信合并成更大的任务。
• 将聚合任务 分配 给进程或线程：将聚合好的任务分配给进程或线程，还要使通信最小化，使得每个进程或线程得到的工作量大致均衡(负载均衡)。

3 MPI编程

MPI 是为 分布式内存系统 的编程而设计的，它提供发送消息的机制。本节将会介绍怎么利用 MPI 使用 消息传递 来对分布式内存系统进行编程。

3.1 预备知识

头文件

#include <mpi.h>

编译

mpicc -g -Wall -o outputname.out filename.c

执行

mpiexec -n <number of processes> <executable>

例如：

mpiexec -n 4 ./mpi_hello.out

运行 mpi_hello.out 文件并开启 4 个进程。

程序框架

//...
#include <mpi.h>
//...
int main(int argc, char *argv[])
{//...MPI_Init(&argc, &argv);//...MPI_Finalize();//...return 0;
}

通信子

int my_rank;//进程编号
int comm_sz;//进程数量
MPI_Comm_rank(MPI_COMM_WORLD, &my_rank);
MPI_Comm_size(MPI_COMM_WORLD, &Comm_sz);

其中 MPI 创建，由所有进程组成的通信子，称为 MPI_COMM_WORLD。

SPMD 程序

• 单程序多数据流
• 只编译一个程序
• 进程 0 做一些不同的事情
• if-else 结构使程序是 SPMD

通信

MPI_Send(send_buf_p, send_buf_sz, send_type, dest, send_tag, send_comm);//q 号进程调用
MPI_Recv(recv_buf_p, recv_buf_sz, recv_type, src, recv_tag, recv_comm, &status);//r 号进程调用

则 q 号进程调用 MPI_Send 函数所发送的消息可以被 r 号进程调用 MPI_Recv 函数接受，如果：

• recv_comm = send_comm
• recv_tag = send_tag
• dest = r
• src = q

MPI_Recv(result, result_sz, result_type, MPI_ANY_SOURCE, result_tag, comm, MPI_STATUS_IGNORE);

当设置 src 为 MPI_ANY_SOURCE 时，该进程接收所有进程发送给他的信息。

集合通信

集合通信 不同于只涉及两个进程的 MPI_Send 和 MPI_Recv，它涉及到一个通信子汇总的所有进程。为了区分这两种通信方式，MPI_Send 和 MPI_Recv 常常称为 点对点通信。

4 Pthreads编程

4.1 预备知识

头文件

#include <pthread.h>

编译

gcc -g -Wall -o outputname.out filename.c -lpthread 

执行

./filename.out <number of threads>

例如，运行 4 个线程的程序：

./filename.out 4

4.2 竞争条件

当多个线程同时执行时，多个线程执行语句的顺序通常是非确定的。当多个线程试图访问同一个共享资源时，并且其中至少有一个访问是更新操作，这样的访问可能会导致错误，导致结果的不确定性，我们称这种现象为 竞争条件。编写共享内存程序时最重要的任务之一就是识别和更正竞争条件。

4.3 临界区

临界区 是一个代码块，在这个代码块中，任意时刻还有一个线程能够更新共享资源，因此临界区中的代码执行应该作为串行代码执行。因此在设计程序时，应该尽可能少地使用临界区，并且使用的临界区应该尽可能短。

有三种避免对临界区竞争访问的基本方法：忙等待、互斥量和信号量。

4.4 忙等待

在忙等待中，线程不停地测试某个条件，但实际上，直到某个条件满足之前，不会执行任何有用的工作。

但是要注意编译器的优化会影响忙等待的正确执行。

4.5 互斥锁

互斥量 是互斥锁的简称，它是一个特殊类型的变量，通过某些特殊类型的函数，互斥量可以用来限制每次只有一个线程能进入临界区。互斥量保证了一个线程独享临界区，其他线程在有线程已经进入该临界区的情况下，不能同时进入。

4.6 信号量

产生原因：

• 忙等待强制顺序线程访问临界区，造成资源浪费。

• 使用互斥量，顺序由系统自己决定。

• 在一些应用程序中，我们需要控制线程访问临界区的顺序。

5 OpenMP编程

5.1 预备知识

预处理器指令：#pragma

编译

gcc -g -Wall -fopenmp -o outputname.out filename.c

执行

./filename.out <number of processes>

例如：

./omp_hello.out 4

程序

最基本的 parallel 指令可以以如下简单的形式表示：

#pragma omp parallel

子句

许多 OpenMP 指令可以被 子句 修改。使用最频繁的是 num_threads 子句，当时用 OpenMP 指令启动线程组时，可以通过修改 num_threads 子句来启动需要数目的线程。

6 并行程序开发

7 代码附录

梯形积分法 MPI 程序

矩阵向量乘

通过数学求和公式计算π

蒙特卡洛方法计算π

奇偶交换排序