并行计算负载平衡和终止检测

《并行计算负载平衡和终止检测》由会员分享，可在线阅读，更多相关《并行计算负载平衡和终止检测（64页珍藏版）》请在装配图网上搜索。

1、,单击此处编辑母版标题样式,,,,*,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,第七章 负载平衡和终止检测,Load Balancing and Termination Detection,负载平衡,----,在并行系统中，使各个节点尽量均衡地分配工作任务的技术。通过在处理机之间均衡地、合理地分配计算任务，以获得最大可能的执行速度。,,终止检测,----,检测一个计算任务何时已经结束。当计算是分布式时，检测计算的终止是一件困难的、且重要的问题。,主要内容,负载平衡,,静态负载平衡,,确定模式与非确定模式,,动态负载平衡,,集中式与分散式,,分布式终止检测方法,,终止

2、条件,,几个终止检测算法,,负载平衡和终止检测实例,主要内容,负载平衡,,静态负载平衡,,确定模式与非确定模式,,动态负载平衡,,集中式与分散式,,分布式终止检测方法,,终止条件,,几个终止检测算法,,负载平衡和终止检测实例,P,1,P,0,P,2,P,3,P,4,P,5,处理机,,,,,,,,time,一、负载平衡,,静态负载平衡,,动态负载平衡,负载平衡,,time,处理机,,P,1,P,0,P,2,P,3,P,4,P,5,,,,,,,负载平衡是利用调度程序实现的。,,调度的目的是通过将任务正确分配给各处理机，并使得任务按照一定的顺序执行，,以尽可能少的时间完成并行应用任务。,,在静态调度

3、中，调度通常是在编译时进行的。并行程序的特点（如：任务的执行时间、通信、数据的相互关联和同步等）在程序执行之前都是已知的。,,在动态调度中，并行程序的特点在执行之前往往知道得很少，因此，调度是在程序执行时进行的。它使程序的执行时间和调度时间尽可能最小。,1.,,静态负载平衡,在任何进程执行之前进行的负载平衡称为静态负载平衡。,,静态负载平衡的优点：,,一般情况下比动态负载平衡省时；,,一般情况下，静态负载平衡在每个处理机上仅生成一个进程，从而减少了进程建立、同步和终止的开销；,,可用来评估并行算法的加速比和性能,。,有向无回路图,(,directed acyclic graph,),利用静态调

4、度的并行程序可由一个有向无回路图,G=(V,E),来表示，其中：,,V—,节点的有限集合，一个节点表示一个子任务,,E—,有向边的有限集合，一个边表示相连的节点的前驱限制,,节点的权值,—,计算开销,,有向边的权值,—,该边相连的节点间的通信开销,T1,,2,,T2,,3,,T3,,1,,T4,,2,,T5,,3,,T6,,3,,T7,,1,,10,5,10,15,4,6,7,8,2,静态负载平衡,,确定模式：在此模式下，每个子任务所需的执行时间和它们之间执行的先后次序在任务运行前就已确定。,,非确定模式：在此模式下，每个子任务所需的执行时间可表示为一个随机变量。,任务图,T1,,2,,T2,

5、,3,,T3,,1,,T4,,2,,T5,,3,,T6,,3,,T7,,1,,10,5,10,15,4,6,7,8,2,静态负载平衡,—,确定模式,一种简化的情况：任务间没有通信开销，其调度可利用甘特图,(Gantt chart),来表示，它表示每个子任务的执行时间和其执行所在的处理机。,,该方法也称为,表调度,，它生成一个调度列表。,T1,,2,,T2,,3,,T3,,1,,T4,,2,,T5,,3,,T6,,3,,T7,,1,,T7,T5,T2,T1,,T6,,T3,,,T4,,,,,,,,,,,8,7,5,4,2,9,6,3,1,time,处 理 机,静态负载平衡,—,确定模式,最优

