4 posts tagged with "并行计算"

并行计算范围​

基础知识--并行平台​

• 单指令流多数据流（SIMD）: 单一控制部件向每个处理部件分派指令；
  • 控制语句会影响 SIMD 的性能
  • 只有一个全局控件
  • 设计研发周期长
• 多指令流多数据流（MIMD）: 计算机的每个处理器都能够独立于其他处理器执行不同的程序；
  • 需要在每个处理器上安装程序和操作系统
• 单程序多数据（SPMD）: 是MIMD模型的简单变形, 相当于将每一个MIMD中的计算指令用任务标识符指定的条件插入到一个大的if-else程序块中

基础知识--并行平台的数据通道/通信模型​

1. 共享地址平台​

共享地址空间是指并行平台支持一个公共的数据空间，所有处理器都能访问该空间。

处理器通过修改存储在共享地址空间的数据来实现交互。

2. 消息传递平台​

消息传递平台由p个处理节点构成，每个节点都有自己的独立地址空间。

运行在不同节点上的进程之间的交互必须用消息来完成，基本的消息交互操作是send和receive。

在由p个节点的共享地址空间计算机上，很容易模拟含有同样节点个数的消息传递体系结构；反之，在消息传递计算机上模拟共享地址空间体系结构的代价很高。

基础知识--并行平台的物理组织​

理想架构​

理想的并行随机访问计算机（PRAM） 包含p个处理器以及大小不受限制的全局内存，所有处理器同样可以访问该内存

然而允许并发就会带来同步问题,目前有几种协议解决同步问题:

• 共有，如果处理器试图写的所有值都相同，则允许并发写。
• 任意，任一处理器可以进行写操作，而其余的处理器则不行。
• 优先级，处理器按预定义的优先级列表排列、最高优先级的处理器可以进行写操作而其他的处理器不能。
• 求和，所有量的总和被写入（基于求和的写冲突解决模型能够扩展到任意由待写入量定义的相关操作符上)。

互联网络​

互联网络 提供多个处理节点之间或处理器与内存模块之间的数据传输的机制。

网络拓扑结构​

互联网络中使用了各种各样的拓扑。这些结构用来实现成本、可拓展性和性能间的平衡

1. 总线网络​

简单,到任意节点距离为O(1)

瓶颈在于总线带宽

2. 交叉开关​

网格型,每个交叉点均为一个开关

3. 多级网络​

多级网络比总线网络在性能方面可扩展性更强，又比交叉开关网络在成本上可扩展性更强

节点分层,每一层都可以采用不同结构

4. 多级omega网络​

每一级网络处理 p 个输入, p 个输出, 网络级数为 log p

每一级都有一种互联模式, 例如 完全混洗互联

经过完全混洗互联后,并非直接输出,而是两辆一组送到 2 * 2 **开关 **中

因此网络成本为 log p * p / 2 , 其中 log p 为 网络深度, p / 2 为每一层开关个数

此成本低于完全交叉网络的 p ^ 2

多级omega网络路由选择​

• 设s为需要写数据到存储区t的处理器的二进制表示。
• 数据穿过链路到达第一个开关节点。
• 如果s和t的最高有效位相同，那么开关就会按直通式方式进行数据选路;如果最高有效位不同，则以跨接方式进行数据选路。
• 在下一个开关级，再使用下一个最高有效位来重复同样的方案。

5. 线性阵列、格网、k-d网​

网络中链路过多, 选择稀疏网构造并行计算机

线性阵列 拓展到二维及为 格网

再拓展到更高维则成为 k-d网

6. 基于树的网络​

网络中任意一对节点间只存在一条通路

线性阵列和星形连接网络都是树网格的特例

静态网络在树的每个节点都有处理器;

动态树网络中，中间层的节点位交换节点，叶子节点是处理器

网络评价​

静态网络​

• 网络直径：网络中任意两个处理节点之间的最长距离。两个处理节点间的距离定义为它们间的最短路径（用链路数目表示)。
• 连通性：连通性是网络中任意两个节点间路径多重性的度量。
• 弧连通性：将一个网络分为两个不连通网络需要删去的最少弧数目。
• 对分宽度：把网络分为两个相等网络时，必须删去的最小通信链路的数目。
• 通道宽度：能够通过连接两个节点链路同时进行通信的位数。
• 对分带宽（或截面带宽）：对分网络任何两半之间允许的最小通信量，它是对分宽度和通道宽度的乘积。成本：网络中所需的通信链路数量。

