并行初探

一些笔记整理

1. 基础认知

1.1 如何编写并行程序

基本思想：将要完成的任务分配给多个核。

两种广泛的方法：任务并行和数据并行

任务并行

将待解决问题所需要执行的各个任务分配到各个核上执行。（执行不同的指令）

数据并行

将待解决问题所需要处理的数据分配给各个核，每个核在分配到的数据集上执行大致相似的操作。

1.2 两种并行内存系统

共享内存系统

各个核能够共享到计算机的内存。

（比如Pthreads和OpenMP就是为此设计）

分布式内存系统

每个核拥有自己的私有内存，核之间的通信是显式的，必须使用类似络中发送消息的机制。

（MPI就是为分布式内存编程而设计）

1.3 目前关注的扩展

消息传递接口MPI(Message-Passing Interface)
POSIX线程Pthreads(POSIX threads)
OpenMP

1.4 指令级并行(ILP)

Instruction-Level parallelism

通过让多个处理器部件或者功能单元同时执行指令来提高处理器的性能。

认知：指令级并行很难利用，因为程序中有许多部分之间存在依赖关系。

两种主要的方法：流水线和多发射。

1.4.1 流水线

此处不详细表述。

通过将功能分成多个单独的硬件或者功能单元，并把它们按顺序串接起来提高性能。

1.4.2 多发射

通过复制功能单元来同时执行程序中的不同指令。

静态多发射

功能单元在编译时调度

ps：先编译成固定顺序，CPU再按顺序执行

动态多发射

功能单元在运行时间调度

ps：处理器自动判断哪些指令可以并行

系统必须找出能够同时执行的指令，其中一种最重要的技术是：预测。

1.5 硬件多线程

线程级并行TLP：通过同时执行不同线程来提供并行性。与ILP相比，TLP提供了粗粒度的并行性，即同时执行的程序基本单元（线程）比细粒度的程序单元（单条指令）更大或更粗。

1.5.1 细粒度多线程

处理器在每条指令执行完后切换线程，从而跳过被阻塞的线程。

缺陷：执行很长一段指令的线程，在执行每条指令的时候都需要等待。

1.5.2 粗粒度多线程

为了避免上述问题，只切换那些需要等待较长时间才能完成操作（比如从主存中加载）而被阻塞的线程。

ps：只有线程遇到一定时间的阻塞时，才会切换执行其他的线程。

优势：不需要线程间的立即切换，切换的次数少了。

但仍有切换，阻塞要等待，导致延迟。

1.5.3 同步多线程

模拟多核的原理。

略。

1.6 并行硬件

如果我们能够通过修改源代码来开发并行性，或者必须修改源代码来开发并行性，那么我们认为这种硬件是并行硬件。

Flynn分类法经常用来对计算机体系结构进行分类，依据是它能够同时管理的指令流数目和数据流数目。

SISD(经典冯诺依曼架构)、SIMD、MISD(不做讨论)、MIMD

典型的冯·诺依曼系统是单指令流单数据流SISD系统。它一次执行一条指令，一次存取一个数据项。

1.6.1 SIMD系统

单指令多数据流 Single Instruction, Multiple Data

通过对多个数据执行相同的指令，从而实现在多个数据流上的操作。

ps：就如同一个控制单元和多个ALU。

它适合对处理大型数组的简单循环实行并行化。通过将数据分配给多个处理器，然后让各个处理器使用相同的指令来操作数据子集实现并行，即数据并行。

经典的SIMD系统是：向量处理器。此外，图形处理单元GPU和台式机的CPU也利用了SIMD计算方面的知识。

SSE、AVX、CUDA、Xeon Phi

1.6.2 MIMD系统

多指令多数据流 Multiple Instruction, Multiple Data

该系统支持同时多个指令流在多个数据流上操作。

MIMD系统通常包括一组完全独立的处理单元（核），每个处理单元都有自己的控制单元和ALU。而且它通常是异步的，各个处理器能够按他们自己的节奏运行，不同处理器上的系统时间之间没有关联。

