并行编程平台

隐式并行

超标量执行/指令流水线

进入流水线之前先消除指令之间的数据相关

这表明，如果重排指令的顺序，可能提升效率

相关性包括

数据相关

资源相关

分支相关

具有乱序执行能力的 CPU 可以重排指令，更好地实现指令流水线，这种模型称为动态指令发送

超长指令字处理器 VLIW

使用编译器来解决数据相关和资源相关

能够并发执行的指令会编入一个组，作为一个超长指令字发送给处理器，并同时在多个处理器上执行

调度由软件来完成

编译器的并行语句选择空间大

编译器可以用复杂的静态预测策略

但是编译器中没有动态程序状态（如分支历史缓冲器）来对调度进行决策，这降低了动态预测的性能

超标量和 VLIW 都只局限在 4 路或者 8 路的并行上

内存性能系统的局限

从主存取一个块存在两个因素影响

1. 延迟

2. 带宽

因为延迟一般比计算时间大得多，所以性能会被这个延迟拖累

所以提出了 cache

提高带宽，也可能提升性能

然后还有内存布局的影响

避免内存延迟的方法

1. 预取

2. 多线程

3. 一次提出多个访问，使得延迟分摊到各个访问

预取和多线程提高了对带宽的要求

并行计算平台

控制结构

处理器 SIMD

协处理器 SIMD

MIMD

MIMD 的一个变体 Single Program Multiple Data, SPMD

SIMD 有一个缺点是处理不规则数据的效率较慢

比如对于一个 if else，所有处理器都用相同的这个代码处理不同的数据，假设一半的数据能满足 if，另外一半只能满足 else，那么在执行这段代码的时候，在所有处理器处理 if 的时候，有一半的处理器忙碌而另一半空闲，else 也是一样

通信模型

共享地址空间平台

共享地址空间的内存可以是处理器本地的，或者是对所有处理器全局的

一致内存访问 Uniform Memory Access UMA 对所有内存的访问时间相同

非一致内存访问 NUMA

有 cache 的计算机时 NUMA

NUMA 需要考虑本地性、结构化数据

UMA 不需要考虑本地性，编写并行程序的代码看上去像串行代码，但是访问数据存在互斥，还需要锁

cache 的存在提出了缓存一致性的问题

共享地址空间指的是所有处理器支持一个公共的数据空间

共享内存计算机指的是多个处理器共享同一个内存，相对的是，不同处理器只能访问内存的不同区域

消息传递平台

视为由节点构成

每一个节点具有唯一 ID，用于表明身份。ID 通过 whoami 函数来分配

设置 send 和 receive 函数，发送和接收消息

设置 numprocs 函数，设置参与消息传递的进程数

通过这四个函数，可以完成任意的消息传递程序

对比

在共享地址空间平台上很方便模拟消息传递

只要给每个处理器独占地分配一片共享地址空间就行了，通过把数据传送到这个空间来模拟消息传递

但是在消息传递平台上模拟就比较昂贵了，因为访问其他节点的内存需要传递消息

物理组织

理想并行计算机

由串行计算拓展而来

p 个处理器，一个大小不限的全局内存

所有处理器共享该内存，地址空间相同，共享时钟

但是不同处理器在同一个时钟可以执行不同的指令

Parallel Random Access Machine, PRAM

不同处理器可能对内存并发访问，所以根据对于内存的访问方法，可以分为

1. 互斥读互斥写（EREW）PRAM

2. 并发读互斥写（CREW）

3. 互斥读并发写

4. 并发读并发写

并发读不会影响语义

但是并发写会影响

几种仲裁方法：

1. 共有：如果所有处理器试图写的值都相同，则允许并发写

2. 任意：任一处理器先写

3. 优先级

4. 求和：所有量的总和被写入

   基于求和的模型可以拓展到任意的，由待写入量定义的操作符

并行计算机互联网络

静态 动态

路由

网络拓朴结构

基于总线的网络

可以为每个节点准备缓存

交叉开关网络

开关节点数是 $p^2$ 元件多，数据传输速度不高

可拓展性不高

多级网络

共享总线：成本上可拓展，性能上不可拓展

交叉开关：成本上不可拓展，性能上可拓展

多级网络：折中

网络级数为 $\log p$

单独把每一级网络拿出来，p 个输入对应 p 个输出

一种对应模式称为完全混洗，输入序号 i 输出序号 j，则完全混洗的函数为

每一级网络含有若干个开关节点，每一个开关节点处理两个输入输出

开关有两种

那么每一级网络有 $p/2$ 个开关节点，所有网络总共有 $p/2\log p$ 个节点，这远远小于交叉开关网络

考虑开关的话，多级网络可以表示为

假设输入的二进制表示是 s

每一级网络的输出的端口的二进制表示是 t

选择开关直通或者跨接的方式是判断 s 和 t 的最高位是否相同

相同则直通，不同则跨接

这种方式不是完美的，可能遇到阻塞

全连接

一定不会阻塞

星形

线性阵列、格网和 k-d 格网

全连接是密集的

线性阵列和格网是稀疏的

格网的拓扑结构适合物理仿真

k-d 格网指的是 d 维，每一维上有 k 个节点