6、调度,—,对给定一个任务图和处理机数，使任务总的执行时间最小化的调度。,,与最优调度有关的一些结论：,,如果所有的子任务都需要一个单位时间，且任务图是一个森林，则算法可在多项式时间内找到最优调度。,,如果子任务的执行时间是不同的，或有两个以上的处理机，则找最优调度的问题是,NP,难的。这就意味着在最坏情况下，寻找最优调度的已知的最好的算法需要指数时间。,确定模式中要求被调度的任务中任何特点都不允许再改变，但在实际的任务调度过程中，某些任务的,调度,往往会影响到后继任务的执行时间的变化，使后继任务的执行和通信等产生一些变化。,,目前有很多,基于动态列表调度方法,的调度算法。与传统方法相比，它们在

7、每次分配任务之后都要重新计算所有未被调度节点的属性，并利用这些新信息重新安排列表中节点的顺序。,静态负载平衡,—,确定模式,静态负载平衡,—,确定模式,基于动态列表调度方法的调度算法采用以下三个步骤：,,确定所有未被调度节点的新属性；,,选择具有最高优先级的节点进行调度；,,将节点分配到使它的通信启动时间,最早的,处理机上。,在动态列表调度算法中“确定未被调度节点的新属性”是计算这些节点的,t-level,和,b-level,值：,,节点,Ti,的,t-level,：从入口节点到,Ti,的一条最长的路径；,,节点,Ti,的,b-level,：从,Ti,到出口节点的一条最长的路径。,,T1,,2

8、,,T5,,4,,T4,,3,,T3,,4,,T2,,3,,T6,,4,,T7,,3,,T8,,1,4,1,10,1,1,1,1,1,6,5,5,,T1,,2,,T5,,4,,T4,,3,,T3,,4,,T2,,3,,T6,,4,,T7,,3,,T8,,1,4,1,10,1,1,1,1,1,6,5,5,节点,t-level,b-level,T1,0,23,T2,6,15,T3,12,11,T4,3,13,T5,3,14,T6,10,10,T7,8,9,T8,22,1,动态列表调度算法实现思想,只用,t-level,的值的意义解释算法,,在调度过程中，节点被调度之前，它的,t-level,是不断

9、变化的。,,t-level,值之所以会发生变化是因为当一条边所连接的两个节点恰被分配到同一个处理机上时，这条边的权值就会变为,0,。从而使这条路径可能不是最长的结果。,静态负载平衡,—,非确定模式,常用的静态负载平衡技术还有：,,循环算法,,—,按进程顺序分配任务，当所有的进程都得到了一个任务后，再从头开始分配。,,随机算法,,—,随机地选择进程并分配任务。,,递归二分法,,—,递归地将问题分为相等计算量的两个子问题，并使其通信量最少。,,模拟退火,(,Simulated annealing),—,一种优化技术,,遗传算法,(,Genetic algorithm),—,一种优化技术,2.,,动

10、态负载平衡,在进程的执行过程中完成的负载平衡。,,它是在应用程序运行期间对各节点间负载进行平衡的调度算法，它通过分析并行系统的实时负载信息，动态地将任务在各处理机之间进行分配和调整，以消除系统中负载分布的不均匀性。如：前面讲的,Mandelbrot,集、热分布问题等。,,虽然动态负载平衡会产生在执行期间的额外开销，但在负载不易均衡的情况下它比静态负载平衡往往更有效。,动态负载平衡,,集中式,—,任务是从一个中心位置分发的，通常是主从结构。,,分散式,—,任务通常在任意进程间进行传递。,,一组“工作者”进程根据问题进行操作，并彼此间进行交互，最后报告给一个单独的进程。,,一个“工作者”进程可以从

11、其它“工作者”进程接收任务，也可以将任务发给其它“工作者”进程，这些工作都由他们自己来决定。,集中式动态负载平衡,主进程拥有要被执行的任务集。,,当从进程完成一个任务，向主进程请求另一个任务时，任务就由主进程发给从进程。如：工作池、处理机农庄等。,,工作池,主进程,,任务队列,,,,从进程,请求任务,(,可能提交一些新任务,),发送任务,当下列条件满足时计算终止：,,任务队列为空，且每个从进程都请求得到新的任务，但没有被产生的新任务。,,当任务队列为空时，且如果仍有进程运行，则此时终止条件不充分，这是因为运行的进程还可能产生新任务并放到任务队列中。,集中式动态负载平衡的计算终止,分散式动态负载