共享内存系统

一组自治的处理器通过互连络与内存系统相互连接，每个处理器能够访问每个内存区域。处理器通过访问共享的数据结构，从而进行隐式的通信。

一致内存访问系统UMA 和非一致内存访问系统 NUMA

详情见《并行程序设计导论》P23

分布式内存系统

每个处理器有自己私有的内存空间，对之间通过互连络相互通信。处理器之间通过发送消息或者使用特殊的函数来访问其他处理器地内存，从而进行显式的通信。

最广泛使用的分布式内存系统称为集群（clusters）。而事实上，这些系统中的节点，通常都是有一个或者多个多核处理器的共享内存系统。这种系统并非纯粹的分布式内存系统，称为混合系统。

1.6.3 互连络

互连络无论是在分布式内存系统还是在共享内存系统中，都扮演了一个决定性的角色。一个缓慢的互连络会严重降低除了简单并行程序外所有程序的整体性能。

共享内存系统的互连络和分布式内存系统的互连络是有区别的。

1.6.3.1 共享内存互连络

目前最常用的两种互连络是总线和交叉开关矩阵。

总线(BUS)

总线是由一组和组成的。

核心特征：

连接到总线上的设备共享通信线。

优点：低成本、灵活性，多个设备能够以较小的额外开销连接到总线上。

缺点：因为通信线是共享的，随着连接的设备增多，争夺总线概率增大，预期性能下降，处理器会经常等待访问内存。

因此，随着内存系统规模的增大，总线会迅速被交换互连络取代。

交叉开关矩阵(Crossbar)

交换互连络使用交换器来控制相互连接设备之间的数据传递。

交叉开关矩阵中，线表示双向通信线路，方块表示核或者内存模块，圆圈表示交换器。

交叉开关矩阵允许在不同设备之间同时进行通信，所以比总线快。但交换器和链路带来的开销也相对高。

一个小型的比相等规模的便宜。

1.6.3.2 分布式内存互连络

分布式内存互连络通常分成两种：直接互连与间接互连。

a. 直接互连

在直接互连中，每个交换器与一个对直接相连，交换器之间也相互连接。

环和二维环面络

环比简单的总线高级，因为它允许多个通信同时发生。在处理器必须等待其他处理器才能完成通信的情况下，制定通信方案会更容易。

在环中，每个交换器需要支持3个链路。// 在图中，连接到每一个圆圈的线，有3条，对应着3条双向通信线路，即3个链路。

环面络更加昂贵，因为交换器更加复杂，每个交换器需要能够支持5个链路。

如果有p个处理器，在环面络中链路的数目为3p，而在环中为2p。// 解释：因为直接互连意味着一个交换器连一个处理器-内存对，因此有p个处理器就有p个交换器。

等分宽度和等分带宽

衡量或者的一个标准——等分宽度。

想象并行系统被分成两部分，每部分都有一半的处理器或者节点，这两部分之间能够同时发生的通信数目（考虑最坏情况）。

如果认为以上说法不好判断的话，对于等分宽度的另一种计算方式为：

最少去除多少条线可以让两部分断开连接，去除的链路数就是等分宽度。

示例：对于正方形的二维环面络，有p = q^2 个节点（q为偶数）

等分宽度为
$2 p$
砍掉”中间“的水平链路和”回绕“的水平链路。

链路的带宽：是指它传输数据的速度。通常用兆位每秒或者兆字节每秒来表示。

等分带宽通常用来衡量络的质量。

等分带宽 = 等分宽度 * 每条线的带宽

示例：在一个环中。等分宽度为2。如果链路的带宽为10亿位每秒，那么环的等分带宽就是20亿位每秒（2000兆位每秒）。

全相连络

这是最理想的直接互连络，即每个交换器与每一个其他的交换器直接连接。它的等分宽度为p^2/4。但是这个需要的链路太多了。