线性阵列是 k-d 格网的一个极端

超立方体是 k-d 格网的另一个极端

超立方体的编号方式有一个特性，就是两个二进制编号之间不同的位数表示了它们之间相隔多少个链路

使用超立方体结构时，这个特性可以导出许多并行算法

基于树的

任意一对节点之间只存在一条通路

传送消息的时候，从下到上先传送到根节点，再传到目标

所以根节点会频繁传送消息，所以可以给上层加粗链路，称为胖树

静态互连网络评价

距离：两节点之间的最短路径

直径：网络中任意两节点之间的距离的最大值

连通性：从一个连通网络中获得两个互不连通的网络所要删除掉的最少弧数量，称为弧连通性

对分宽度：分为两个相等网络所要删除掉的最少链路数量

通道宽度：越过两个节点之间进行通信的位数 = 每个通信链路中物理线路的数目

通道速度：单一物理线路能够传送的峰值速度

通道带宽：两个通信节点之间传送的峰值速度 = 通道速度 * 通道宽度

对分带宽：对分网络任何两半之间允许的最小通信量 = 对分宽度 * 通道宽度
（截面带宽）

成本：用通信链路数量或者对分带宽来评价

动态互连网络

信息经过开关的时候存在开销

那么把开关视为节点

距离、直径的定义相同

连通性：弧连通性和节点连通性

节点连通性这里只考虑开关

考虑对分宽度的时候，只需要保证对分网络中的处理节点的数目相等，而不需要包括开关节点

在所有划分对分网络的方法中，要选择划分穿过的边数最少

成本：=链路成本=开关成本

多处理器中的缓存一致性

多处理器中的缓存一致性比单处理器中的缓存一致性更复杂

因为可能有多个处理器修改副本

修改多个副本的过程必须是串行的

要不就同时修改所有副本，要不就单独修改某一个副本，使得别的副本失效

这称为更新（update）协议和无效（invalid）协议

同一时间只能选用一个协议

一种情况：假共享

假共享指的是不同处理器更新相同缓存行中的不同部分的情况

如果使用无效协议，那么处理器 A 在更新自己的变量的时候，因为 A、B、C 关注同一行的不同位置，所以这会使得别的处理器 B、C 的缓冲中的这一行无效。等到 B、C 想要获取自己的缓存中的这一行的时候，还要去 A 中取。

书中说的”虽然没有对共享变量进行更新，但是系统并不进行检测“应该说的是，假设讨论的处理器有 A、B、C，那么 A 对自己的共享变量进行更新的时候，A 更新的并不是 B、C 的共享变量，所以无法设计一个程序来检测假共享？总之这话听起来挺怪的

假共享导致数据在各个处理器之间像乒乓球一样传来传去

用无效协议维护数据一致性

常用无效协议，之后的讨论都默认使用无效协议

使用无效协议时的三个状态：共享 S、无效 I、脏 D

还可以使用硬件机制来实现一致性

硬件机制包括

1. 侦听系统

2. 基于目录的系统

3. 以上两者的结合

缓存侦听系统

侦听与广播互连网络有关

所有处理器都侦听总线

多个处理器同时读相同的数据会有一致性问题

共享带宽会限制同一时间一致性操作的个数

向所有处理器广播某个处理器的所有内存操作不是一个可拓展的方案

一个解决方法是只将一致性操作传播给那些必须参与操作的处理器

要知道哪些处理器包含这个数据的副本，还有这些数据的状态信息

这些信息存储在一个目录中

基于信息的一致性系统称为基于目录的系统

这句话说的并不是说直接把目录结合到侦听系统，而是接着要介绍一个完全基于目录的

看的时候听着他这么说我还以为是马上要介绍拓展了呢

基于目录的系统

多个处理器同时写入一个数据的时候，产生一致性操作

一致性操作有两种开销

1. 传播状态更新

   这是通信开销

2. 从目录产生状态信息

   这会产生资源争用

目录在内存中，单位时间只能进行有限次的读写，所以目录会限制单位时间一致性操作的个数

还有另外一个瓶颈是目录的大小

假设内存块的大小为 m，p 是处理器的数目，那么目录的大小就是 mp

解决方法之一是增大内存块的大小，这样，在内存空间不变的情况下，m 会减小

但是在遇到假共享的时候，开销更大

分布式目录方案

因为目录是争用中心，所以很自然的想到拆分目录

其实拆分目录的本质上就是拆分内存，因为一个目录必须管理一个完整的内存，一个目录不会对应多个内存，也不会有多个目录对应同一个内存，这是一对一的

所以如果存在多个目录的话，那你就是在拆分内存

允许 $O(p)$ 个同时的一致性操作

更加具有可拓展性

请求块的信息和无效信息通过网络传播，网络延迟和带宽成为主要瓶颈

并行计算机的通信成本

与编程模型语义、网络拓朴结构、数据处理、路由选择以及相关的软件协议有关

消息传递成本

启动时间 $t_s$

每站时间 $t_h$

每字传送时间 $t_w$

存储转发路由选择

每个站都要先把消息存储完整之后再开始转发

总时间：$t_{comm}=t_s+(m{t}_w+t_h)l$