12、平衡,分布式工作池,进程,M,0,主进程,,,初始任务队列,,,,,,任务子队列,,,,,,任务子队列,进程,M,n-1,进程,M,0,主进程,,,初始任务队列,,,,,,任务子队列,,,,,,任务子队列,进程,M,n-1,分散式动态负载平衡,全分布式工作池,,由接收者启动方式,—,适合于高系统负载时,,由发送者启动方式,—,适合于低系统负载时,,进程,,进程,,进程,,进程,请求,/,任务,使用线性结构实现动态负载平衡,每个处理机上运行两个进程,,用于左右两边的通信进程,,用于执行当前任务的进程,,主进程,P,0,,,,P,1,,,,P,2,,,,P,3,,,,P,n,任务,,,P,comm

13、,,P,task,若缓冲区为空，则产生请求信号,接收请求的任务,如果,P,task,空闲，则请求任务,接收请求的任务,,请求任务,若缓冲区满，则发送任务,实现通信和计算间的时间共享的代码,主进程,P,0,：,,,for (i = 0; i < no_tasks; i++) {,,recv(P,1,, request_tag);,/* request for task */,,,/* send tasks into queue */,,send(&task, P,1,, task_tag);,,},,recv(P,1,, request_tag);,/* request for task */,

14、,send(&empty, P,1,, task_tag);,/* end of tasks */,从进程,P,i,(1,,,i,<,n,),：,,if (buffer == empty) {,,send(P,i-1,, request_tag);,/* request new task */,,recv(&buffer, P,i-1,, task_tag);,/* task from left proc */,,},,if ((buffer == full) && (!busy)) {,/* get next task */,,task = buffer;,/* get task*/,,b

15、uffer = empty;,/* set buffer empty */,,busy = TRUE;,/* set process busy */,,},,nrecv,(P,i+1,, request_tag, request);,/* check msg from right */,,if (request && (buffer == full)) {,,send(&buffer, P,i+1,);,/* shift task forward */,,buffer = empty;,,},,if (busy) {,/* continue on current task */,,Do som

16、e work on task.,,If task finished, set busy to false.,,},必须对右边接收的请求使用非阻塞,recv — nrecv,，当,nrecv,收到了请求消息后，会将参数,request,置为,TRUE,。,,MPI,中非阻塞接收例程,MPI_Irecv( ),，,这个函数比阻塞操作只多一个参数：,,,MPI_Request *request,,这个函数的调用将分配一个通信请求对象，把它和参数,request,连接。之后，,request,能被用于查寻这个通信的状态或等待它的完成。,,函数,MPI_WAIT,和,MPI_TEST,用于完成和查询一

17、个非阻塞通信。,二、 分布式终止检测算法,终止条件,,使用消息应答实现终止检测,,环形终止算法,,固定能量分布式终止算法,终止条件,,在时间,t,时需要满足下列条件：,,在时间,t,时，对所有的进程满足局部应用终止的条件；,,在时间,t,时，没有消息在进程间传递。,,分布式终止条件,与,集中式终止条件,之间存在着一些差别：需要考虑被传递的消息。,,考察是否还有被传递的消息不是一件容易的事情，因为消息在进程间传送的时间预先是不知道的。,一个常见的分布式终止算法,—,,使用消息应答实现终止检测,每个进程处于下面两种状态之一：,,非活动的,(inactive) –,没有任何任务要执行,,活动的,(a

18、ctive),,发送一个任务使某个进程处于活动状态的进程称为被激活进程的“父亲”进程。,,当进程收到一个任务（未必是其父亲发来的任务）时，除了进程接收的任务来自其父亲进程外，它必须马上发送一个确认消息。,,每个进程有唯一的父亲进程。,当进程即将成为非活动状态时，则发送一个确认消息给其父亲进程。即当：,,其局部终止条件满足（即所有的任务被完成）,,它对已收到的任务都发送了确认消息,,对发出的任务都收到了确认消息,,一个进程必须在其父亲进程之前成为非活动状态；当第一个进程成为空闲时，计算就终止了。,,进程,,非活动的,,活动的,,父亲进程,第一个任务,最后的确认,发送任务,接收确认,用消息应答实现

