任务调度、负载平衡技术与停机准则

任务调度、负载平衡技术与停机准则两种主要并行开销：进程交互进程空闲：负载不平衡、任务依赖优良调度必须尽量达到两个目标：减少不同进程上任务之间的依赖减少由于负载不平衡引起的进程空闲两个目标通常相互冲突，任务调度并不简单2024/2/41任务调度、负载平衡技术与停机准则(续)负载平衡是减少进程空闲的必要条件，但并非充分条件123456789101112P0P1P2P3开始同步结束t=0t=2t=32024/2/42任务调度、负载平衡技术与停机准则(续)负载平衡是减少进程空闲的必要条件，但并非充分条件147102581136912P0P1P2P3开始同步结束t=0t=3t=62024/2/43任务调度、负载平衡技术与停机准则(续)静态调度在算法执行之前事先进行任务分配对静态生成的任务，可用静态调度，也可用动态调度采用静态调度时，并行算法的设计与编程比较容易动态调度程序执行过程中在进程间分配任务不知道任务的计算量，静态调度有可能引起严重的负载不平衡，或者任务是动态生成的采用动态调度时，并行算法的设计与编程比较复杂2024/2/44静态调度策略基于数据划分的静态调度基于任务分解的静态调度混合调度2024/2/45基于数据划分的静态调度数组分布方法块分布：将数组中连续的部分数据分布到进程上循环块分布与循环分布随机块分布图划分方法2024/2/46块分布一个d维数组通过沿某几个具体的维，将一个数据块分布到进程上当交互具有局部性时，块分布十分有效可以分为一维块分布与多维块分布两类2024/2/47块分布(续)一维块分布示例按行块分布P0P2P3P1按列块分布P0P1P2P32024/2/48块分布(续)二维块分布示例4

4块分布P0P8P12P4P1P9P13P5P2P10P14P6P3P11P15P72

4块分布P0P1P2P3P4P5P6P72024/2/49块分布(续)一般高维分布下可以利用更多的进程来并行计算矩阵乘法就是典型例子对许多问题，高维分布除了提供更高的并发度外，也有助于减少进程交互矩阵乘法的例子2024/2/410块分布(续)二维分布有利于减少矩阵乘法中的进程交互开销ACBP0P1P4P5P2P3P6P7P8P9P12P13P10P11P14P15P0P1P4P5P2P3P6P7P8P9P12P13P10P11P14P15P0P1P4P5P2P3P6P7P8P9P12P13P10P11P14P15AP0P2P3P1CP0P2P3P1BP0P2P3P12024/2/411循环块分布当对每个矩阵元素，其计算量相差比较大时，采用块分布将引起严重的负载不平衡。例如，稠密矩阵的LU分解Col_LU(A,n)Fork=1tondoForj=ktondoA(j,k):=A(j,k)/A(k,k);Forj=k+1tondoFori=k+1tondoA(i,j):=A(i,j)–A(i,k)