超立方体

一种已经用于实际系统中的高度互连的直接互连络。

它是递归构造的。

维度为d的超立方体有p = 2^d个节点，并且，在d维超立方体中，每个交换器与一个处理器和d个交换器直接连接。

这样，超立方体的等分宽度为p/2，所以它比环或者二维环面格连接性更高，但需要更加强大的交换器，因为每个交换器必须支持条连线。所以，这是更贵的。

b. 间接互连

（简单理解）

交换器不一定与处理器直接连接。

它们通常由一些单向连接和一组处理器组成，每个处理器有一个输入链路和一个输出链路，这些链路通过一个交换络连接。

交叉开关矩阵和 omega 络。

延迟：从发送源开始发送数据，到目的地开始接收数据之间的时间。

带宽：开始接收数据之后，接收数据的速度

一个互连络的延迟为L秒，带宽为b字节每秒，则传输一个n字节的消息需要时间

time = L + n/b

一个新手的常识性问题：

Q：为什么不是所有的MIMD系统都是共享内存的—大多数程序员觉得通过共享数据结构隐式地协调多个处理器的工作，比显式地发送信息更加吸引人。（巧了，原来不是我一个人这么觉得。）

A：这里有一些问题。其中主要的硬件方面的问题是互连络扩展的代价。当向总线增加处理器时，访问总线发生冲突的可能性骤升，所以总线适用于处理器数目较少的系统。而大型的交叉开关矩阵非常昂贵。分布式内存互连络相对便宜（哪怕是超立方体、环面格）。因此分布式内存系统比较适合于那些需要大量数据和计算的问题。

1.6.4 Cache一致性

Cache一致性问题：在多核系统中，各个核的Cache存储了相同变量的副本，当一个处理器更新Cache中该变量的副本时，其他处理器应该知道该变量已更新，即其他处理器中Cache中的副本也应该更新。

（这种不可预测的行为与系统使用写直达策略还是写回策略无关。）

两种方法来保证Cache一致性：

监听Cache一致性协议
基于目录的Cache一致性协议

1.6.4.1 监听Cache一致性协议

实际的监听协议，与上述大致原理的差别：广播会通知其他核，包含x的整个Cache行已经更新，而不是只有x更新。（相当于更粗粒度地通知）

补充：

互连络不一定必须是总线，只要能够支持从每个处理器广播到其他处理器。
监听协议在写直达和写回cache上都可以工作。原则上，如果互连络可以像总线那样被Cache共享，如果是写直达Cache，就不需要额外地互连络开销，因为每个核都能“检测”写；如果是写回Cache，就需要额外的通信，因为对Cache的更新不会立即发送给内存。

缺陷：

在大型络上，广播是非常贵的。监听Cache一致性协议每更新一个变量就要做一次广播。它不可扩展，对大型系统会导致性能的下降。

1.6.4.2 基于目录的Cache一致性协议

该协议通过使用一个叫做目录的数据结构来解决上述问题。

目录存储每个内存行的状态，该数据结构一般是分布式的。

每个对，负责存储一部分的目录。这部分目录标识了局部内存对应高速缓存行的状态。

当一个高速缓存行被读入时，如核0的Cache，与这个高速缓存行相对应的目录项就会更新，表示核0有这个行的副本。当一个变量需要更新时，就会查询目录，将所有包含该变量高速缓存行置为非法。

目录需要大量额外的存储空间，但是当一个Cache变量更新时，只需要与存储这个变量的核交涉。（对应的部分目录在这个核上）

1.7 并行软件

前提：

这里只讨论MIMD系统的软件。
我们主要关注单程序多数据流（SPMD）程序。

SPMD不是在每个核上运行不同得程序，相反，SPMD程序仅包含一段可执行代码，通过使用条件转移语句，可以让这一段代码在执行时表现得像是在不同处理器上执行不同的程序。

SPMD可以实现数据并行，也能实现任务并行。

任务并行：

