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

并行计算负载平衡和终止检测第一页，共六十四页，2022年，8月28日主要内容负载平衡静态负载平衡确定模式与非确定模式动态负载平衡集中式与分散式分布式终止检测方法终止条件几个终止检测算法负载平衡和终止检测实例第二页，共六十四页，2022年，8月28日主要内容负载平衡静态负载平衡确定模式与非确定模式动态负载平衡集中式与分散式分布式终止检测方法终止条件几个终止检测算法负载平衡和终止检测实例第三页，共六十四页，2022年，8月28日P1P0P2P3P4P5处理机time一、负载平衡静态负载平衡动态负载平衡负载平衡time处理机P1P0P2P3P4P5第四页，共六十四页，2022年，8月28日负载平衡是利用调度程序实现的。调度的目的是通过将任务正确分配给各处理机，并使得任务按照一定的顺序执行，以尽可能少的时间完成并行应用任务。在静态调度中，调度通常是在编译时进行的。并行程序的特点（如：任务的执行时间、通信、数据的相互关联和同步等）在程序执行之前都是已知的。在动态调度中，并行程序的特点在执行之前往往知道得很少，因此，调度是在程序执行时进行的。它使程序的执行时间和调度时间尽可能最小。第五页，共六十四页，2022年，8月28日1.静态负载平衡在任何进程执行之前进行的负载平衡称为静态负载平衡。静态负载平衡的优点：一般情况下比动态负载平衡省时；一般情况下，静态负载平衡在每个处理机上仅生成一个进程，从而减少了进程建立、同步和终止的开销；可用来评估并行算法的加速比和性能。第六页，共六十四页，2022年，8月28日有向无回路图(directedacyclicgraph)利用静态调度的并行程序可由一个有向无回路图G=(V,E)来表示，其中：V—节点的有限集合，一个节点表示一个子任务E—有向边的有限集合，一个边表示相连的节点的前驱限制节点的权值—计算开销有向边的权值—该边相连的节点间的通信开销T12T23T31T42T53T63T71105101546782第七页，共六十四页，2022年，8月28日静态负载平衡确定模式：在此模式下，每个子任务所需的执行时间和它们之间执行的先后次序在任务运行前就已确定。非确定模式：在此模式下，每个子任务所需的执行时间可表示为一个随机变量。任务图T12T23T31T42T53T63T71105101546782第八页，共六十四页，2022年，8月28日静态负载平衡—确定模式一种简化的情况：任务间没有通信开销，其调度可利用甘特图(Ganttchart)来表示，它表示每个子任务的执行时间和其执行所在的处理机。该方法也称为表调度，它生成一个调度列表。T12T23T31T42T53T63T71T7T5T2T1T6T3T4875429631time处理机第九页，共六十四页，2022年，8月28日静态负载平衡—确定模式最优调度—对给定一个任务图和处理机数，使任务总的执行时间最小化的调度。与最优调度有关的一些结论：如果所有的子任务都需要一个单位时间，且任务图是一个森林，则算法可在多项式时间内找到最优调度。如果子任务的执行时间是不同的，或有两个以上的处理机，则找最优调度的问题是NP难的。这就意味着在最坏情况下，寻找最优调度的已知的最好的算法需要指数时间。第十页，共六十四页，2022年，8月28日确定模式中要求被调度的任务中任何特点都不允许再改变，但在实际的任务调度过程中，某些任务的调度往往会影响到后继任务的执行时间的变化，使后继任务的执行和通信等产生一些变化。目前有很多基于动态列表调度方法的调度算法。与传统方法相比，它们在每次分配任务之后都要重新计算所有未被调度节点的属性，并利用这些新信息重新安排列表中节点的顺序。静态负载平衡—确定模式第十一页，共六十四页，2022年，8月28日静态负载平衡—确定模式基于动态列表调度方法的调度算法采用以下三个步骤：确定所有未被调度节点的新属性；选择具有最高优先级的节点进行调度；将节点分配到使它的通信启动时间最早的处理机上。第十二页，共六十四页，2022年，8月28日在动态列表调度算法中“确定未被调度节点的新属性”是计算这些节点的t-level和b-level值：节点Ti的t-level：从入口节点到Ti的一条最长的路径；节点Ti的b-level：从Ti到出口节点的一条最长的路径。T12T54T43T34T23T64T73T81411011111655第十三页，共六十四页，2022年，8月28日T12T54T43T34T23T64T73T81411011111655节点t-levelb-levelT1023T2615T31211T4313T5314T61010T789T8221第十四页，共六十四页，2022年，8月28日动态列表调度算法实现思想只用t-level的值的意义解释算法在调度过程中，节点被调度之前，它的t-level是不断变化的。t-level值之所以会发生变化是因为当一条边所连接的两个节点恰被分配到同一个处理机上时，这条边的权值就会变为0。从而使这条路径可能不是最长的结果。第十五页，共六十四页，2022年，8月28日静态负载平衡—非确定模式常用的静态负载平衡技术还有：循环算法