动态网络​

由于动态网络中存在开关的概念, 因此需要将开关损耗也考虑在内,新增 节点连通性 指标

• 节点连通性：把网络分成两个部分必须删去的最小节点数目。这里只考虑开关节点（与考虑所有节点不同)。

高速缓存一致性​

该问题仍属于同步问题,目前依靠协议解决, 现存 更新 以及 无效 协议

• 更新协议: 无论何时写入一个数据项，它在系统中的所有副本都被更新。因此，如果某处理器只读了一次数据项，就再也不使用它，那么，其他处理器对该数据项的更新将会造成多余的开销。
• 更新协议和无效协议的性能均会受到**假共享（false sharing）**的影响。
• 当前的高速缓存一致性计算机 通常依靠无效协议。

无效协议​

每个数据副本都关联一个状态（shared, invalid, dirty）

当某处理器对变量做 存储操作 时, 该变量的所有副本都被标记为无效(invalid)。并把自己拥有的变量标记为已修改或脏（dirty)

若另一处理器执行 加载操作, 将变量标记为 dirty 的处理器会对请求提供服务, 并将全局副本更新, 数据重新变回 共享(shared) 状态

基础知识-进程-处理器映射​

映射过程中，有三个参数很重要。

• 第一，E中有可能不止一条边映射到E^′的一条边上。映射到E^′的任意边上的边数最大值称为映射拥塞度(congestion)。
• 第二，E中的一条边可能被映射到E'中多个相邻的边上。这一点也很重要，因为在相应链路的通信必须穿过不止一条链路，可能导致网络拥塞。E中的任意一条边能映射到E^′中的最大链路数目，称为映射膨胀度( dilation)。
• 第三，集合V和V^′可能包含不同数量的顶点。在这种情况下，V中的节点和V^′中不止一个节点相对应。集合V^′中节点的数目和集合V中节点数目之比称为映射扩充度。

并行计算优化​

传统意义上的串行计算机主要由 处理器、内存和数据通道 三个部件组成

优化处理器延迟​

改进设计理念: 一个时钟周期内执行多个指令

1. 流水线与超标量​

单流水线的速度最终受到流水线中最大原子任务的限制。

超标量: 在CPU中有一条以上的流水线，并且每时钟周期内可以完成一条以上的指令

超标量效率:

• 垂直浪费: 某一周期中执行部件没有指令发送；
• 水平浪费: 一个周期中只用到部分部件；

2. 超长指令字处理器(VLIW)​

超标量调度器的硬件成本和复杂性是处理器设计中的主要瓶颈。

为解决这个问题，VLIW处理器依靠编译分析技术来识别和捆绑可以同时执行的指令。

这些指令被调度和打包在一起，因此成为了长度超长的指令字。

这样做的好处是硬件设计简单

优化内存延迟​

1. 设立高速缓存(cache)​

2. 增加内存带宽​

增加块大小,使得取数操作减少,减少与 DRAM 交互,减少等待, 从而提高效率

3. 消除跨距访问​

该例子中,每次只读取 b 一行中的一个数, 会导致 cache 失效, 从而每次都需要直接与 DRAM 交互, 产生 跨距访问

该问题本质上与高速缓存相同

4. 多线程躲避延迟​

任务划分,这在第二章会详细解释, 本章节中简单理解为将互不影响的部分分到不同线程中并行执行,从而减少空闲时间

5. 预取​

数据载入操作提前, 即使发生 cache miss, 在真正需要使用时也能准备好

缺点: 如果数据项在载入和使用之间的时间间隔内被覆盖，就必须重新发出数据载入指令，从而影响程序性能。

优化通信成本​

两个节点间传送一条消息所花的时间是准备传送消息所花的时间及消息从网络中传送到目的地所花时间之和. 有以下主要参数：

1. 启动时间(ts)：在发送节点和接收节点处理消息所花费的时间。它包括消息的准备、执行路由算法等时间。
2. 每站时间(th)：消息在单个节点上的延迟时间。该时间受到网络延时、开关或路由延时的影响。
3. 每字传送时间(tw)：如果通道带宽是r个字每秒，那么每个字要花tw=1/r秒穿过链路。它包括网络开销以及缓冲开销。

1. 存储转发​