数据并行：

1.7.1 并行算法设计

进程/线程间的任务分配
1. 负载均衡。使得每个进程/线程获得大致相等的工作量
2. 使得需要的通信量尽可能少（一般涉及分布式系统）
安排进程/线程间的同步
安排进程/线程间的通信

单个机器上一般是多线程，而且一般不会涉及显式的通信。

1.7.2 并行程序设计的复杂性

足够的并发度（阿姆达尔定律）
并发粒度
- 独立的计算任务的大小
局部性
- 对邻近的数据进行计算
负载均衡
- 处理器的工作量相近
协调和同步
- 谁负责理频率/li>

1.8 输入和输出

通常应该尽可能避免输入和输出的问题。

我们一般做一些假设并遵循一些规则：

在分布式内存程序中，只有进程0能够访问stdin。在共享内存程序中，只有主线程或者线程0能够访问stdin。
在分布式内存和共享内存系统中，所有进程/线程都能访问stdout和stderr。
调试程序输出在生成输出结果时，应该包括进程/线程的序或者标识符以供区分。
……

见书P38

1.9 性能

串行算法评价：算法时间复杂度表示为输入规模的函数

并行算法评价：除了输入规模外，还考虑处理器数目、处理器相对运算速度、通信速度。

评价标准：

运行时间
加速比：并行算法比串行算法快多少

反直觉的地方：

Q：如果有很多串行算法，选哪个来做比较/p>

A：拿最优的串行算法。

例如：串行冒泡排序算法时间150s，串行快速排序算法30s，并行冒泡排序算法40s。那么加速比，而不是！！！！

1.9.1 加速比和效率

在理想情况下（任务在核之间平均分配，又不会为每个核引入额外的工作量），在p核系统上运行程序，每个核运行一个进程或线程，并行程序运行速度就是串行程序速度的p倍。

串行运行时间为，并行运行时间为，则最佳的预期为：。此时我们称并行程序有线性加速比。

实际上是不可能得到线性加速比的。

并行程序的加速比为

并行程序的效率为

并行算法总额外开销：

一点常识问题：

一般都是。S = p就是线性加速比。

（超线性加速比）在实践中是可能出现的。比如

串行算法计算量大于并行算法
硬件问题不利于串行算法

超线性的例子：由cache引起的超线性加速；搜索分解导致超线性

1.9.2 阿姆达尔定律

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

a为串行程序中可被完美并行化的比例

分子可以视作

分母可以视作

例题：某串行程序运行时间为20s，可并行化比例为90%，若使用p个核将其并行化，加速比为多少/p>

a = 0.9

S = 1 / (1 – a + a/p) = 1 / (0.1 + 0.9 / p)

1.9.3 可扩展性

对于某并行程序，核数（线程/进程数）固定，且输入规模固定。效率为E。

现在增加核数p，如果输入规模也以相应增长率增加的情况下，若效率E一直是E（不降），则该程序是可扩展的。

强可扩展的：增加线程/进程个数时，不增加问题规模，就可以维持固定的效率E。

弱可扩展的：增加线程/进程个数时，只有亿相同倍率增加问题规模，才能维持固定效率E。

2. MPI编程

MPI基本原语

阻塞通信

编程模型（对等、主从）

组通信

了解非阻塞通信

了解混合编程

2.1 起步和基本原语

消息传递：这是超级计算机和集群主要的编程模型

可移植 + 偏底层

这是一种分布式的并行编程，它隔离了独立的地址空间。

不会有数据竞争，可能有通信错误。
暴露了执行模型，迫使程序员思考局部性，两点对性能都有好处。
编程复杂，代码膨胀。

特性：

所有的通信、同步都通过调用函数来完成，不再有共享变量了。

基本原语：（这里是C版本的代码）

告进程数，值存储在size中。

告识别调用进程的rank，从0~size – 1。值存储在rank中。

消息传递——发送

消息缓冲区buf， count， datatype

