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

1、2022-3-3编辑ppt1任务调度、负载平衡技术与停机准则任务调度、负载平衡技术与停机准则n两种主要并行开销：两种主要并行开销：v进程交互进程交互v进程空闲：负载不平衡、任务依赖进程空闲：负载不平衡、任务依赖n优良调度必须尽量达到两个目标：优良调度必须尽量达到两个目标：v减少不同进程上任务之间的依赖减少不同进程上任务之间的依赖v减少由于负载不平衡引起的进程空闲减少由于负载不平衡引起的进程空闲 v两个目标通常相互冲突，任务调度并不简单两个目标通常相互冲突，任务调度并不简单 2022-3-3编辑ppt2任务调度、负载平衡技术与停机准则任务调度、负载平衡技术与停机准则(续续)n负载平衡是减少进程空

2、闲的必要条件，但并非充负载平衡是减少进程空闲的必要条件，但并非充分条件分条件123456789101112P0P1P2P3开始 同步 结束t=0 t=2 t=32022-3-3编辑ppt3任务调度、负载平衡技术与停机准则任务调度、负载平衡技术与停机准则(续续)n负载平衡是减少进程空闲的必要条件，但并非充负载平衡是减少进程空闲的必要条件，但并非充分条件分条件147102581136912P0P1P2P3开始开始 同步同步 结束结束t = 0 t = 3 t = 0 t = 3 t=6t=62022-3-3编辑ppt4任务调度、负载平衡技术与停机准则任务调度、负载平衡技术与停机准则(续续)n静态调

3、度静态调度v在算法执行之前事先进行任务分配在算法执行之前事先进行任务分配 v对静态生成的任务，可用静态调度，也可用动态调度对静态生成的任务，可用静态调度，也可用动态调度v采用静态调度时，并行算法的设计与编程比较容易采用静态调度时，并行算法的设计与编程比较容易n动态调度动态调度v程序执行过程中在进程间分配任务程序执行过程中在进程间分配任务v不知道任务的计算量，静态调度有可能引起严重的负不知道任务的计算量，静态调度有可能引起严重的负载不平衡，或者任务是动态生成的载不平衡，或者任务是动态生成的 v采用动态调度时，并行算法的设计与编程比较复杂采用动态调度时，并行算法的设计与编程比较复杂2022-3-3

4、编辑ppt5静态调度策略静态调度策略n基于数据划分的静态调度基于数据划分的静态调度n基于任务分解的静态调度基于任务分解的静态调度n混合调度混合调度2022-3-3编辑ppt6基于数据划分的静态调度基于数据划分的静态调度n数组分布方法数组分布方法v块分布：将数组中连续的部分数据分布块分布：将数组中连续的部分数据分布到进程上到进程上v循环块分布与循环分布循环块分布与循环分布v随机块分布随机块分布n图划分方法图划分方法2022-3-3编辑ppt7块分布块分布n一个一个d d维数组通过沿某几个具体的维数组通过沿某几个具体的维，将一个数据块分布到进程上维，将一个数据块分布到进程上n当交互具有局部性时，块

5、分布十当交互具有局部性时，块分布十分有效分有效n可以分为一维块分布与多维块分可以分为一维块分布与多维块分布两类布两类2022-3-3编辑ppt8块分布块分布(续续)n一维块分布示例一维块分布示例按行块分布按行块分布P0P2P3P1按列块分布按列块分布P0 P1P2 P32022-3-3编辑ppt9块分布块分布(续续)n二维块分布示例二维块分布示例4 4 4 4块分布块分布P0P8P12P4P1P9P13P5P2P10P14P6P3P11P15P72 2 4 4块分布块分布P0P1P2P3P4P5P6P72022-3-3编辑ppt10块分布块分布(续续)n一般高维分布下可以利用更多的进程一般高维

6、分布下可以利用更多的进程来并行计算来并行计算v矩阵乘法就是典型例子矩阵乘法就是典型例子n对许多问题，高维分布除了提供更高对许多问题，高维分布除了提供更高的并发度外，也有助于减少进程交互的并发度外，也有助于减少进程交互v矩阵乘法的例子矩阵乘法的例子2022-3-3编辑ppt11块分布块分布(续续)n二维分布有利于减少矩阵乘法中的进程交互开销二维分布有利于减少矩阵乘法中的进程交互开销ACBP0P1P4P5P2P3P6P7P8P9P12P13P10P11P14P15P0P1P4P5P2P3P6P7P8P9P12P13P10P11P14P15P0P1P4P5P2P3P6P7P8P9P12P13P10P