现在 $t_h$ 一般很小，可以忽略不计，那么总时间计算为 $t_{comm}=t_s+m{t}_{w}l$

包路由选择

把消息分成包，接收到消息的一半的时候，路由就可以开始转发

也可以分为四份

假设包的大小是 $r+s$，$r$ 是原始消息，$s$ 是附加信息

将消息分成包的时间应该与消息的长度成正比，所以可以设为 $m{t}_{w1}$

那么设每字传送时间的记法改为 $t_{w2}$

第一个包送达的时间是 $t_s+t_{h}l+t_{w2}(r+s)$

每个包到达的时间间隔是 $t_{w2}(r+s)$

总共有 $m/r$ 个包，第一个到达之后，后续还有 $m/r-1$ 个包

那么总时间是 $t_s+t_{h}l+t_{w2}(r+s)m/r+m{t}_{w1}$

令 $t_w=t_{w_1}+t_{w2}(1+1/r)$

总时间为 $t_s+t_{h}l+t_{w}m$

现在 $m$ 和 $l$ 之间分开了，不是相乘了

一开始还不知道这个包和计网中的数据包有什么区别

看完这个时间的计算之后我懂了，计网中的包指的是对于全部的信息来说，把长长的信息分段了

但是分段之后的信息，对于路由怎么传送呢？没有要求

而这里说的包，只是对于路由而言的，对于路由，传送不再是接受完所有信息才能传了，接受了一部分也可以开始传了

直通路由选择

强制所有包选择同样的路劲，可以减少路由选择开销

强制顺序传送，可以减少排序开销

将错误信息与消息层联系而不是与包层相联系，可以减少错误检测与校正的开销（由上层负责检错？）

并行计算网络中的错误率低，可以用便宜的错误检测替代错误校正

这些优化之后的方案，称为直通路由选择

中间节点直接转发，什么都不用存

那么总时间是 $t_s+t_{h}l+t_{w}m$

这种模式会要求线路传输速度以恒定的速度运行

那么数据片太小和太大都不合适

太小的话，为了保持固定带宽，需要发送速度很大

太大的话，传送的延迟增加

假设路由器允许这么短的消息，对于需要短消息的计算，发送延迟又是一个问题

一个解决方法是多道直通路由选择。它将一个物理通道分为多个虚拟通道

这种路由选择模式也会遇到死锁问题

成本模型

为了减少传送时间，对于公式 $t_s+t_{h}l+t_{w}m$，可以有以下方法

1. 大块通信

   为了减少开始成本 $t_s$

   在机群和消息传递计算机这样的平台，$t_s$ 的值远大于其他两项

2. 减少数据的大小

   减少 $m$

3. 减少数据传送的距离

   减少 $l$

第三项最难，因为程序无法控制消息在路由中的传播路径，减少路由数目可能使网络争用加剧

因为每站时间 $t_h$ 对于小消息而言主要由开始延迟决定，对于大消息主要由信息的长度决定，所以公式可以化简为

$t_{comm}=t_s+t_{w}m$

该成本模型没有考虑拥塞，不适用于拥塞的情况

共享地址空间计算机的通信成本

希望通过对通信时间的分析可以知道程序设计

但是难点在于

1. 内存布局通常由系统决定

2. 有限大小的缓存导致缓存颠簸

3. 与无效和更新相关的开销很难量化

4. 空间本地性很难模仿

5. 预取很难模拟

6. 假共享

7. 数据争用

互连网络的路由选择机制

根据是否选择最短路径分类：

1. 最小化路由选择

2. 非最小化路由选择

根据如何使用网络状态来分类：

1. 确定性路由选择

   维序路由选择

2. 自适应路由选择

用于二维格网的维序路由选择称为 XY 路由选择

用于超立方体称为 E 立方体路由选择

先由 X 维度到达目标节点的 X 维度，再沿着 Y 维度走到目标节点

对于超立方体，其实就是一个长度只有 2 的多维空间

他说的是确定两点的序号的二进制，每一步沿着两个编号异或结果的最后一个非零位走

其实二进制编号就是各个维度的笛卡尔坐标嘛，异或的非零位就是说明坐标不同，选最后一个非零位就是沿着 i j k 这个顺序找，找到了之后加 1，就是沿着坐标轴正方向走一步，走一步之后就算是进位了，也不会影响到后面，所以从后往前找

进程-处理器映射的影响和映射技术

这种映射通常无法控制

图的映射技术

图 G(V,E) 映射到图 G’(V’,E’)

点映射到点，边映射到边

E 中的一条边可能映射到 E‘ 中的多条边

映射拥塞度：E 中的一条边映射到 E‘ 中的多条边的最大数目

映射膨胀度：E 中的一条边映射到 E‘ 中的链路的最大数目

映射扩充度：V’ 与 V 中节点数目之比

以下讨论限于映射扩充度为 1

将线性阵列嵌入超立方体

感觉就是将超立方体的编号二进制化了

膨胀度和拥塞度都是 1

将格网嵌入超立方体

类似环

膨胀度和拥塞度都是 1

将格网嵌入线性阵列

链路变少了，一定会拥塞

拥塞度下界为格网的对分宽度 $\sqrt{p}$

将超立方体嵌入 2 维格网