目的进程dest（目的进程在comm指定的通信域中的编）

阻塞发送——函数返回时，数据已经转给系统进行发送，缓冲区可作他用；消息可能还未送达目的进程。

消息传递——接收

阻塞接收——等待，直到收到匹配的消息(source和tag都相同)，缓冲可作他用。

source可以是comm中的编，或MPI_ANY_SOURCE

tag为需要匹配的特定标签，或MPI_ANY_TAG

接收的数据量比指定的少是允许的，但接收到更多数据就是错误。

status包含更多信息，比如接收到的消息大小。

基本概念：

进程可以组成进程组，每个消息都是在一个特定上下文中发送，必须在同一个上下文中接收。进程组和上下文一起形成了通信域，进程用它在进程组中的编标识。

MPI_COMM_WORLD：默认通信域，其进程组包含所有初始进程。

MPI数据类型

MPI是强类型数据传输。消息中的数据用三元组（地址、个数、类型）描述。

比如MPI_CHAR、MPI_SHORT、MPI_FLOAT、MPI_BYTE、MPI_PACKED等等之类的。其中有的和C语言有类型对应，有的没有对应类型。比如哪个MPI_BYTE和MPI_PACKED就没有对应类型。

类型匹配——

宿主语言的类型和消息所指定的类型相匹配；

发送方和接收方的类型相匹配。

类型匹配规则——

有类型数据的通信，发送方和接收方使用的数据类型要相同。

无类型数据的通信，发送方和接收方均用MPI_BYTE作为数据类型。

打包数据的通信，发送方和接收方均使用MPI_PACKED。

MPI Tags

发送的消息都伴随一个用户定义的整数标签，帮助接收进程识别消息。

接收方通过指定特定标签来筛选消息，或者指定MPI_ANY_TAG来表示不筛选。

MPI_STATUS

在C实现中，status是至少由三个域组成的结构类型。

status.MPI_SOURCE(MPI_ANY_SOURCE)

status.MPI_TAG(MPI_ANY_TAG)

status.MPI_ERROR

接收函数获取status后，可以调用其属性来获得MPI_SOURCE和MPI_TAG，可得知其tag和source进程。

2.2 编程模型

消息传递有两种编程模型

对等式：地位平等，功能相近

主从式：地位不同，功能不同

2.2.1 对等模式

Jacobi迭代例子。

每个进程的地位对等，处理方式基本相同。

2.2.2 主从模式

主进程和从进程。

通常是主进程将任务进行划分，然后发送给各个从进程，并负责回收各个从进程的计算结果。

从进程负责计算。

2.3 组通信

一个进程组（通信域）内的所有进程同时参加通信。

所有参与进程的函数调用形式完全相同

哪些进程参加、以及组通信的上下文都是由在调用时指定的通信域限定的。

组通信中不需要通信消息标志参数

三个功能：通信、同步和计算

操作是成对的——互为逆操作

2.3.1 广播

一个进程向其他所有进程发送相同数据

初始，只有源继承有一份m个字的数据。广播操作后，所有进程都拥有一份相同数据

root: 每个调用广播操作的进程中root都相同

count：待广播的数据的个数

2.3.2 归约

初始，每个进程都有一份m个字的数据。归约操作后，p份数据经过计算（加、乘、。。。）得到一份数据结果，传送到目的进程。

MPI预定义了很多归约操作，比如MPI_SUM就是求和，MPI_PROD求积。

2.4 非阻塞通信

含义：调用返回 != 通信完成

作用：计算和通信的重叠

形式：非阻塞发送和非阻塞接收

消息传递与缓冲

当用户提供的buffer可被重用时，才表明send完成。

send完成并不意味着receive也完成——

消息可能被系统缓冲
消息可能还在传输中

实现非阻塞通信的难点
系统层面：

硬件支持通信在后台完成，不需要CPU参与；

有相应的编程接口。

算法层面：

要保证与通信重叠的计算与通信无依赖关系；