7、11P14P15AP0P2P3P1CP0P2P3P1BP0P2P3P12022-3-3编辑ppt12循环块分布循环块分布n当对每个矩阵元素，其计算量相差比较大当对每个矩阵元素，其计算量相差比较大时，采用块分布将引起严重的负载不平衡。时，采用块分布将引起严重的负载不平衡。例如，稠密矩阵的例如，稠密矩阵的LULU分解分解Col_LU(A, n)For k = 1 to n do For j = k to n do A(j,k) := A(j,k) / A(k,k); For j = k+1 to n do For i = k+1 to n do A(i,j) := A(i,j) A(i,k) A(

8、k,j); EndforEndfor2022-3-3编辑ppt13循环块分布循环块分布(续）续）n采用采用3 3 3 3块分布时形成的块分布时形成的1414个任务个任务 2022-3-3编辑ppt14循环块分布循环块分布(续）续）n循环块分布是块分布的一种变种，它有利循环块分布是块分布的一种变种，它有利于减轻负载不平衡程度与减少进程空闲于减轻负载不平衡程度与减少进程空闲n将数组划分为多个块，使块的数量远大于将数组划分为多个块，使块的数量远大于进程数，再将块以循环方式分布到进程进程数，再将块以循环方式分布到进程n当每个块只有一个单位时，称为循环分布当每个块只有一个单位时，称为循环分布n块分布也是

9、循环分布的特例块分布也是循环分布的特例2022-3-3编辑ppt15循环块分布循环块分布(续）续）n一维循环块分布与二维循环块分布的例子一维循环块分布与二维循环块分布的例子一维循环块分布一维循环块分布P0P1P2P3P0P1P2P3P0P1P2P32 2循环块分布循环块分布P0P0P2P2P1P1P3P3P0P0P2P2P1P1P3P32022-3-3编辑ppt16随机块分布随机块分布 n当任务分布具有一些特殊模式时，块循环分布可能也不当任务分布具有一些特殊模式时，块循环分布可能也不能使得负载平衡，例如能使得负载平衡，例如081241913521014631115708124191352101

10、46311157081241913521014631115708124191352101463111572022-3-3编辑ppt17随机块分布随机块分布(续续)n引入长度为引入长度为 p p的数组的数组V V，对对0 0 j j =k)(i=k)向某向某个进程个进程P Pj j(j k)(j k)发送消息发送消息，则将进程则将进程P Pi i标志标志为黑色，否则为白色；为黑色，否则为白色；v如果令牌传输时遇到黑色进程，则将令牌变为如果令牌传输时遇到黑色进程，则将令牌变为黑色黑色, ,令牌传出后，进程变为白色令牌传出后，进程变为白色；v如果如果P P0 0接收到白色令牌，则所有进程都已经终接收

11、到白色令牌，则所有进程都已经终止，如果接收到黑色令牌，则继续传递。止，如果接收到黑色令牌，则继续传递。2022-3-3编辑ppt40固定能量检测算法固定能量检测算法n能量的意义与令牌的意义很相似，但这里的能量有一个能量的意义与令牌的意义很相似，但这里的能量有一个具体的数值具体的数值n任务开始执行之前，所有能量都在主进程中，它将部分任务开始执行之前，所有能量都在主进程中，它将部分任务以及与任务对应的能量传给请求任务的进程任务以及与任务对应的能量传给请求任务的进程n进程收到任务请求，也将其上的部分任务和对应的能量进程收到任务请求，也将其上的部分任务和对应的能量传给请求进程传给请求进程n一个进程完成当前任务后，需要将其上的能量传给主进一个进程完成当前任务后，需要将其上的能量传给主进程或任务的来源进程。对后一种情况，一个进程在它发程或任务的来源进程。对后一种情况，一个进程在它发出的所有能量都已收回出的所有能量都已收回，与本进程的剩余能量累加之后与本进程的剩余能量累加之后才会将其上的能量返回才会将其上的能量返回n当所有能量返回到主进程，且主进程空闲时，就满足了当所有能量返回到主进程，且主进程空闲时，就满足了全局终止条件全局终止条件2022-3-3编辑ppt41任务调度技术回顾任务调度技术回顾负负载载平平衡衡任任务务依依赖赖任务