超立方体的二进制编号对半分，可以确定 2 维格网的两个坐标

计算拥塞度的时候，因为是映射到 2 维，所以考虑到超立方体的节点数量是 2 维得到的话，那么就相当于一个超立方体分成若干个子超立方体，每个子超立方体有 $\sqrt{p}$

那么现在就是一个子超立方体映射到 2 维格网的一个行

子超立方体的对分宽度是 $\sqrt{p}/2$，而二维格网的一个行的对分宽度是 1

所以拥塞度是 $\sqrt{p}/2$

进程-处理器映射与互联网络设计

稠密网格映射到稀疏网格中，拥塞度大于 1，也就是我们额外多了拥塞控制相关的开销

但是如果我们的稀疏网格的带宽足够大，大到抵消拥塞控制的影响，那么映射到稀疏网格就是有利的，因为这样就缩小节点之间的距离了

比如超立方体嵌入到 2 维格网的拥塞度是 $\sqrt{p}/2$，那么只要 2 维格网的带宽是超立方体的 $\sqrt{p}/2$ 就行了

这个带宽增加以抵消拥塞控制的网络称为胖网络

高维网络还有一个缺点是网络布局复杂、线路纵横，线长不一

性能-成本平衡

看不懂计算了

并行算法设计原则

识别能并发执行的任务部分

映射个并发任务块到并行运行的多处理器上

分布与程序有关的输入、输出和中间数据

管理对由多处理器共享的数据的访问

在并行程序执行的各个阶段对处理器进行同步

预备知识

分解、任务与依赖图

粒度、并发性与任务交互

最大并发度

平均并发度

关键路径：最长有向路径

关键路径长度

平均并发度 = 总工作量 / 关键路径长度

加速比= 串行时间/并行时间

交互

任务交互图

任务交互图通常是任务依赖图的超集

例如稀疏矩阵和向量相乘

设任务 i 是 A 的第 i 行和 b 的第 i 个元素的拥有者

这意味着任务 i 要计算结果的第 i 个元素，还要去向别的任务发送自己拥有的 b[i]，要从别的任务 j 那里接受自己需要的 b[j]

进程和映射

这里的进程指的不是操作系统的进程

而是一个抽象的利用代码和数据产生结果的实体

给进程分配任务称为映射

需要避免增加任务与任务的交互引出进程间的交互

例如 图3-7 任务 5 如果分配给 P2，那么 P0 和 P1 都要和 P2 交互

但是如果分配给 P0，那么就只有 P1 和 P0 一次交互

进程与处理器

进程一般可以与处理器有一一对应的关系

但是一个节点也可以有多个 CPU

所以一般的思路是

先设计消息传递模式下的并行算法

用在节点之间

然后设计共享存储模式下的并行算法

用在节点内部的多 CPU

分解技术

1. 递归分解

2. 数据分解

3. 探测性分解

4. 推测性分解

递归分解

例：快排

有些问题的直观算法上没有分治的特性，也可以构造出分治的算法

例如找最小数

数据分解

例：矩阵与矩阵相乘，划分分块矩阵

1. 划分输入数据

2. 划分输入和输出数据

3. 划分中间结果

拥有者-计算规则

每个划分都执行设计它拥有的数据的所有计算

探测性分解

某些问题的基本计算对应于解空间的一次搜索

划分搜索空间维更小的部分，然后并发搜索这些小的部分

一个任务找到解之后就通知其他任务结束

例：15 迷宫问题

推测性分解

并行执行 switch 的多个分支

正确的分支被使用，错误的分支被抛弃

混合分解

前面介绍的分解方式的混合

比如找一组数中的最大数的时候，单纯递归分解的话，可能得到的任务数很多，远远超过可用的进程数

那么可以先数据分解，就是先把这一组数分解成几份，然后再对每份递归分解

又或者单纯递归分解的话，各个任务的大小不一，那么并发性有限。先通过数据划分划分出近似相等工作量的数据，再递归分解就好了

任务和交互的特点（映射方案）

任务和交互的特点对映射方案产生影响

任务特性

任务产生

静态任务产生：所有任务在算法开始执行前是已知的

动态任务产生：例如递归分解

探测性分解可能静态任务产生也可能动态任务产生

任务大小

任务大小是完成任务所需的相对时间

均匀：是否需要大致相同的时间来执行这些任务

非均匀：~

任务大小的只是

任务大小是否为已知

与任务相关的数据大小

数据移动开销

数据类型（输入数据，输出数据）

任务间交互的特征

静态与动态

静态交互模式：每一个任务的交互在预定的事件发生，该任务集在算法执行前已知

动态交互模式：两者至少一个不知道

消息传递模式中，静态容易，动态难，因为消息传递交互需要知道发送者和接收者。所以实现动态需要额外的同步或轮询

使用共享地址空间，静态和动态都容易

有规则与无规则

有规则：交互结构有利于实现

只读和读写

单向与双向

双向：某一任务需要的数据要由另外一个任务提供

单向：只有一对通信任务，该任务不会妨碍其他任务（看不懂？）

消息传递中需要把单向交互转化为双向交互（看不懂？）

负载平衡的映射技术

两个并行化任务的运行开销源

1. 进程间交互