19、终止检测,单环终止算法,,当,P0,已经终止，它就发送一个标记,(,令牌,token),给,P1,。,,当,Pi (1 .. i < n),收到发来的标记，并且自己也已终止，则向,Pi+1,传送一个标记；否则，就等待局部终止条件满足再向,Pi+1,传送标记。直到,Pn-1,将标记发给,P0.,,当,P0,收到一个标记时，它确信环上的所有进程已经终止。如果必要的话，它向所有的进程发送一个消息通知他们全局终止。,,该算法假设进程满足局部终止条件后不会在被激活。它,不适合于,工作池的情况,—,即：一个进程可以将一个新任务传送给一个处于空闲的进程。,环形终止算法,,P,0,,P,1,,P,2,,P,n

20、,,当满足本地终止条件时，将标记传给下一个进程,,,局部终止,,,AND,P,j,环形终止算法,双环终止算法,----,可以处理进程再次被激活的情况，但需要对环进行两次扫描。,,当进程,Pi,要将任务传给,Pj,，其中,j < i,，且,Pj,的结束标记已传出时，在这种情况下结束标记就必须在整个环上再循环传送一次。,,为了区分在不同的情况下传送的结束标记，我们将标记着为白色和黑色。,,进程收到黑色标记时意味着全局终止可能还没有出现，标记必须沿环重新传送。,双环终止算法,,当,P0,已经满足局部终止时，它变为白色，并向,P1,发送一个白色标记。,,当环上的某个进程已终止时，标记就在环上从一个进程

21、传向下一个进程，但标记的颜色可能会发生改变。,,如果,Pi,向,Pj,传送一个任务,( j < i) (,即： 在环上,Pj,在,Pi,的前面,),，,Pi,就变为黑色进程；否则，它为白色进程。,,黑色进程将会把要传送的标记变为黑色，并将其传给下一个进程。白色进程将接收到的标记（白色或黑色）往下传递。在,Pi,传出标记后，进程的颜色将变为白色。,Pn-1,传递标记给,P0.,双环终止算法,(,续,),,当,P0,收到一个黑色标记时，它将一个白色标记再次传递下去；如果它收到一个白色标记，则所有的进程已终止，即全局终止。,,在上述两种终止算法中，,P0,为全局终止条件的中心点。且假设每个请求将产生

22、一个应答。,,P,0,,P,j,,P,i,,P,n,,任务,,,,,,双环终止算法的执行,,P,i,,P,i,固定能量分布式终止算法,计算开始时，所有的能量仅由一个进程（根进程）拥有；,,随后，根进程在下发任务的同时将部分能量也分给相应的进程。,,如果进程收到了请求的任务和能量，它可以继续将任务和它拥有的能量继续下发给其它进程。,,如果进程处于空闲，则在请求新任务之前将自己的能量返回。,,一个进程只有收回它分发出去的全部能量时才将自己的能量归还给其能量的进程。,,当所有的能量返回到根进程且该进程处于空闲时，所有的进程必定也处于空闲，且全局计算可以终止。,三、负载平衡和终止检测实例,--,最短路

23、径问题,问题的描述：,,在给定的一个连通加权图中，找出任意给定两点,a,，,b,之间的最短路径。即，,a,到,b,的路径经过的各边权值之和最小。,B,E,D,C,A,F,,,,,,,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,用图表示如下：,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,图的表示：常用的方法有邻接矩阵和邻接列表,,邻接矩阵：一个,2,维数组,a,，,a