很多时候要重构算法。

2.5 多线程混合编程

多核集群的常见编程方法

纯MPI
1. 节点内和跨节点都采用MPI实现进程并行
2. 节点间MPI，内部是采用共享内存通信。
MPI + OpenMP
1. 节点内使用OpenMP，跨节点用MPI
MPI + Pthreads
1. 节点内使用pthreads，跨节点用MPI

后两种都可以称为混合编程。

2.5.1 四种线程安全级别

MPI定义了四种线程安全级别。

MPI_THREAD_SINGLE：应用中只有一个线程

MPI_THREAD_FUNNELED：多线程，但只有主线程会进行MPI调用

MPI_THREAD_SERIALIZED：多线程，但同一时间只会有一个线程会进行MPI调用。

MPI_THREAD_MULTIPLE：多线程，且任何线程任何时候都会进行MPI调用。

安全级别递增。

多线程混合编程时，定义了一个替代API，用以替代MPI_Init。

3. SSE/AVX编程

SIMD编程问题（打包解包、对齐开销、控制流开销）

SIMD编程

3.1 SIMD并行

多个算术运算 —-> 一个SIMD操作

多个取数/存结果操作 —-> 一个更宽的内存操作

3.2 SIMD编程额外开销

3.2.1 打包/解包数据的开销

打包源运算对象——拷贝到连续内存区域

解包目的运算对象——拷贝回内存

（数据在读与写回时，需要以多个一组整体的形式进行，因此设计打包与解包。）

解决方案：

重排数据使之连续。

3.2.2 对齐开销

对齐与不对齐的内存访问是不同的。

如果地址总是向量长度的倍数（比如16字节），那么很完美。但如果不是的话，我们不得不进行处理。

静态对齐：对没有对齐的读操作，做两次相邻的对齐读操作，然后合并。

动态对齐：距16字节边界的偏移是变化的或未知的。合并点在运行时计算。

小结：

最坏情况下，需要计算地址，动态对齐。
编译器/程序员可以分析确认对齐，一般而言是从起始地址处开始对齐，如果是在一个循环中顺序访问数据，起始位置固定，则对其特性不变。
可调整算法，先串行处理到对齐边界，然后再SIMD计算。

有时对齐开销会完全抵消SIMD的并行收益。

3.2.3 控制流导致额外开销

比如有一个if-else语句，有不同的处理。

程序会把两分支的运算都做了，存储在不同的寄存器t1和t2中，然后根据条件真假进行合并。

永远都是两个控制流路径都执行！

如何优化/p>

针对频率最高的路径优化代码。

小结：

一般观点：当存在控制流问题时，SIMD不是一个好的模型。

3.3 SIMD编程复杂性

高层编程：利用编译器，但不总是有效。
低层编程：使用intrinsic或汇编繁琐易错
数据必须对齐，在内存中连须存储。未对齐的数据可能产生不正确结果；可能需要拷贝到连续区域产生额外开销。
控制流问题引入了更多复杂性，还可能导致低效。

3.4 SSE/AVX编程

4. Pthread编程

共享内存编程

并行程序设计的复杂性

pthread一些基础api

同步相关概念

忙等待互斥量信量障碍

了解条件变量读写锁

复杂均衡任务划分

4.1 起步

pthreads是一个多线程编程库。

包含头文件

gcc编译时加上连接到库。

线程安全：若多线程并行调用能正确执行，就称之为线程安全的。

Pthread时POSIX标准

相对底层
1. 程序员控制线程管理和协调
2. 程序员分解并行任务并管理任务调度
可移植但可能较慢
在系统级代码开发中广泛使用，也用于某些类型的应用程序。

对比OpenMP新标准：

高层编程，适用于共享内存架构上的科学计算
1. 程序员在较高层次上指出并行方式和数据特性，指导任务调度
2. 系统负责实际的并行任务分解和调度管理
多种架构相关的编译指示。

一个例子：

声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！