2. 某些进程的空闲时间

最小化这两个时间通常是矛盾的

因为最小化交互的最直接办法就是，把大部分任务都映射到同一个进程上，这样就完全没有交互了

但是这样就会导致这个被分配了大部分任务的进程的计算时间长，其他进程的空闲时间又多了

该任务分解表示了 12 个具有依赖关系的任务的映射到进程的关系

映射技术：

1. 静态映射

   算法执行前把任务分给进程

   静态产生的任务，可以用静态映射也可以用动态映射

   选择好的映射经常是 NP 难问题，所以一般用启发式方法

2. 动态映射

   在算法执行时在进程间分配任务

   动态产生的任务必须用动态映射

   如果任务大小未知，那么静态映射可能引起负载不平衡

   但是动态映射要负责在进程间移动数据，所以如果与任务相关的数据很大，那么数据移动的开销可能抵消动态映射的优势

静态映射方案

以数据划分为基础的映射

与拥有者-计算规则相关

数组分配方案 块分配

按照数组的某一维

或者按照数组的多个维度

对于 2d 的话，就是可以按照某一行，或者某一列，或者某一个块

多维分配一般是比较好的

1. 多维分配可以分配更多的进程

   例如假设维度为 n，一维分配的话最多分配 n 个进程，二维分配的话最多分配 n^2 个进程

2. 多维分配可能有利于减少进程之间的交互

如图所示，一维分配，每一个进程划分了 A 矩阵的 n/p 个行，每一行有 n 个元素，那么要访问 A 矩阵的 n^2/p 个元素。对于 B 矩阵，每一行都要遍历矩阵的所有行，对于 B 矩阵就是 n^2

所以一维分配就是 n^2/p + n^2

对于二维分配，要访问 A 矩阵的 $n/\sqrt{p}$ 行和 B 矩阵的 $n/\sqrt{p}$ 列，每一行和每一列都是 $n$ 个元素，那么总共访问的元素是 $2n^2/\sqrt{p}$

这明显少于一维分配的情况

数组分配方案 循环分配和块循环分配

不同元素的计算量不同时，块分配会引起负载不平衡

经典的 LU 分解，分解出来的 LU 是写在 A 里面的，A 的对角线上是 U 的对角线，L 的对角线隐含为 1

对于 A 中的元素，越靠右下角的元素需要进行的任务越多，如图所示

计算 $A_{1,1}$ 仅需要一个任务，计算 $A_{3,3}$ 需要任务 9、13、14

这就是块负载不平均的例子

块循环分配的中心思想是把数组划分成比可用进程数更多的块，这样就可以采用循环的方式分配任务，让每个进程获得若干不相邻的块

所有进程都从矩阵的各个部分得到任务，所以块循环分配减少了进程的空闲时间，使进程负载均衡

粒度太细的话，当然负载更加均衡，但是没有相邻数据，本地性很差，可能导致性能下降，同时也可能进程间交互增大

数组分配方案 随机块分配

图划分

一般每个格网点的计算量相同

但是我们希望相邻的格网尽可能被分配到同一个进程中，以减少格网之间的数据依赖

如图，分配格网到随机进程，那么进程之间的数据交互会很多

我们希望相邻的格网被分到同一个线程，并且交互最少

那么很容易想到，分到同一个线程的格网就是一个图形，不同线程会对应不同的图形，图形之间的共享边就是发生数据交互的地方，希望数据交互最少，就是希望这个边最小

求这个边最小是一个 NP 难问题，但是我们可以用启发式的图划分算法

以任务划分为基础的映射

存在时任务依赖图，可以根据这个图，将图的节点映射到进程

求最优映射也是 NP 难，一般用简单解

一个例子是完全二叉树形式的任务依赖图

把以数据划分为基础的映射改为以任务划分为基础的映射，可能减少交互

例如稀疏矩阵与向量相乘

下图展示了以数据划分为基础的映射，三个进程以行为划分，每个进程拥有自己的 A 的特定行数和 b 的特定行数。为了完成乘法，每个进程还需要 b 中的别的元素，这就产生了交互

例如进程 0 具有 b 中的 0 1 2 3，他还需要 b 的 4 5 6 7 8 号元素

把 A 矩阵写成图，$a_{ij}$元素不为 0，那么 i 和 j 之间相连

这个图实际上也可以表示，具有 A 中的第 i 行的话，需要的 b 的号就是图中与 i 相连的序号

将这个图划分为若干个子图，每个子图表示每个进程拥有的 A 的行号，每个子图之间的相连的边就表示每个进程需要向别的进程请求的 b 的序号

划分子图，使得每个子图之间的相连的边尽可能少

可见，划分这个任务交互图得到的交互是可以小于以数据划分的交互的

分级映射

动态映射方案

主要是为了保持负载平衡

集中式方案

主进程

从进程：从主进程拿任务

例：多个排序的任务，每一个任务对应一个下标，维护一个下标池，有进程空闲时，若下标池不为空，那么空闲进程就获取一个下标，进行对应的任务

这被称为自调度

如果分配任务的时间相对于执行任务的时间更大时，可能瓶颈就会在分配上了

这个时候可以用块分配，一次分配得到多个任务