24、[i, j],表示为图中顶点,i,和顶点,j,之间的边的有关数值。,10,8,14,9,17,13,24,51,A,,B,,C,,D,,E,,F,源,A B C D E F,目标,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,∞,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,邻接列表：图中每个顶点拥有一个链表，链表中各项保存着该顶点与其它顶点之间的边的有关数值。,A,,B,,C,,D,,E,,F,源,,B 10,╳,,C 8,,D 14,╳,,E

25、 9,╳,,F 17,╳,,,╳,,D 13,,E 24,,F 51,╳,图的搜索,常用的最短路径算法有：,,Moore,的单源最短路径算法,,Dijkstra,的单源最短路径算法,,,Moore,算法更易于并行化,,要求权值为正数,Moore,最短路径算法,由源顶点开始，在考察顶点,i,时，方法如下：,,找出从源点经过顶点,i,的顶点,j,的距离，并与当前到顶点,j,的距离比较，求其最小值作为到顶点,j,的距离。即：,,假设,d,i,为由源点到顶点,i,的当前最小距离，,w,ij,为顶点,i,到顶点,j,的边的权值。那么为由源点到顶点,j,的当前最小距离为：,

26、,d,j,= min(,d,j,,,d,i,,+,w,ij,),Moore,最短路径算法,,顶点,i,,顶点,j,d,i,w,ij,d,j,数据结构,建立一个先进先出的顶点队列，用来存放将要被考察的顶点链表。最初，只有源顶点存放在该队列中；,,从源顶点到顶点,i,的当前最短路径存放在数组,dist[i],中。最初，,dist,数组中各元素的值被赋值为,∞,。,,假设,w,ij,为顶点,i,到顶点,j,的边的权值，若两顶点无边，则权值为 ∞。,求当前最短路径的代码：,Newdist_ j = dist[i] + w[i][j];,,if (newdist_ j < dist[j]) di

27、st[j] = newdist_ j;,,,当顶点,j,发现了更短的路径后，且顶点,j,不在顶点队列中，就将顶点,j,加入到顶点队列中。这将使顶点,j,重新被考察。,图搜索的过程,两个关键数据结构的初始状态：,,,顶点队列表,dist[ ],A,,,,,,0,∞,∞,∞,∞,∞,A B C D E F,,各顶点当前最小距离,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,图搜索的过程,在测试顶点,A,后：,,,顶点队列表,dist[ ],B,,,,,,0,10,∞,∞,∞,∞,A B C D

28、 E F,Moore,算法对测试顶点的顺序没有要求。,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,图搜索的过程,在测试顶点,B,后：,,,顶点队列表,dist[ ],D,E,C,,,,0,10,18,23,34,61,A B C D E F,因,F,为终点，故不需要加,F,到顶点队列中。,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,测试顶点,D,后：,,顶点队列表,dist[ ],,,,,C,E,61,32,23,18,10,0,A B C

29、 D E F,测试顶点,E,后：,,顶点队列表,dist[ ],,,,,,C,49,32,23,18,10,0,A B C D E F,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,测试顶点,C,后：,,顶点队列表,dist[ ],,,,,,,49,32,23,18,10,0,A B C D E F,,A,,B,,C,,D,,E,,F,10,17,9,14,8,51,24,13,顶点可能重复进入顶点队列的情

30、况：,顶点队列表,dist[ ],,,,,,B,∞,∞,∞,∞,10,0,A B C D E F,顶点队列表,dist[ ],,,,C,D,E,61,34,23,18,10,0,A B C D E F,顶点队列表,dist[ ],,,,,C,D,51,34,23,18,10,0,A B C D E F,,,,,,A,∞,∞,∞,∞,∞,0,A B C D E F,顶点队列表,dist[ ],顶点可能重复进

31、入顶点队列的情况：,顶点队列表,dist[ ],,,,,,E,51,32,23,18,10,0,A B C D E F,顶点队列表,dist[ ],,,,,,,49,32,23,18,10,0,A B C D E F,,,,,E,C,51,32,23,18,10,0,A B C D E F,顶点队列表,dist[ ],在,dist[ ],数组中存放着从源点到各个顶点的最小距离。,顺序代码：,设,next_vertex( ),,返回顶点队列中的下一个顶点或,no_vertex,