—按进程顺序分配任务，当所有的进程都得到了一个任务后，再从头开始分配。随机算法

—随机地选择进程并分配任务。递归二分法

—递归地将问题分为相等计算量的两个子问题，并使其通信量最少。模拟退火(Simulatedannealing)—一种优化技术遗传算法(Geneticalgorithm)—一种优化技术第十六页，共六十四页，2022年，8月28日2.动态负载平衡在进程的执行过程中完成的负载平衡。它是在应用程序运行期间对各节点间负载进行平衡的调度算法，它通过分析并行系统的实时负载信息，动态地将任务在各处理机之间进行分配和调整，以消除系统中负载分布的不均匀性。如：前面讲的Mandelbrot集、热分布问题等。虽然动态负载平衡会产生在执行期间的额外开销，但在负载不易均衡的情况下它比静态负载平衡往往更有效。第十七页，共六十四页，2022年，8月28日动态负载平衡集中式—任务是从一个中心位置分发的，通常是主从结构。分散式—任务通常在任意进程间进行传递。一组“工作者”进程根据问题进行操作，并彼此间进行交互，最后报告给一个单独的进程。一个“工作者”进程可以从其它“工作者”进程接收任务，也可以将任务发给其它“工作者”进程，这些工作都由他们自己来决定。第十八页，共六十四页，2022年，8月28日集中式动态负载平衡主进程拥有要被执行的任务集。当从进程完成一个任务，向主进程请求另一个任务时，任务就由主进程发给从进程。如：工作池、处理机农庄等。工作池主进程任务队列从进程请求任务(可能提交一些新任务)发送任务第十九页，共六十四页，2022年，8月28日当下列条件满足时计算终止：任务队列为空，且每个从进程都请求得到新的任务，但没有被产生的新任务。当任务队列为空时，且如果仍有进程运行，则此时终止条件不充分，这是因为运行的进程还可能产生新任务并放到任务队列中。集中式动态负载平衡的计算终止第二十页，共六十四页，2022年，8月28日分散式动态负载平衡分布式工作池进程M0主进程初始任务队列任务子队列任务子队列进程Mn-1进程M0主进程初始任务队列任务子队列任务子队列进程Mn-1第二十一页，共六十四页，2022年，8月28日分散式动态负载平衡全分布式工作池由接收者启动方式—适合于高系统负载时由发送者启动方式—适合于低系统负载时进程进程进程进程请求/任务第二十二页，共六十四页，2022年，8月28日使用线性结构实现动态负载平衡每个处理机上运行两个进程用于左右两边的通信进程用于执行当前任务的进程主进程P0P1P2P3Pn任务第二十三页，共六十四页，2022年，8月28日PcommPtask若缓冲区为空，则产生请求信号接收请求的任务如果Ptask空闲，则请求任务接收请求的任务请求任务若缓冲区满，则发送任务第二十四页，共六十四页，2022年，8月28日实现通信和计算间的时间共享的代码主进程P0：for(i=0;i<no_tasks;i++){recv(P1,request_tag);/*requestfortask*/

/*sendtasksintoqueue*/send(&task,P1,task_tag);}recv(P1,request_tag);/*requestfortask*/send(&empty,P1,task_tag);/*endoftasks*/第二十五页，共六十四页，2022年，8月28日从进程Pi(1

i<n)：if(buffer==empty){send(Pi-1,request_tag);/*requestnewtask*/recv(&buffer,Pi-1,task_tag);/*taskfromleftproc*/}if((buffer==full)&&(!busy)){/*getnexttask*/task=buffer;/*gettask*/buffer=empty;/*setbufferempty*/busy=TRUE;/*setprocessbusy*/}nrecv(Pi+1,request_tag,request);/*checkmsgfromright*/if(request&&(buffer==full)){send(&buffer,Pi+1);/*shifttaskforward*/buffer=empty;}if(busy){/*continueoncurrenttask*/Dosomeworkontask.Iftaskfinished,setbusytofalse.}第二十六页，共六十四页，2022年，8月28日必须对右边接收的请求使用非阻塞recv—nrecv，当nrecv收到了请求消息后，会将参数request置为TRUE。MPI中非阻塞接收例程MPI_Irecv()，这个函数比阻塞操作只多一个参数：