但是如果一次分配很多，有可能导致负载不平衡

也可以通过减小块大小的方式来调整

分布式方案

可执行任务集分布在多个进程

1. 怎么成对地发送和接受进程

2. 由发送者还是接收者启动任务的传递

3. 每次交换中传递多少任务？

   传递太少，不够算，导致多次请求，通信开销变大

   传递太多，发送者陷入空闲，又导致发送者向别人请求，也导致通信开销变大

4. 何时传递任务

   接受者的所有任务都执行完？

   或者是接收者只剩下很少的任务？

并行结构的适应性

在消息传递模式中，与计算对应的任务大小应该远大于数据大小，才有执行任务的价值

在共享地址空间模式中，任务不需要显式移动（有内存到缓存的的数据移动，但是隐式的），所以任务的粒度可以小一点

包含交互开销的方法

1. 交换数据的大小

2. 交互的频率

3. 交互的空间和时间模式

最大化数据本地性

最小化数据交换量

例如矩阵和向量相乘，从一维映射到二维映射的例子

使用高维分配是一个方法，使用本地数据存储中间结果是另一个方法

例如计算向量点积的时候，计算长度为 n 的两个向量的点积，p 个任务，每个任务把累加量存到本地，最后一起加到共享变量，这对共享变量的访问从 n 降低到 p

最小化交互频率

交互有启动开销嘛

启动开销要是相对于传输开销更大的话，多次启动就效率低

这都是之前分析过的

怎么减少交互呢？

使得访问数据位置接近

在共享地址空间模式中，程序具有空间本地性，就可以利用缓存

在消息传递模式中，一次传递多个消息

稀疏矩阵与向量相乘的时候，每个任务自己有 b 的一部分，要去请求别的任务获得 b 的其他部分。为了减小交互频率，每个任务预取 b，而不是在乘法进行时再取

我感觉这就是预取？

最小化争用与热点

资源争用

数据争用

进程争用（对同一个进程发消息

例如对于矩阵与矩阵相乘

一个进程算一个 $C_{i,j}$

如果使用

$$C_{i,j}=\sum _{k=0}^{\sqrt{p}-1}{A}_{i,k}{B}_{k,j}$$

那么可能发生争用，例如

$$C_{1,0}=A_{1,0}{B}_{0,0}+A_{1,1}{B}_{1,0}$$

$$C_{1,1}=A_{1,0}{B}_{0,1}+A_{1,1}{B}_{1,1}$$

那么计算 $A_{1,0}{B}_{0,0}$ 和 $A_{1,0}{B}_{0,1}$ 的时候会争用 $A_{1,0}$

但是只要把计算顺序改一下

$$C_{i,j}=\sum _{k=0}^{\sqrt{p}-1}{A}_{i,(i+j+k)\%\sqrt{p}}{B}_{(i+j+k)\%\sqrt{p},j}$$

就可以让相邻的 C 对 A 的计算错开

$$C_{1,0}=A_{1,1}{B}_{1,0}+A_{1,0}{B}_{0,0}$$

$$C_{1,1}=A_{1,0}{B}_{0,1}+A_{1,1}{B}_{1,1}$$

因为这个形式本身就是棋盘格的形式，之前讲过的

它这里应该是默认一个任务是算一项 AB 吧

分布式代替集中式

使计算与交互重叠

提前启动交互，使得任务在等待交互完成时，进程可以执行另一个任务

预测自己的任务将要完成，提前发送请求，那么自己在完成剩下的部分的时候，同时也等待了请求的应答

计算与交互应该有硬件支持。用原语提供这种支持

预取硬件：预测即将访问的存储地址

复制数据或计算

如果多个进程要以只读的方式频繁访问共享数据

某些模式下，只读访问共享数据会比访问本地数据的开销更大

那么复制该数据，为每一个进程准备一份，因为是只读，所以没有交互开销

用来存储这些复制的副本的存储量随着进程数线性增长

某些可以被共享的中间计算结果，各个进程自己独立计算可能反而更快

使用最优聚合交互操作

1. 访问数据

2. 通信密集的计算

3. 同步

MPI

一些交互与另一些交互的重叠

a 和 b 是广播 m1 的两种方法

a 用了交互的重叠，此时 a 比 b 快

但是如果广播 m1 m2 m3 m4

反而是 b 比 a 慢，如 c 所示

所以程序员要知道什么时候自己写聚合通信函数更好

并行算法模型

算法模型就是将前面讲的分解、映射、最小化交互组合起来的方法

数据并行模型

稠密矩阵相乘

任务图模型

与任务对应的数据量远大于与任务对应的计算时，使用该模型

利用任务之间的相互关系来提高本地性或减少交互开销

快速并行排序、稀疏矩阵分解、分治算法

工作池模型

动态映射任务到进程以保持负载平衡

指向任务的指针可以保存在物理共享列表、优先队列、散列表或树种、或存储在物理分布的数据结构中

与任务相关的数据量远小于与任务相关的计算时，使用该模型

这样任务可以方便地移动

块调度的循环并行化

主-从模型

任务预先分配

如果产生任务很费时间，那么间断地分配任务

流水线模型或生产者-消费者模型

数据流通过一串进程传递，每一进程执行一个任务