消息穿过有多个链路的路径时，路径上的每个中间节点接收和存储完整的消息后，就把消息转发给下一个节点。

将m个字的消息通过l个通讯链路发送到目的节点的总通讯时间 可用上述参数表示为: ts + th * l + tw * m * l

由于每站时间 th 很小,因此可以忽略不计, 简化为: ts + tw * m * l

2. 包路由选择​

把大的消息块分割成多个包,在网络中以流水线的方式处理这些包

这样可以省去等待包传输的时间, 因此总时间优化为: ts + th * l + tw * m

3. 直通路由选择​

直通路由选择在包路由选择的基础上做了以下改动：

• 消息被分成固定大小的单元，称为流量控制数字(flow control digit)或数据片(flit)；
• 强制所有的数据片走同样的路径。

相较于包路由选择，直通路由选择有以下优势：

• Flit比包小得多；
• 无每个包的传送路由选择信息开销；
• 无需顺序信息；
• 在并行计算机互连网络中（错误率极低），可采用错误检测机制取代开销很大的错误校正方案

在直通路由选择中,消息传递还可优化:

1. 大块通信：把多个小消息集中成一个大消息，这样就不用发送每条小消息和为每条消息花费开始成本ts；
2. 减少数据的大小：减少每字传送时间的开销；
3. 减少数据传送的距离：减少消息必须通过的站的数目。

互联网络路由选择​

根据路径长短的方式划分：

• 最小化路由选择；
• 非最小化路由选择。

根据确定性的方式划分：

• 确定性路由选择；

• XY路由选择 -》二维格网

  • 消息首先沿X维出发，直到到达目标节点的列，再沿Y维达到目的节点

• E立方体路由选择 -〉 超立方体网络

  • 与XY路由选择方案类似：在d维的超立方网络中，先从第一维出发，找到目标节点第一维相同的位置，再从第二维出发，直到在第d维到达目标节点

• 自适应路由选择

分解与分配是并行计算的关键步骤​

• 分解：将计算划分成许多小的计算；

• 分配：再把分解得到的小的计算分配到不同处理器中以便并行执行。

本文依据上述关键步骤, 大体上也分为 分解 与 分配 两个板块, 但在进入真正学习之前, 还请了解基础知识

一、基础知识​

1. 粒度、并发度、交互关系​

• 粒度: 体现了分解问题得到的任务数量和大小。

• 最大并发度: 任意时刻可同时执行的最大任务数称为最大并发度

• 平均并发度: 程序执行的整个过程中能并发运行的任务平均数,程序执行的整个过程中能并发运行的任务平均数

• 任务依赖图: 抽象表示任务间的依赖关系和任务的执行次序关系

• 关键路径长度: 依赖图中, 没有输入边的节点称为 起始节点，把没有输出边的节点称为 终止节点，任何一对起始节点和终止节点之间的最长有向路径就是 关键路径。关键路径上所有节点的权重之和称为 关键路径长度

• 任务交互图: 任务之间的交互方式可通过 任务交互图 来描述。

  • 任务交互图中节点代表任务，边连接彼此交互的任务

  • 任务交互图中的边集合通常是对应任务依赖图边集合的超集

• 任务间交互有无规则判定:

  • 有规则: 对于一个交互模式，如果 有一些结构（空间结构）有利于其交互的高效实现，那么这个模式被认为是有规则的。

  • 无规则: 如果一个交互模式中 不包含规则模式 ，则被称为是无规则的。

• 任务间交互静态与动态性

  • 静态交互模式：对于每一个任务，它们之间的交互在预定的时间发生，并且在这些时间交互的任务集在算法执行之前是已知的。

  • 动态交互模式：在算法执行前，交互的时间或交互的任务集不与先确定

• 交互的单向与双向

  • 双向交互：需要交互涉及的两个任务参与，某一任务或任务子集所需要的数据或工作明显由另一任务或任务子集提供。
  • 单项交互：交互可由参与某一个任务发起和完成，完成此交互并不会妨碍其他交互。双向交互在编程时往往更加 复杂。

2. 进程与映射​

分解中的任务数量超过可用处理元素的数量。因此，并行算法还必须提供 任务到进程的映射

映射由任务依赖关系图和任务交互图确定。

任务依赖图 可用于确保工作在任何时间点均等地分布在所有进程中（最小空闲和最佳负载平衡）

任务交互图 可用于确保进程需要与其他进程的交互最少（最少通信）