A(k,j);EndforEndfor2024/2/412循环块分布(续）采用3

3块分布时形成的14个任务2024/2/413循环块分布(续）循环块分布是块分布的一种变种，它有利于减轻负载不平衡程度与减少进程空闲将数组划分为多个块，使块的数量远大于进程数，再将块以循环方式分布到进程当每个块只有一个单位时，称为循环分布块分布也是循环分布的特例2024/2/414循环块分布(续）一维循环块分布与二维循环块分布的例子一维循环块分布P0P1P2P3P0P1P2P3P0P1P2P32

2循环块分布P0P0P2P2P1P1P3P3P0P0P2P2P1P1P3P32024/2/415随机块分布

当任务分布具有一些特殊模式时，块循环分布可能也不能使得负载平衡，例如08124191352101463111570812419135210146311157081241913521014631115708124191352101463111572024/2/416随机块分布(续)引入长度为

p的数组V，对0

j<

p，置V(j)的值为j对V随机置换，将置换后V(k

:(k+1)

-1)对应的块分布到进程k上下图给出了

＝3且p=4时的一个例子V=[0,1,2,3,4,5,6,7,8,9,10,11]random(V)=[8,2,6,0,3,7,

11，1,9,

5,4,10]2024/2/417图划分方法有许多算法是针对稀疏数据结构的：在对许多物理现象进行模拟时，可先对待求解的物理区域进行离散，代之以许多网格单元，于是问题就转化为计算网格单元的网格点对应的物理量在这些算法中，数据元素间的交互具有高度的不规则性，与网格点的分布有关2024/2/418图划分方法(续)苏必利尔(Superior)湖进行污染物扩散模拟时的一个离散网格2024/2/419图划分方法(续)随机分布时的交互开销很大2024/2/420图划分方法(续)对网格进行分块分布有利于减少交互开销2024/2/421基于任务分解的静态调度适用于可以用任务依赖图来描述，且事先知道每个任务的计算量的问题必须尽量保持负载平衡，同时尽量使得具有依赖关系的任务分布到一个进程上2024/2/422基于任务分解的静态调度(续)将完全二叉树调度到8个进程上的例子P0P0P4P0P2P4P6P0P2P4P6P1P3P5P72024/2/423基于任务分解的静态调度(续)在块分布下稀疏矩阵乘以向量的图示2024/2/424基于任务分解的静态调度(续)利用任务依赖图分布稀疏矩阵乘以向量中的任务

P0：(0,4,5,8)；P1：(1,2,3,7)；P2：(6,9,10,11)。

C0=(1,2,6,9)；

C1＝(0,5,6)；C2=(1,2,4,5,7,8)。012374568910112024/2/425混合调度有些算法单纯基于任务依赖图来调度时负载严重不平衡，或者并发度不高在树型任务依赖图中，对靠近根结点的任务，如果计算量较大，可以再进行分解

2024/2/426动态调度策略当静态调度导致负载严重不平衡，或有任务动态生成时，就必须采用动态调度采用动态调度的根本原因是为了平衡负载，所以也常称为动态负载平衡将介绍的内容集中式动态调度分布式动态调度分布式动态调度中的终止检测算法2024/2/427集中式动态调度所有任务用一个集中式的数据结构来维护，或者由一个或一组进程来维护一旦一个进程空闲，就从主进程或集中式数据结构提取部分任务一旦生成一个新任务，就将其加入集中式数据结构，或向主进程报告该任务的产生集中式调度策略一般比分布式任务调度策略更容易实现，但可扩展性较差2024/2/428集中式动态调度(续)集中式动态调度图示集中式任务池进程进程

进程请求任务，同时可能提交新任务；分配任务2024/2/429集中式动态调度(续)如果每个任务的计算时间为M，且需要

时间将一个任务调度到一个进程，那每个时候最多只能有M/

个进程同时执行。M=3

的例子：t=0123456782024/2/430集中式动态调度(续)为了缓解瓶颈问题，可以采取如下措施：一次调度多个任务，但又存在负载不平衡的潜在问题利用一组进程来控制为应对负载不平衡，可以采用如下措施：随着程序的不断运行，不断减少每次调度的任务个数先调度计算量较大的任务，将计算量较小的任务推迟调度

2024/2/431集中式动态调度(续)需要满足以下两个条件，才能终止：任务队列为空；每个进程都处于空闲状态。尚在运行的其它进程可能新产生任务，不能单凭任务队列为空来判别对象曼德勃罗特集这种不会产生新任务的计算，可通过只检测任务队列是否为空来判别是否终止有些应用中，一个从进程通过本地终止条件就可以检测出整个计算过程的终止条件，如搜索算法2024/2/432分布式动态调度在分布式动态调度中，可执行的任务分布在所有进程上，在执行时，进程间通过交互来进行负载平衡每个进程都可以从其它进程接收任务，也可以将任务发给其他进程影响分布式动态调度有效性的几个参数：发送与接收进程如何配对？如循环算法与随机算法等任务的传输是由发送进程启动，还是由接收进程启动？每次交互传输多少任务？什么时候开始任务传输？空闲时还是预先进行？2024/2/433分布式动态调度中的终止检测算法在t时候，需要同时满足两个条件，才能终止:在t时候，对所有进程，都已经满足局部终止条件；在t时候，进程间没有消息在传送第二个条件是因为传递中的消息还可能在一个已经终止的进程上启动新的任务分布式动态调度中的终止检测算法：应答式算法；环形检测算法；固定能量检测算法2024/2/434应答式算法每个进程处于两种状态：活跃与不活跃。开始时，没有任何任务执行，所有进程都处于不活跃状态一个进程接收到任务后，就处于活跃状态，发送任务使其处于活跃状态的进程称为其父进程，每个进程都有唯一的父进程每次向另一进程发送任务时，都等待对方的应答当进程每次从其它非父进程接收一个任务时，就立即发送一个应答消息，对来自父进程的第一个任务，并不立即发送应答消息当一个进程准备进入不活跃状态时，给父进程发送一个应答消息2024/2/435应答式算法(续)一个进程只有在满足以下条件时，才能进入不活跃状态：已经满足本地终止条件；对接收到的所有任务发送了应答消息；收到了其发出去的所有任务的应答消息当根进程处于不活跃状态时，整个计算过程就终止2024/2/436应答式算法(续)应答式算法的图示56-32-1632-12-4-6-216-4-412-44+44+6-24+2+22024/2/437环形检测算法单通环形终止检测算法如下：当P0已经终止时，产生一令牌传给P1；当Pk接收到令牌且已经终止时，将令牌传给P(k+1)%p；当P0接收到令牌后，就知道所有进程都已经终止。一个进程满足本地终止条件后可能重新激活，如采用工作池模式设计的并行算法，这时算法不再适用。可以推广到树型结构：对任何一个结点，当它收到所有子结点的令牌且满足本地终止条件时，就向父接点传递令牌。2024/2/438环形检测算法(续)双通环形终止检测算法：P0终止时，产生白色令牌传递给P1；记令牌所处当前进程为Pk，如果Pi(i>=k)向某个进程Pj(j<k)发送消息，则将进程Pi标志为黑色，否则为白色；如果令牌传输时遇到黑色进程，则将令牌变为黑色,令牌传出后，进程变为白色；如果P0接收到白色令牌，则所有进程都已经终止，如果接收到黑色令牌，则继续传递。2024/2/439固定能量检测算法能量的意义与令牌的意义很相似，但这里的能量有一个具体的数值任务开始执行之前，所有能量都在主进程中，它将部分任务以及与任务对应的能量传给请求任务的进程进程收到任务请