并行 LU 分解

混合模型

基本通信操作

假设通信开销可以用 $t_s+m{t}_w$ 的形式表示

$t_w$ 应该反应通信拥塞导致的延迟

假设共享地址空间模式中，数据共享的开销也可以用 $t_s+m{t}_w$ 的形式表示

以下假设网络支持直通路由选择；通信时间与路径上的中间节点数无关；通信链路是双向的；单端口

一对多广播以及多对一归约

一对多广播：一份数据广播出去，n 个副本

多对一规约：n 份数据累加到一个目标进程

环或线性阵列

要发送 p 个消息

一个源进程向其他 p - 1 个进程，顺序地发送 p - 1 次，效率比较低

递归加倍：一个源进程向第一个进程发消息，然后这两个进程向另外两个进程发消息，如此递归，时间复杂度 $\log p$

环中的递归加倍：

每一步都选择最远的节点去通知

这样选择是为了避免网络拥塞

例如第一步，0 如果不选择 4 而是选择 1，那么第二步中，如果 0 要发给 2，1 要发给 3，那么在 1-2 这条路上就会出现拥塞

其实对于单独一个线性阵列进行递归加倍的时候，你也要面对怎么选择序号的问题。也要把它视为线性阵列视为环来选取序号

归约是对偶过程

例子：

矩阵和向量相乘

格网

格网是线性阵列的推广

分为两个阶段，一个维度一个阶段

第一个维度上所有节点都受到信息之后，进入下一个阶段

这里就体现了，每一个线性阵列的递归加倍都是按照环来找序号的

超立方体

也是线性阵列的推广

平衡二叉树

超立方体算法自然映射到平衡二叉树

算法细节

假设节点数是 2 的幂，但是可以拓展到任意数量

procedure ONE_TO_ALL_BC(d, my_id, X)
begin
	mask := 2^d - 1;  /* Set all d bits of mask to 1 */
	for i := d - 1 downto 0 do  /* Outer loop */
		mask := mask XOR 2^t;  /* Set bits i of mask to 0 */
		if (my_id AND mask) = 0 then  /* If lower i bits of my_id are 0 */
			if (my_ud AND w^i) = 0 then
				meg_destination := my_id XOR 2^t;
				send X to meg_destination'
			else
				meg_source := my_id XOR 2^i;
				receive X from msg_source;
			endelse;
		endif;
	endfor;
end ONE_TO_ALL_BC

i 是从 d-1 递减的

所以是从二进制数的高位到低位

这个 mask 一开始是全 1，然后从高位到低位与 2^i 异或，实际上就是从高位到低位置 0

mask 的变化：

1111…1
0111…1
0011…1

那么异或之后和 my_id 与操作，判断结果是不是 0，就是判断 my_id 的后 i 位是不是全 0

如果 my_id 的后 i 位全是 0 了，那么剩下的就是每次要参与发送和接受信息的序号了

比如 3d 的例子，d = 3

一开始 i = d - 1 = 2

那么第一次循环，待处理的序号是

000，100

第二次循环，待处理的序号是

000，100，010，110

可见，按照寻找后 i 位为 0 的序号的规则，每一次增加的序号都是对应位为 1 的

那么其实每次增加的是要接受信息的

所以我们从对应位为 0 的发送到 1 的

这就是为什么 meg_destination := my_id XOR 2^t;

具体怎么判断对应位也很简单了，if (my_ud AND w^i) = 0 then

这真是太巧妙了……

只有当节点 0 是广播源时，才能执行该算法

对于任意源的广播，对所有节点的序号，和源节点的标号进行 XOR，这就完成了重新编号

procedure GENERAL_ONE_TO_ALL_BC(d, my_id, source, X)
begin
	my_virtual_id := my_id XOR source;
	mask := 2^d - 1;
	for i := d - 1 downto 0 do  /* Outer loop */
		mask := mask XOR 2^i;  /* Set bit i for mask to 0 */
		if (my_virtual_id AND mask) = 0 then
			if (my_virtual_id AND 2^i) = 0 then
				virtual_dest := my_virtual_id XOR 2^i;
				send X to (virtual_dest  XOR source);  /* Convert virtual_dest to the label of the physical destination */
			else
				virtual_source := my_virtual_id XOR 2^i;
				receive X fom (virtual_source XOR source);  /* Convert virtual_source to the label of the physical source */
			endelse
		endfor
	endif
end GENERAL_ONE_TO_ALL_BC

归约类似

成本分析

p 个节点，使用递归加倍，需要广播 $\log p$ 次

所以总时间为 $T=(t_s+t_{w}m)\log p$

多对多广播和归约

矩阵相乘、矩阵-向量相乘

如果顺序执行 p 个一对多广播，那么开销就是一对多广播的 p 倍

如果并行执行 p 个一对多广播，把所有在同一条路劲上传送的消息链接成一个长度为各个消息长度总和的消息进行发送，利用率更高

线性阵列和环

归约作为对偶操作，可以通过反转消息的方向和顺序来实现

格网

先对每一行，再对每一列

其中 my_id - (my_id mod sqrt p) 等于行数 * $\sqrt{p}$，那么后面的就是列号

超立方体

