分布式-chapter3-Parallel Algorithm Design

1. 算法设计方法

1.1 Foster设计方法

并行算法设计的四个阶段：

1. Partitioning（分区）
2. Communication（通信）
3. Agglomeration（聚集）
4. Mapping（映射）

分区和通信 : 处理机器独立的问题，影响并发性和可伸缩性
聚集和映射 : 处理与机器相关的问题，影响局部性和其他性能问题

1.1.1 Partitioning（分区）

1. 将要执行的计算或计算操作的数据分成小任务

2. 尽可能多的确定可以并行执行的任务

3. 两种方法

   区域分解：将数据分成几部分，确定如何将计算与数据相关联

   1. 如果可能，将数据切分成大小相等的小块
   2. 生成多个任务，每个任务都有一些数据和数据操作集
   3. 好的经验法则是首先关注最大的数据结构或者最常访问的数据结构

   功能分解：将计算分成几部分，确定如何将数据与计算相关联

   1. 最初的重点是要执行的计算，而不是数据
   2. 功能分解是区域分解的补充策略
   3. 这些任务的数据需求可能是脱节的，或者它们可能会有很大的重叠
   4. 通常，函数分解产生的任务集合通过流水线实现并发
   5. 功能分解作为程序结构化技术也发挥着重要作用

   比较：每个组件可以使用区域分解技术自然的并行化，如果系统首先使用功能分解技术分解，那么作为一个整体，并行算法会更简单

4. 分区检查清单

   1. 您的分区定义的任务是否至少比目标并行计算机中的处理器多一个数量级？（如果该条件不能满足的话，则后面的设计将受到很大限制）
   2. 您的分区是否避免了冗余计算和存储需求？（如果该条件不能满足的话，则该设计 在问题规模增加的时候可能效果不佳）
   3. 任务的大小是否大致相同？（如果该条件不能满足的话，则难以平衡处理器之间的工作）
   4. 任务数量是问题规模的增函数吗？（如果该条件不能满足的话，则也许不能使用更多的处理器去求解更大规模的问题）
   5. 您是否确定了几个可选分区？（如果该条件不能满足的话，则也许不需要使用该分区方法）

1.1.2 Communication（通信）

确定在前一步确定的任务中需要进行什么沟通

对于功能分解易，对于区域分解难

通信模式分类一：

1. 本地通信

   任务需要来自少量相邻任务的值
   创建说明数据流的通道

   

2. 全局通信

   大量相邻任务和远程任务都提供数据来进行运算
   通常，不要在设计早期为它们创建通道
   可能会导致过多的通信或可能限制并发执行的机会

   

在基于纯本地通信的算法中，有两个普遍问题会阻碍并发：

1. 算法是集中的：它不分配计算和通信，每个操作都必须有一个单独的任务参与
2. 算法是顺序的：它不允许多个计算和通信操作并发执行

解决方法：

1. 分布式通信计算

   1. 一种求和算法，将数组中的N个任务连接起来，以便对分布在这些任务中的N个数字求和。
   2. 每个通道都标有使用该通道的步骤号和在其上通信的值。
   3. 单个求和仍然需要N-1步，但是只有当多个求和操作要执行时，才允许并发执行。
   4. 
   5. 通过使每个任务 i 分配 N 个数字的总和，计算总和Si=Xi+Si-1

2. 分而治之

   1. 为了解决一个复杂的问题，要把它划分成两个或更多大小大致相同的较简单的问题。这个过程被递归地应用来产生一组不能被进一步细分的子问题。
   2. 当问题划分产生的子问题能够并行解决时，分治法在并行计算中是有效的。
   3. 完整的和在logN步骤之后的树的根处可以求到。
   4. 其结果是一个常规的通信结构，其中每个任务与一小组邻居通信。
   5. 

通信模式分类二：

1. 结构化通信

   一个任务和它的邻居形成一个规则的结构，例如：树或网格

2. 非结构化通信

   1. 网络可能是任意的图形

   2. 非结构化通信使聚集和映射任务复杂化。

   3. 如果通信需求是动态的，那么必须在程序执行期间频繁地应用负载平衡算法，并且必须权衡这些算法的成本和收益。

      通信 :

      1. 任务间的通信是并行算法开销的一部分。
      2. 最小化并行开销是并行算法设计的一个重要目标。

通信检查清单：

