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

2020/5/14,-,1,任务调度、负载平衡技术与停机准则,两种主要并行开销：进程交互进程空闲：负载不平衡、任务依赖优良调度必须尽量达到两个目标：减少不同进程上任务之间的依赖减少由于负载不平衡引起的进程空闲两个目标通常相互冲突，任务调度并不简单,2020/5/14,-,2,任务调度、负载平衡技术与停机准则(续),负载平衡是减少进程空闲的必要条件，但并非充分条件,2020/5/14,-,3,任务调度、负载平衡技术与停机准则(续),负载平衡是减少进程空闲的必要条件，但并非充分条件,2020/5/14,-,4,任务调度、负载平衡技术与停机准则(续),静态调度在算法执行之前事先进行任务分配对静态生成的任务，可用静态调度，也可用动态调度采用静态调度时，并行算法的设计与编程比较容易动态调度程序执行过程中在进程间分配任务不知道任务的计算量，静态调度有可能引起严重的负载不平衡，或者任务是动态生成的采用动态调度时，并行算法的设计与编程比较复杂,2020/5/14,-,5,静态调度策略,基于数据划分的静态调度基于任务分解的静态调度混合调度,2020/5/14,-,6,基于数据划分的静态调度,数组分布方法块分布：将数组中连续的部分数据分布到进程上循环块分布与循环分布随机块分布图划分方法,2020/5/14,-,7,块分布,一个d维数组通过沿某几个具体的维，将一个数据块分布到进程上当交互具有局部性时，块分布十分有效可以分为一维块分布与多维块分布两类,2020/5/14,-,8,块分布(续),一维块分布示例,2020/5/14,-,9,块分布(续),二维块分布示例,2020/5/14,-,10,块分布(续),一般高维分布下可以利用更多的进程来并行计算矩阵乘法就是典型例子对许多问题，高维分布除了提供更高的并发度外，也有助于减少进程交互矩阵乘法的例子,2020/5/14,-,11,块分布(续),二维分布有利于减少矩阵乘法中的进程交互开销,2020/5/14,-,12,循环块分布,当对每个矩阵元素，其计算量相差比较大时，采用块分布将引起严重的负载不平衡。例如，稠密矩阵的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);EndforEndfor,2020/5/14,-,13,循环块分布(续）,采用33块分布时形成的14个任务,2020/5/14,-,14,循环块分布(续）,循环块分布是块分布的一种变种，它有利于减轻负载不平衡程度与减少进程空闲将数组划分为多个块，使块的数量远大于进程数，再将块以循环方式分布到进程当每个块只有一个单位时，称为循环分布块分布也是循环分布的特例,2020/5/14,-,15,循环块分布(续）,一维循环块分布与二维循环块分布的例子,2020/5/14,-,16,随机块分布,当任务分布具有一些特殊模式时，块循环分布可能也不能使得负载平衡，例如,2020/5/14,-,17,随机块分布(续),引入长度为p的数组V，对0j=k)向某个进程Pj(jk)发送消息，则将进程Pi标志为黑色，否则为白色；如果令牌传输时遇到黑色进程，则将令牌变为黑色,令牌传出后，进程变为白色；如果P0接收到白色令牌，则所有进程都已经终止，如果接收到黑色令牌，则继续传递。,2020/5/14,-,40,固定能量检测算法,能量的意义与令牌的意义很相似，但这里的能量有一个具体的数值任务开始执行之前，所有能量都在主进程中，它将部分任务以及与任务对应的能量传给请求任务的进程进程收到任务请求，也将其上的部分任务和对应的能量传给请求进程一个进程完成当前任务后，需要将其上的能量传给主进程或任务的来源进程。对后一种情况，一个进程在它发出的所有能