拓展到超立方体像这样

通信的两个节点的最低有效位不同，用 XOR 2^i 来区分

归约，看不懂了

senloc 指向即将发送的消息的开始位置

recloc 指向累积接收到的消息的位置

看这个图可能更能看懂一点，每次传送的消息的长度是 2 的幂

成本分析

环或者线性阵列中，每一次传一个消息，传 p - 1 次，所以用时 $T=(t_s+t_{w}m)(p-1)$

这实际上是流水线广播

流水线广播提高性能的例子：

高斯消元法、回代法亿记寻找图中最短路径的 Floyd 算法

格网中，第一阶段是传 $\sqrt{p}$ 个消息，每个消息的长度是 $m$，第二个阶段是传 $\sqrt{p}$ 个消息，每个消息的长度是 $m\sqrt{p}$，所以用时 $T=(t_s+t_{w}m)(\sqrt{p}-1)+(t_s+t_{w}m\sqrt{p})(\sqrt{p}-1)=2t_s(\sqrt{p}-1)+t_{w}m(p-1)$

p 个节点的超立方体中，维度为 $\log p$，传送 $\log p$ 次，第 $i$ 次传送的消息的长度为 $2^i$，所以用时为 $T={\sum }_{i=1}^{\log p}(t_s{2}^{i-1}{t}_{w}m)=t_s\log p+t_{w}m(p-1)$

可见，超立方体并不优于其他结构

超立方体的算法不能直接应用在别的结构中，可能存在拥塞

全归约与前缀和操作

全归约：先进行多对一归约，再进行一对多广播

但是使用多对多广播，可以更快地进行全归约操作

散发和收集

散发（一对多私自通信）

收集（连接）

与一对多广播不同

成本分析

$T=t_s\log p+t_{w}m(p-1)$

多对多私自通信

多对多私自通信（总体交换）

例子：快速傅里叶变换、矩阵转置、样本排序以及某些并行数据库连接操作

环

每个节点都要发送 m(p-1) 个消息

假设是节点 0 作为源，这 m(p-1) 个消息中，第 1 个是 0 发给 1，第二个是 0 发给 2，以此类推……

在第一步，所有节点都发送 m(p-1) 个消息，然后每个节点都从受到的消息中取出自己需要的那一份，然后把剩下的部分再往下传

以此类推

成本分析

第 $i$ 步中，传送消息的大小为 $m(p-i)$，这个操作耗费的总时间

从另一个角度，每一个 m 字的包的平均传送距离是 ${\sum }_{i=1}^{p-1}i/(p-1)=p/2$

一个节点发送了 $m(p-1)$，所有节点发送的数据量为 $$m(p-1)p$$。乘以平均传送距离，总通信量为 $m(p-1)p/2\ast p$

网络中的链路数量为 $p$，那么假设所有链路平均分担通信，通信时间为 $m(p-1)p/2$

可见，之前提出的方法就是最优的

格网

这里的格网的每一行每一列都是一个环

第一阶段，每个节点都对自己的消息平均分为 $\sqrt{p}$ 组

比如节点 0 的消息有

[0,0], [0,3], [0,6]
[0,1], [0,4], [0,7]
[0,2], [0,5], [0,8]

第一行所代表的组相当于 0 发送到 0

第二行所代表的组相当于 0 发送到 1

第三行所代表的组相当于 0 发送到 2

其他同理

第二个阶段，对自己的消息重新排列一下，

比如第二个阶段开始时，节点 0 的消息有

[0,0], [0,3], [0,6]
[1,0], [1,3], [1,6]
[2,0], [2,3], [2,6]

其中应该把 [0,0] [1,0] [2,0] 排成一组，作为 0 发送给 0 的那组，以此类推

成本分析

因为格网的每一行每一列都是一个环，所以可以用上之前在环的成本分析中的公式

现在格网的两个阶段的操作是相同的，但是每一个阶段的参与的节点数是 $\sqrt{p}$，传递的消息大小 $m\sqrt{p}$

那么每一个阶段耗费的时间为 $t_s+t_{w}mp/2(\sqrt{p}-1)$

总时间就是 $T=(2t_s+t_{w}mp)(\sqrt{p}-1)$

其中不包含数据重新排列的时间

因为这是环的推广，所以也是最优的

超立方体

成本分析

$\log p$ 次迭代，每次传 $mp/2$ 那么总时间为 $T=(t_s+t_{w}mp/2)\log p$

这里没有包括重新排序的时间

每一步，每一个节点要重新排列 $mp$ 个字的时间

总时间就是 $t_{r}mp\log p$。其中 $t_r$ 表示节点的本地存储器上执行一次读写一个字的操作所需要的时间

从另一个角度，每个节点都发送和接收 $m(p-1)$ 字的数据，并且超立方体中的任意两个节点间的平均距离为 $(\log p)/2$，所以网络中的总数据量为 $pm(p-1)(\log p)/2$

超立方体网络中总共有 $(p\log p)/2$ 条通信链路，所以时间下界为

$T=\frac{t_{w}pm(p-1)(\log p)/2}{(p\log p)/2}=t_{w}m(p-1)$

这表明，超立方体的算法反而不是最优的

优化算法实例