1. 任务之间的通信操作是否平衡？（不平衡的通信需求意味着一个不可伸缩的结构。重新审视您的设计，看看是否可以更公平地分配通信操作。例如，如果频繁访问的数据结构封装在单个任务中，请考虑分发或复制此数据结构。）
2. 每个任务是否与少量邻居通信？（如果每个任务必须与许多其他任务进行通信，请评估在本地通信结构方面形成这种全局通信的可能性。）
3. 通信操作能否同时进行？（否则，您的算法可能效率低下且不可缩放。尝试使用分治技术来揭示并发性）
4. 不同任务的计算是否能够同时进行？（否则，您的算法可能效率低下且不可缩放。考虑是否可以重新排序通信和计算操作）

1.1.3 Agglomeration（聚集）

将前两个步骤中确定的任务和通信合并为更大的任务。

在聚集期间，考虑合并是否有用，并确定是否值得复制数据和/或计算。

eg：

目标：

1. 提高性能

   1. 降低通信成本

   合并由一个信道连接的任务，消除了通信，增加了并行算法的局部性，图a
   合并发送和接收任务可以减少消息的发送次数,图b

   

   2. 更少的任务创建成本和任务调度成本。

2. 保持程序的可扩展性

   假设我们正在操作一个尺寸为8 x 128 x 256的3D矩阵，我们的目标机器是一个具有4个cpu的中央多处理器。

   问题一：假设我们把第2维和第3维集合起来。我们可以在目标机器上运行吗?

   答：可以的，因为我们有这样的任务，每个任务对应2 x 128 x 256的子矩阵。

   问题二：假设我们将目标机器改为一个具有8个cpu的中央多处理器。我们之前的设计能基本完成吗?

   答：可以的，因为每个任务可以处理1 x 128 x 256的矩阵。

   问题三：但是，如果我们去超过8个cpu呢?如果我们把第2维和第3维结合起来得到8 x 128 x 256矩阵，我们的设计会改变吗?

   答：是的，设计需要改变。这说明把2维和3维聚集在一起的决定从长远上来看是有一定的缺点的，即代码在更多cpu上的可移植性受到损害。

3. 简化编程

讨论：

1. 关于聚集和复制，这三个目标导向的决策有时会产生冲突。

   可以通过增加计算和通信粒度来降低通信成本，在可伸缩性和映射决策方面保持灵活性，并降低软件工程成本。

2. 增加粒度

   通过发送更少的数据来减少通信时间。即使我们发送相同数量的数据，也可以通过使用更少的消息来实现。
   还可以降低任务创建成本。
   方法：表面对体积效应；复制计算；避免通信。

3. 表面对体积效应

   

   8*8 网格上的计算被划分为 8*8个任务，每个任务负责一个点

   问题一：需要多少通信？

   答：每个任务需要4次，共需要64*4次通信

   问题二：传输了多少数据值？

   答：256个

   

   同样的计算分成2*2个任务，每个任务负责16个点

   问题一：需要多少次通讯？

   答：总共4*4=16

   问题二：传输了多少数据值？

   答：16*4=64个值

   结论： 一个任务的通信需求与它所操作的子域的表面成正比，而计算需求与子域的体积成正比

4. 复制计算

   有时我们可以权衡复制计算以减少通信需求和/或执行时间。
   

   

   先进行求和，再进行通信，那么经过在 2(N-1) 步之后，N 个值的总和被复制到 N 个任务中的每一个中。

   1. 一种替代算法，执行时间更短，但代价是不必要的(复制的)计算和通信。其基本思想是并发执行多个求和，每个并发求和在不同的任务中产生一个值。
   2. 我们首先考虑一种基于这种思想的数组求和算法。在这个变体中，任务被连接成一个环而不是一个数组，所有N个任务执行相同的算法，使得N个部分和同时运动。在N-1步之后，在每个任务中复制完整的和。这种策略避免了后续广播操作的需要，但以（N-1）^2冗余加法和(N-1)^2不必要的通信为代价。但是，求和和和广播是以N-1而不是2（N-1）步完成的。因此，如果处理器在等待求和结果时处于空闲状态，则该策略会更快。

5. 保持灵活性

   1. 如果程序要具有可移植性和可扩展性，那么创建不同数量的任务的能力至关重要。
   2. 在为特定计算机调整代码时，这种灵活性也很有用。
   3. 如果任务在等待远程数据时经常阻塞，那么将多个任务映射到一个处理器是有益的。
   4. 重叠计算和通信：一个任务的通信与另一个任务的计算重叠。
   5. 创建比处理器更多的任务为在可用处理器上平衡计算负载的映射策略提供了更大的范围。

6. 降低软件工程成本

   1. 当并行化现有的顺序代码时，另一个问题是与不同分区策略相关的相对开发成本。
   2. 从这个角度来看，最有趣的策略可能是那些避免大量代码更改的策略。

聚集检查清单：