好的映射:

1. 应把相互独立的任务映射到不同的进程以获取最大并发度;
2. 应确保可用进程来执行关键路径上的任务，以使得任务变成可执行的时候总计算时间最短;
3. 映射相互交互的任务到同一个进程以便最小化进程间的交互

静态映射和动态映射​

• 静态映射:静态映射技术在 算法执行前 将任务分配给进程。
  • 以数据划分为基础的映射
  • 以任务划分为基础的映射
  • 分级映射(混合映射)
• 动态映射:动态映射技术在 算法执行期间 在进程间分配任务。
• 动态与静态的选择取决于以下几个因素：
  • 任务是否是动态产生
  • 任务大小是否已知
  • 与任务相关的数据大小任务间交互的特点
  • 并行编程模式等

二、 分解任务​

1. 递归分解​

流程:

1. 递归划分子问题
2. 对独立子问题并发求解

2. 数据分解​

流程:

1. 对数据划分
2. 根据划分数据推导计算到任务的划分

数据分解形式多样,可分为:

• 输入划分
• 输出划分
• 输入输出划分
• 中间结果划分

例子如下:

拥有者-计算规则

以划分输入或输出数据为基础的分解也常称为 拥有者-计算 规则。

规则思想：每一个划分都执行涉及它拥有的数据的所有计算。

3. 探测性分解​

探测性分解中只要一个任务找到答案，其他未完成任务就可以终止。因此并行形式执行的操作既可以少于也可以多于串行算法执行的操作

4. 推测性分解​

对于类似 switch 的语句, 在编译阶段并不可知其最终进入哪个分支, 因此需要推测分解任务

通常有两种方法：

• 保守方法：仅在保证没有依赖关系时并行执行；
• 乐观方法：即使它们可能是错误的，也调度和执行任务

保守的方法可能会产生很少的并发性，而乐观的方法可能需要在发生错误的情况下使用回滚机制

5. 混合分解​

组合以上分解方法以获得更优效果

分配任务(映射)​

负载平衡映射​

让各个进程负载平衡，并使进程的空闲时间最小，并尽量减少进程间的交互

静态映射​

以数据划分为基础​

数组分配​

• 块分配

  • 把数组分成小块,按照块划分, 负载不平衡

• 循环分配

  • 块循环分配思想：把数组划分成比可用进程数更多的块，这样就可以采用循环的方式把划分的块（和相关任务）分配给进程，以便每个进程都能得到若干不相邻的独立的块。解决负载不平衡

  • 在二维块循环分配中，如果每一块只有一个元素，这种分配称为循环分配

图划分​

有许多运行在稀疏数据结构上的算法，这些算法的数据元素间的交互模式具有数据依赖，并且非常不规则,物理现象的数值模拟提供了这种计算类型的大量来源。

以任务划分为基础​

决定一个通用任务依赖图的最优映射是NP完全问题。但在特定情况下，人们通常可以找到简单的最优解或者可接受的近似解。

分级映射​

纯粹建立在任务依赖图上的映射可能会遇到负载不平衡，或并发度不够

动态映射​

如果静态映射导致进程间负载高度不平衡，或任务依赖图本身就是动态的，就必须采用动态映射而排除静态映射。

一对多广播​

一个进程发送相同的数据给其他所有的进程或其他所有进程的子集

多对一归约(一对多广播的对偶)：在多对一归约操作中，p个参与进程的每一个都有一个缓冲区M，它包含m个字。来自所有进程的数据通过一个相关的操作符组合起来，并被累加到一个目标进程中一个m字的缓冲区中

实现方法​

可利用对偶性（一对多广播的对偶）实现：多对一归约可以先进行多对多归约（多对多广播的对偶），再进行收集操作（散发的对偶）

• 简单实现: 源节点向其余节点都发送消息, 简单但效率低下
• 递归加倍：源进程首先发送消息给另外一个进程。然后，这两个进程可以同时发送消息给还在等待消息的其他两个进程。继续这一过程，直到所有进程都收到了数据，这样消息可以在log p步广播完毕

1. 环或线形队列​

2. 网格​

可以把一个具有p个节点的方形格网的行或者列看作一个有√p节点的线性阵列。

一个线性阵列的通信操作可以在一个格网中分两个阶段来执行。

• 第一阶段，可以将格网中的行看作是线性阵列,将操作沿着一行或所有行进行。(除去每一行末尾节点)
• 第二阶段，再对列进行同样的操作。