32、,假设利用名为,w[ ][ ],的相邻矩阵,.,,while ((i = next_vertex()) != no_vertex) {,/*while a vertex*/,,for (j = 1; j < n; j++),/* get next edge */,,if (w[i][j] != infinity) {,/* if an edge */,,newdist_j = dist[i] + w[i][j];,,if (newdist_j < dist[j]) {,,dist[j] = newdist_j;,,append_queue(j);,/* add to queue if not

33、there */,,},,},,},/*no more to consider*/,集中式工作池,集中式工作池拥有顶点队列,vertex_queue[ ],，其每个元素为一个任务,,每个从进程从顶点队列每次取一个顶点，并返回可能的新顶点,,由于相邻矩阵的值始终不会改变，所以将相邻矩阵拷贝给每一个从进程,,Dist[ ],存放在主进程的局部存储器中,主进程代码：,while (vertex_queue() != empty) {,,recv(P,ANY,, source = Pi);,/* request task from slave */,,v = get_vertex_queue();,,

34、send(,/* send next vertex and */,,send(,/* current dist array */,,recv(&j, &dist[j], P,ANY,, source = Pi);,/* new distance */,,append_queue(j, dist[j]);,/* append vertex to queue */,,},/* and update distance array */,,for (i=0; i

35、e */,,send(Pi, termination_tag);,/* termination message*/,,},从进程代码：,send(P,master,);,/* send request for task */,recv(&v, P,master,, tag);,/* get vertex number */,if (tag != termination_tag) {,recv(&dist, &n, P,master,);,/* and dist array */,for (j = 1; j < n; j++),/* get next edge */,if (w[v][j] !=

36、 infinity) {,/* if an edge */,newdist_j = dist[v] + w[v][j];,if (newdist_j < dist[j]) {,dist[j] = newdist_j;,send(&j, &dist[j], P,master,);,/* add vertex to queue */,},/* send updated distance */,},},分散式工作池,从进程,P,i,仅围绕顶点,v,i,搜索,,数组,dist[ ],将分散在各个从进程的局部存储器中，它表示当前从源点到顶点,v,i,的最小距离,,进程,P,i,也存放对顶点,v,i,的相

37、邻矩阵（一行）,,搜索算法,顶点,A,是第一个被搜索的顶点，拥有顶点,A,的进程被激活；,,这个进程将搜索与其相连的顶点，寻找其距离；,,从顶点,A,到顶点,j,的距离将发给进程,j,，用来与进程,j,目前拥有的值进行比较和替换（如果当前值较大）；,,以相同的方法，每个进程在搜索过程中最小距离在不断被修改；,,如果,dist[i],的值被改变，进程,i,将再次被激活来重新搜索。,,主进程,,dist,,,w [ ],,,顶点,,进程,A,,dist,,,w [ ],,,顶点,,进程,B,源到,B,的新距离,,dist,,,w [ ],,,顶点,,进程,F,,dist,,,w [ ],,,顶点,

38、,进程,C,源到,C,的新距离,源到,F,的新距离,从源点开始,从进程,Pi,的代码：,recv(newdist, P,ANY,);,if (newdist < dist) {,dist = newdist;,vertex_queue = TRUE;,/* add to queue */,} else vertex_queue == FALSE;,if (vertex_queue == TRUE),/*start searching around vertex*/,for (j = 1; j < n; j++),/* get next edge */,if (w[j] != infinity) {,d = dist + w[j];,send(,/* send distance to proc j */,},需考虑的具体问题：,进程收到消息后才有必要工作,----,使用同步消息传递；,,相应的顶点被放到顶点队列中后，进程才应被激活，可能有许多进程处于未激活状态，将导致算法低效的执行；,,每个顶点对应一个处理机不适应顶点数目较大的情况,----,每个处理机分配一组顶点。,