1. 聚集是否通过增加地域性降低了通信成本？（如果不是，请检查您的算法，以确定是否可以使用其他聚集策略来实现这一点。）
2. 如果聚合复制了计算，那么对于一系列问题大小和处理器数量，您是否验证了这种复制的好处大于其成本？
3. 如果聚合复制数据，您是否验证了这不会通过限制问题大小或处理器计数的范围而影响算法的可伸缩性？
4. 聚合是否产生了相似的计算和通信成本任务？（聚集所产生的任务越大，它们具有相似的成本就越重要。如果每个处理器只创建一个任务，那么这些任务的开销应该几乎相同。）
5. 任务的数量是否仍随问题的大小而变化？（如果不是，那么你的算法就不能在大型并行计算机上解决更大的问题。）
6. 如果您排除了并发执行的机会，您是否验证了当前和将来的目标计算机有足够的并发性？（如果其他算法的通信开销过大，那么并发性不足的算法可能仍然是最有效的；性能模型可以用来量化这些权衡。）
7. 在不引入负载不平衡、增加软件工程成本或降低可伸缩性的情况下，任务的数量还能进一步减少吗？（在其他条件相同的情况下，创建较少大粒度任务的算法通常比创建许多细粒度任务的算法更简单、更高效。）
8. 如果您正在并行化一个现有的顺序程序，您是否考虑过修改顺序代码所需的成本？（如果这些成本很高，那么可以考虑增加代码重用机会的其他聚合策略。如果生成的算法效率较低，请使用性能建模技术来估计成本权衡。）

1.1.4 Mapping（映射）

将任务分配给处理器的过程

开发映射算法的目标通常是最小化总执行时间。映射的冲突目标：

1. 最大化处理器利用率，即系统处理器积极执行解决问题所需任务的平均时间百分比。(通过计算平衡)
2. 最小化处理器间通信(映射到同一处理器的通信进程)

这样做应该使通信最小化，并且每个进程/线程得到大致相同的工作量。

eg：

最佳映射：

1. 寻找最佳映射是一个NP难问题
2. 必须依赖于启发式

映射决策树（映射策略）：

1. 静态任务数

   结构化通信：

   1. 每个任务的恒定计算时间：聚合任务以最小化通信；每个处理器创建一个任务
   2. 每个任务的可变计算时间：循环映射任务到处理器

   非结构化通信：

   使用静态负载平衡算法

2. 动态任务数

   任务之间频繁的通信 :

   使用动态负载均衡算法

   许多短期任务(没有任务间通信) :

   使用运行时任务调度算法

映射检查清单：

1. 考虑基于每个处理器一个任务和每个处理器多个任务的设计
2. 评估静态和动态任务分配
3. 如果使用集中式负载均衡方案，您是否验证过管理器不会成为瓶颈？（通过将指向任务的指针（而不是任务本身）传递给管理器，可以降低这些方案中的通信成本。）
4. 如果使用动态负载平衡方案，您是否评估过不同策略的相对成本？（一定要在分析中包括实现成本。概率或循环映射方案很简单，应始终予以考虑，因为它们可以避免重复的负载平衡操作。）
5. 如果使用概率或循环方法，您是否有足够多的任务来确保合理的负载平衡？（通常，任务数至少是处理器所需任务数的十倍。）

2. 案例研究

2.1 边界值问题

棒随着时间推移而冷却

有限差分近似

分区：

1. 每个网格点一个数据项
2. 每个网格点关联一个基本任务
3. 二维域分解

通信：

1. 确定基本任务之间的通信模式
2. 每个内部基本任务有三个传入和三个传出通道

聚集和映射：

并行执行时间：

1. p-处理器的数量
2. λ-信息通信的时间
3. x-表示计算ui,j+1所需的时间，已知ui−1,j, ui,j，和ui+1,j
4. m-迭代次数
5. 串行执行时间：m(n-1)x
6. 并行执行时间：m(x⌈(n-1)/p⌉+2λ)

比较：

n-1	m	Sequential	Task/Channel with p << n-1
		m **(**n-1) x	m（x⌈(n-1)/p⌉+2λ）
48	100	4800x p = 1	600x + 200λ p = 8
48	100	ditto	300x + 200λ p = 16
8K	100	~(800K)x	~800x + 200λ p = 1000
64K	100	~(6400K)x	~6400x + 200λ p = 1000

2.2 寻找最大值

1. 考虑到结合运算符： ⊕

2. a0⊕a1⊕a2⊕…..⊕an-1

3. 例子：add，multiply，and，or，maximum，minimum

并行规约：

n-1个任务———>两个（n-1）/2个任务———>四个(n-1)/4任务……