MPI_Request*request这个函数的调用将分配一个通信请求对象，把它和参数request连接。之后，request能被用于查寻这个通信的状态或等待它的完成。函数MPI_WAIT和MPI_TEST用于完成和查询一个非阻塞通信。第二十七页，共六十四页，2022年，8月28日二、分布式终止检测算法终止条件使用消息应答实现终止检测环形终止算法固定能量分布式终止算法第二十八页，共六十四页，2022年，8月28日终止条件在时间t时需要满足下列条件：在时间t时，对所有的进程满足局部应用终止的条件；在时间t时，没有消息在进程间传递。分布式终止条件与集中式终止条件之间存在着一些差别：需要考虑被传递的消息。考察是否还有被传递的消息不是一件容易的事情，因为消息在进程间传送的时间预先是不知道的。第二十九页，共六十四页，2022年，8月28日一个常见的分布式终止算法—

使用消息应答实现终止检测每个进程处于下面两种状态之一：非活动的(inactive)–没有任何任务要执行活动的(active)发送一个任务使某个进程处于活动状态的进程称为被激活进程的“父亲”进程。当进程收到一个任务（未必是其父亲发来的任务）时，除了进程接收的任务来自其父亲进程外，它必须马上发送一个确认消息。每个进程有唯一的父亲进程。第三十页，共六十四页，2022年，8月28日当进程即将成为非活动状态时，则发送一个确认消息给其父亲进程。即当：其局部终止条件满足（即所有的任务被完成）它对已收到的任务都发送了确认消息对发出的任务都收到了确认消息一个进程必须在其父亲进程之前成为非活动状态；当第一个进程成为空闲时，计算就终止了。第三十一页，共六十四页，2022年，8月28日进程非活动的活动的父亲进程第一个任务最后的确认发送任务接收确认用消息应答实现终止检测第三十二页，共六十四页，2022年，8月28日单环终止算法当P0已经终止，它就发送一个标记(令牌token)给P1。当Pi(1..i<n)收到发来的标记，并且自己也已终止，则向Pi+1传送一个标记；否则，就等待局部终止条件满足再向Pi+1传送标记。直到Pn-1将标记发给P0.当P0收到一个标记时，它确信环上的所有进程已经终止。如果必要的话，它向所有的进程发送一个消息通知他们全局终止。该算法假设进程满足局部终止条件后不会在被激活。它不适合于工作池的情况—即：一个进程可以将一个新任务传送给一个处于空闲的进程。环形终止算法第三十三页，共六十四页，2022年，8月28日P0P1P2Pn当满足本地终止条件时，将标记传给下一个进程局部终止ANDPj第三十四页，共六十四页，2022年，8月28日环形终止算法双环终止算法----可以处理进程再次被激活的情况，但需要对环进行两次扫描。当进程Pi要将任务传给Pj，其中j<i，且Pj的结束标记已传出时，在这种情况下结束标记就必须在整个环上再循环传送一次。为了区分在不同的情况下传送的结束标记，我们将标记着为白色和黑色。进程收到黑色标记时意味着全局终止可能还没有出现，标记必须沿环重新传送。第三十五页，共六十四页，2022年，8月28日双环终止算法当P0已经满足局部终止时，它变为白色，并向P1发送一个白色标记。当环上的某个进程已终止时，标记就在环上从一个进程传向下一个进程，但标记的颜色可能会发生改变。如果Pi向Pj传送一个任务(j<i)(即：在环上Pj在Pi的前面)，Pi就变为黑色进程；否则，它为白色进程。黑色进程将会把要传送的标记变为黑色，并将其传给下一个进程。白色进程将接收到的标记（白色或黑色）往下传递。在Pi传出标记后，进程的颜色将变为白色。Pn-1传递标记给P0.第三十六页，共六十四页，2022年，8月28日双环终止算法(续)当P0收到一个黑色标记时，它将一个白色标记再次传递下去；如果它收到一个白色标记，则所有的进程已终止，即全局终止。在上述两种终止算法中，P0为全局终止条件的中心点。且假设每个请求将产生一个应答。第三十七页，共六十四页，2022年，8月28日P0PjPiPn任务双环终止算法的执行PiPi第三十八页，共六十四页，2022年，8月28日固定能量分布式终止算法计算开始时，所有的能量仅由一个进程（根进程）拥有；随后，根进程在下发任务的同时将部分能量也分给相应的进程。如果进程收到了请求的任务和能量，它可以继续将任务和它拥有的能量继续下发给其它进程。如果进程处于空闲，则在请求新任务之前将自己的能量返回。一个进程只有收回它分发出去的全部能量时才将自己的能量归还给其能量的进程。当所有的能量返回到根进程且该进程处于空闲时，所有的进程必定也处于空闲，且全局计算可以终止。第三十九页，共六十四页，2022年，8月28日三、负载平衡和终止检测实例--