3. 超立方体​

超立方具有2d个节点，那么可以将其看作是一个d维的格网，每个维度上有两个节点。因此格网算法能扩展到超立方体，在超立方体中的通信需要分d步来进行，每一步对应于每一维。

4. 平衡二叉树​

一对多广播的超立方算法可以自然地映射到平衡二叉树；

在平衡二叉树中，每一个叶子是处理节点，每一个中间节点是开关单元。

多对多广播​

实现方法​

1. 每个节点同时向它的一个邻居节点广播数据；
2. 在后面的步骤中，将每个节点同时向其他邻居节点转发从上一步骤中接受到的邻居节点的数据。
3. 整个算法在p-1步完成

1. 环型队列​

2. 网格​

1. 第一阶段，格网中的每一行执行一次线性阵列形式的多对多广播。在这一阶段里，每个节点从它们各自所属的具有√p个节点的行上收集√p个消息。每个节点把这些收集到的消息聚合成一个大小为m √p的消息，然后进行算法的第二通信阶段。
2. 第二通信阶段按列对合并后的消息执行多对多广播。当这一阶段完成时，每个节点获得p个m字的数据、这些数据原来驻留在不同的节点上。

全归约与前缀和​

• 全归约( all-reduce）操作等同于先进行一个多对一归约，再进行一个一对多广播。这个操作与多对多归约不同，多对多归约是p个多对一归约同时进行，并且每个操作都有不同的目标节点。使用多对多广播通信模式，可以更快地进行全归约操作
• 前缀和: 原始数字序列为（3，1，4，0，2），那么前缀和序列为（3，4，8，8，10）。

散发和收集​

• 散发(scatter)：单个节点发送一个大小为m的唯一消息给每一个其他的节点。发散操作的源节点从p个独自消息开始，每个消息将发给不同的节点。
• 收集(gather)：一个节点从其他各个节点那里处收集消息。收集操作并不涉及数据的组合与归约。

多对多私自通信​

每个节点给其他的每个节点发送一个大小为m的不同消息。每个节点都发送不同的消息给不同的节点！

环上的多对多私自通信​

1. 开始时每个节点把它们所有的数据作为一个合并的大小为m(p-1)的消息，发送给它们的一个邻居节点。
2. 随后，每个节点从接收到的数据中提取属于自身的数据，然后将剩下的p-2块m字大小的数据转发到下一个邻居节点上。
3. 重复步骤2，直至所有数据都发送到相应的节点上。

循环位移​

循环q移位(circular q-shift）定义:在一个p节点的系统中，节点i发送一个数据包给节点 (i+q) mod p，其中(0 < q < p )。

并行算法性能解析基础​

并行算法的执行时间不仅依赖于输入数据大小，还依赖于所用的处理器的数目，及它们相关的计算速度和进程间的通信速度

开销类型​

• 进程间通信：并行系统中 进程之间的通信，通常是并行程序开销的 最重要来源。
• 空闲时间：由于负载不平衡、同步问题或执行串行部分程序造成的空闲时间。
• 额外计算：在某些情况下，最优的串行算法可能无法并行化，这时我们需要使用较慢但容易并行化的算法，从而带来额外的计算开销。

性能评估指标​

• 执行时间: 从程序开始到结束所使用的时间
• 总并行开销: 所有处理器使用的总时间
• 加速比: 在单个处理器上求解问题所花的最短时间与用p个相同处理器并行计算机求解同一问题所花时间之比。

效率​

加速比与处理器数目的比率，即E= S/p。E的理想值应该小于等于1

当给定处理器数目p后，加速性能随着任务数n增加而下降！

粒度对于性能的影响​

有的时候使用更少的处理器可以提高并行系统的性能

如果使用少于最大可用处理器数量来执行一个并行算法的方法被称为按处理器数目***缩小（scaling down）***一个并行系统

可拓展性​

具备同时增加处理器数目和问题规模来保持效率为固定值的特性的系统称为 可扩展并行系统

并行系统的可扩展性是与处理器数目成比例增加加速比能力的度量，它反映一个并行系统有效利用（可变数量的）处理资源的能力。

对于给定的问题规模，当增加处理器数目时并行系统的总效率下降。这种现象在所有并行系统是常见的。

在很多情况下，如果问题规模增加而处理器数目不变，并行系统的效率增加。