二叉树（由根逐渐向根节点扩展）：

超立方体的子图：

求全局和：

生成的二叉树：

聚集：

并行执行时间：

1. x:进行依次二进制操作的时间
2. λ:信息传递的时间
3. n个值分给p个任务，每个任务至多有⌈n/p⌉个值
4. 所有任务同时执行，计算所需的时间为(⌈n/p⌉-1)x
5. p个任务之间的通信的步骤为⌈logp⌉
6. 接受进程等待并且执行需要的时间为λ+x
7. 总计时间为(⌈n/p⌉-1)x+⌈logp⌉(λ+x)

2.3 N-Body问题

分区：

1. 每个粒子有一项任务
2. 任务有粒子的位置，速度向量
3. 迭代：获取其他粒子的位置；计算新的位置，速度

通信：

1. 聚集（gather）操作：采用分布在一组任务中的数据集并收集单个任务上的项的全局通信；将数据项b、c和d连接到包含a的进程中。

   

2. 聚集所有（all-gather）操作 : 与聚集类似，除了在通信结束时，每个任务都有整个数据集的副本。在当前上下文中用于更新每个粒子的位置。经过n ~ 1个通信步骤后，每个任务拥有所有其他粒子的位置。可以通过超立方体拓扑结构实现logn级别的通信

   相邻的两个节点进行一次通信。（比如0就有了0和1的信息，2就有了2,3的信息。）
   奇数处理器之间交换两个粒子，偶数处理器之间交换两个粒子（0和2进行交换，1和3进行交换）
   继续，直到所有处理器都有所有的粒子，每一步都增加粒子的数量

   原始图：

   

   超立方图：

   

聚集和映射：

假设n是p的倍数且n远远大于p，每个任务处理n/p个粒子

all-gather的通信需要logp个粒子

• 第一步中，消息的长度为n/p

• 第二步中，消息的长度为2n/p

• 分析

  • λ为初始化通信的延迟
  • β为带宽
  • 发送具有n个物体的消息现在需要λ+n/β
  • logp次迭代的通信时间：∑（1->logp）(λ+2^(i-1)*n/βp)=λ log p + n(p − 1) /βp
  • 执行一次计算的时间为x
  • 每一次并行的计算时间：χ*(n/p)

• 采用两种方法的通信时间：

  

• 计算时间：χ*(n/p)

• 总时间为通信时间+计算时间。

2.4 增加数据输入

• 并行程序输入n个粒子的初始位置和速度矢量
  • 假设一个任务负责所有IO
  • 打开数据文件，读取n个粒子的位置和速度
  • 输入或输出n个数据元素所需的时间:λio+n/βio
  • 读取所有n个粒子的位置(2个数据项作为x和y坐标)和速度的时间:λio+4n/βio
• 通信
  • 将输入数据分成若干块，为每个任务分配n/p个元素
  • 分散（scatter）操作-集合（gather）的反向操作
  • 依次向每个任务发送正确的n/p粒子
    • p-1条消息，每一个的长度为4n/p（位置坐标x，y和速度坐标vx和vy所以为4）
    • 时间：(p − 1)(λ + 4n/(pβ))
  • 推导一个需要log p通信步骤的分散（scatter）操作
    • 将列表的一半发送给另一个任务
    • 接下来，每个进程将1/4列表发送给以前不活动的任务
    • 然后继续发送前一步的一半
    • 时间：∑（1->logp）(λ+4n/(2^i)βp)=λ log p + 4n(p − 1) /βp
• 推导总时间
  • I/O的位置和速度的n个粒子是一个完全顺序的操作，需要时间：t0=2(λio + 4n/βio)
  • 计算开始时的散射和计算结束时的粒子收集都需要时间:t1=2(λ log p + 4n(p − 1) /βp)
  • 并行算法的每次迭代都需要粒子位置的全集通信，需要时间:t2=λ log p + 2n(p − 1)/ βp
  • 每个处理器执行它的计算份额，需要时间:t3=χ ⌈n/p⌉(n − 1)
  • 如果算法执行m次迭代，并行计算的总执行时间约为:t0+t1+m(t2+t3)

3. 总结

3.1 并行计算

任务集，通过渠道互动

3.2 好的设计

最大化本地计算；尽量减少沟通；按比例放大

3.3 设计步骤

1.分区计算
2.通信计算
3.聚集任务
4.任务映射到处理器
5.目标：-最大化处理器利用率；-最小化处理器间通信

3.4 基本算法

1. 规约

2. 聚集和分散（gather and scatter）

3. 全聚集(all gather)

参考资料

分布式并行计算第三章

不重复造轮子了，详细见博主一个点的分布式文章