最短路径问题问题的描述：在给定的一个连通加权图中，找出任意给定两点a，b之间的最短路径。即，a到b的路径经过的各边权值之和最小。BEDCAF第四十页，共六十四页，2022年，8月28日ABCDEF10179148512413ABCDEF10179148512413ABCDEF10179148512413用图表示如下：ABCDEF10179148512413第四十一页，共六十四页，2022年，8月28日图的表示：常用的方法有邻接矩阵和邻接列表邻接矩阵：一个2维数组a，a[i,j]表示为图中顶点i和顶点j之间的边的有关数值。10814917132451ABCDEF源ABCDEF目标∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞ABCDEF10179148512413第四十二页，共六十四页，2022年，8月28日邻接列表：图中每个顶点拥有一个链表，链表中各项保存着该顶点与其它顶点之间的边的有关数值。ABCDEF源B10╳C8D14╳E9╳F17╳╳D13E24F51╳第四十三页，共六十四页，2022年，8月28日图的搜索常用的最短路径算法有：Moore的单源最短路径算法Dijkstra的单源最短路径算法Moore算法更易于并行化要求权值为正数第四十四页，共六十四页，2022年，8月28日Moore最短路径算法由源顶点开始，在考察顶点i时，方法如下：找出从源点经过顶点i的顶点j的距离，并与当前到顶点j的距离比较，求其最小值作为到顶点j的距离。即：假设di为由源点到顶点i的当前最小距离，wij为顶点i到顶点j的边的权值。那么为由源点到顶点j的当前最小距离为：dj=min(dj,di

+wij)第四十五页，共六十四页，2022年，8月28日Moore最短路径算法顶点i顶点jdiwijdj第四十六页，共六十四页，2022年，8月28日数据结构建立一个先进先出的顶点队列，用来存放将要被考察的顶点链表。最初，只有源顶点存放在该队列中；从源顶点到顶点i的当前最短路径存放在数组dist[i]中。最初，dist数组中各元素的值被赋值为∞。假设wij为顶点i到顶点j的边的权值，若两顶点无边，则权值为∞。第四十七页，共六十四页，2022年，8月28日求当前最短路径的代码：Newdist_j=dist[i]+w[i][j];if(newdist_j<dist[j])dist[j]=newdist_j;当顶点j发现了更短的路径后，且顶点j不在顶点队列中，就将顶点j加入到顶点队列中。这将使顶点j重新被考察。第四十八页，共六十四页，2022年，8月28日图搜索的过程两个关键数据结构的初始状态：顶点队列表dist[]A0∞∞∞∞∞ABCDEF各顶点当前最小距离ABCDEF10179148512413第四十九页，共六十四页，2022年，8月28日图搜索的过程在测试顶点A后：顶点队列表dist[]B010∞∞∞∞ABCDEFMoore算法对测试顶点的顺序没有要求。ABCDEF10179148512413第五十页，共六十四页，2022年，8月28日图搜索的过程在测试顶点B后：顶点队列表dist[]DEC01018233461ABCDEF因F为终点，故不需要加F到顶点队列中。ABCDEF10179148512413第五十一页，共六十四页，2022年，8月28日测试顶点D后：顶点队列表dist[]CE61322318100ABCDEF测试顶点E后：顶点队列表dist[]C49322318100ABCDEFABCDEF10179148512413第五十二页，共六十四页，2022年，8月28日测试顶点C后：顶点队列表dist[]49322318100ABCDEFABCDEF10179148512413第五十三页，共六十四页，2022年，8月28日顶点可能重复进入顶点队列的情况：顶点队列表dist[]B∞∞∞∞100ABCDEF顶点队列表dist[]CDE61342318100ABCDEF顶点队列表dist[]CD51342318100ABCDEFA∞∞∞∞∞0ABCDEF顶点队列表dist[]第五十四页，共六十四页，2022年，8月28日顶点可能重复进入顶点队列的情况：顶点队列表dist[]E51322318100ABCDEF顶点队列表dist[]49322318100ABCDEFEC51322318100ABCDEF顶点队列表dist[]在dist[]数组中存放着从源点到各个顶点的最小距离。第五十五页，共六十四页，2022年，8月28日顺序代码：设next_vertex()返回顶点队列中的下一个顶点或no_vertex假设利用名为w[][]的相邻矩阵.while((i=next_vertex())!=no_vertex){/*whileavertex*/for(j=1;j<n;j++)/*getnextedge*/if(w[i][j]!=infinity){/*ifanedge*/newdist_j=dist[i]+w[i][j];if(newdist_j<dist[j]){dist[j]=newdist_j;append_queue(j);/*addtoqueueifnotthere*/}}}/*nomoretoconsider*/第五十六页，共六十四页，2022年，8月28日集中式工作池集中式工作池拥有顶点队列vertex_queue[]，其每个元素为一个任务每个从进程从顶点队列每次取一个顶点，并返回可能的新顶点由于相邻矩阵的值始终不会改变，所以将相邻矩阵拷贝给每一个从进程Dist[]存放在主进程的局部存储器中第五十七页，共六十四页，2022年，8月28日主进程代码：while(vertex_queue()!=empty){recv(PANY,source=Pi);/*requesttaskfromslave*/v=get_vertex_queue();send(&v,Pi);/*sendnextvertexand*/send(&dist,&n,Pi);/*currentdistarray*/recv(&j,&dist[j],PANY,source=Pi);/*newdistance*/append_queue(j,dist[j]);/*appendvertextoqueue*/}/*andupdatedistancearray*/for(i=0;i<slave-no;i++){recv(PANY,source=Pi);/*requesttaskfromslave*/send(Pi,termination_tag);/*terminationmessage*/}第五十八页，共六十四页，2022年，8月28日从进程代码：send(Pmaster);/*sendrequestfortask*/recv(&v,Pmaster,tag);/*getvertexnumber*/if(tag!=termination_tag){recv(&dist,&n,Pmaster);/*anddistarray*/for(j=1;j<n;j++)/*getnextedge*/if(w[v][j]!=infinity){