第18卷　第11期小型微型计算机系统Vol.18No.11 1997年11月MINI-MICROSYSTEMSNov.1997

对三种典型分布式任务分配算法的分析*何炎祥　罗先林　吴　思　彭堂玉　祝向幸(武汉大学计算机科学与技术学院　武汉430072)摘　要　本文先分析了基于图论的分配算法,整数规划方法和试探法等几种典型的分布式任务分配算法的基本思想、特点,不足和算法复杂度,以及可进一步改进之处,然后给出了一种试探法的改进算法,并简单讨论了其特点和性能,最后指出了分布式任务分配的发展方向。关键词　通信开销,执行开销,负载平衡,合一,试探法

在分布式系统中非同居模块间的数据传递产生处理机间的通信,这种机间通信可能使得增加处理机数目反而会引起系统吞吐量的降低,即产生“饱和效应”。为降低饱和效应,人们倾向于把模块分配到尽可能少的处理机上,但这又导致系统负载不平衡,从而降低了系统的吞吐量。显然,这是任务分配中相互冲突的两个方面,不同的任务分配算法试图用不同的策略来平衡这两个方面。传统的分布式任务分配算法大致可分为三类:基于图论的分配算法,整数规划方法和试探法。这三类算法并非互斥的,一类算法中往往可以借鉴其它方法中的某些技术。下面,我们先对这三类典型算法进行分析和比较,然后给出一种试探法的改进算法。在讨论中,我们假定提交的任务已分解成一组模块并使模块间的通信量尽可能小。还假定分配模式为:一任务被分解成m个模块T={t1,t2,…,tm},系统中有n个可利用的处理机P={p1,p2,…,pn}。任务分配的目的就是将这m个模块分配到n个处理机上,使预期的性能目标函数值最小。

1　对三种典型算法的分析

1.1　基于图论的分配算法基本思想是给定矩阵Cmxm表示模块间的通信开销:C={ci,j󰀁1≤i≤m&1≤j≤m&ci,j为ti与tj

间的通信量}

给定矩阵Qmxn表示模块的执行开销:Q={qi,j󰀁1≤i≤m&1≤j≤n&qi,j为ti在pj上的执行开销}将模块t1,t2,…,tm作为图中结点,若两模块间有数据传递,则相应结点间有一条无向边,

1996-04-26收稿　*软件工程国家重点实验室开放基金部分资助。何炎祥,教授,研究方向:分布式OS与分布信息处理,并行程序设计与编译系统。罗先林、吴思,研究生,研究方向:分布式OS与分布信息处理。边上的权wi,j=ci,j;处理机p1,p2,…,pn也作为图中结点,若qi,k≠∞,则在ti与pk间有一条边,定义该边上的权为wi,k=1n-1∑j≠kqi,j-n-2n-1ci,k。于是,可将该图视为一个网络,并定义n度割集为将网络中各个结点分割成n个不相交的子集,使得每个子集中有且仅有一个处理机结点。可以证明,每个切口的开销正好是执行开销和通信开销之和,因此,在图上执行MaxFlow/MinCut算法,就可得到任务的最优分配方案[1]。在现阶段,仅有多项式复杂度n=2的MaxFlow/MinCut算法,因此,基于图论的分配算法仅限于在处理机数目小于3的环境中使用,因而局限性较大。Lo在[1]中提出了一种改进算法。该算法分为迭代、汇总和贪心三个阶段。在第一阶段的每一轮迭代中,依次考虑每个结点p1,p2,…,pn,把pj和p-j=P-{pj}作为两个独立的结点,并将所有到P-{pj}的边用一个到p-j的边代替,该边上的权为所有到P-{pj}的边上的权之和。利用MaxFlow/MinCut算法,可得到分配给pj的模块的一个子集。删去在此轮迭代中已分配给pj的那些模块结点,并定义未删除的模块tj与处理机pk间的权为qi,k=qi,j+∑tj为已分配给p-k的某个处理机的模块ci,j

若所有的模块结点已分配完,或在最后一轮迭代中没有模块分配给某个处理机,则迭代阶段结束。Lo证明了迭代的终止性及若此时模块分配完则将获得最优解。在汇总阶段,首先计算一个优化的n度割集的下界L=∑tj∈T′mink(qi,k)+minj≠rc(pj,pr)

其中,c(pj,pr)为任意选择的处理机间最小切口的开销,T′为所有第一阶段中没有分配的模块的集合。然后,检查将剩余模块指派到某个处理机上是否更合适,若是,则算法结束,也得到一个最优解。否则进入贪心阶段。将相互通信开销大的模块汇集成簇,同一簇中的模块分配到同一个处理机上,这样得到的结果是次最优的。这个改进算法解决了基本算法在处理机数目上的限制。为使此算法更能反映真实情况,Lo还考虑了每个处理机上可利用资源的限制和同居模块间的通信开销,并引入了冲突开销的因素。此外,Lo提出了一种限制各处理机上模块数的方法,其基本思想是:若m>2n,则先进行合一,并保证合一后的簇中模块数目不超过[B/2](B为一处理机上最大允许的模块数)。重复这种合一过程,直至模块簇数目m′≤2n,然后再用适当算法将m′个模块簇按最小执行开销分配到n个处理机上。这个改进算法利用了试探法中对模块进行合一的思想,并直接利用了现有的网络算法,因此实现较简单,但算法开销大,因为MaxFlow/MinCut算法的时间复杂度为O(a2log2+a/n

b),其中a,b分别为边数和结点数。每次迭代中,每获得分配给一个处理机的模块子集的复

杂度为O(m4log2m)(设系统为全互连的),这样,每次迭代的开销为O(nm4log2m),而最坏迭代次数为m。因此,最坏情况下的复杂度为O(nm5log2m)。此外,该算法没有明确反映实时性和存储方面的限制,没有提供保护模块优先关系的机制,也不能衡量排队延迟对吞吐量的影响。1.2　整数规划方法基本思想是仍用前面定义的Q矩阵表示执行开销,但用Vm×m表示模块间的通信开销:V={vi,j󰀁1≤i≤m&1≤j≤m&vi,j为ti向tj

传递的数据量}

2 小型微型计算机系统 1997年同时引进一个距离矩阵Dnxn:D={di,j󰀁1≤i≤n&1≤j≤n&di,j为pi与pj

间的距离}

模块分配函数用矩阵Xmxm来定义:

X={xi,j󰀁1≤i≤m&1≤j≤n&xi,j=1　表示ti分配到pj上xi,j=0　否则该分配方法的目标函数定义为:

T(X)=∑k∑i{qi,kxi,k+∑r其中,常数w用来调节通信开销和执行开销间的差异。此时任务分配即要找使T最小的那个X的指派。因此,这种方法实质上是带有某些限制条件的隐式枚举算法,其时间复杂度随问题规模成指数增长。这显然限制了算法的实用性。这种方法的优点是很容易加入适当的限制条件,以满足实际环境的需要。[2]提出了一种分支界限法,它用一棵搜索树来表示分配问题,每个叶子结点处表示一个分配方案。除了存储限制和实时限制外,它还引入了以下限制条件:

模块优先矩阵P*mxn

pi,j=1　表示ti不能分配给pj;

pi,j=0　否则

模块互斥矩阵E

mxm

ei,j=1　表示ti和tj不能分配给同一处理机;

ei,j=0　否则并允许一个任务(模块)的多份拷贝,以提高系统的可靠性。该算法在每个分支处检查P*,E关系和存储及实时限制条件,若不满足,则剪枝;若满足,则检查这次分配后的部分开销是否超过已得到的最小全部开销,若超过,则剪枝;否则就分配,并选择下一扩充结点。若全部可能的路径都被探查完,或规定的执行时间已到,则算法结束。该算法的空间复杂度较小,只需记录当前最小开销的分配方案和此开销即可,约为O

(mn)。但时间复杂度仍可能是指数级的,而且没有保护模块优先规定的机制和实施负载平衡的机制。对该算法,还可以进行如下改进:󰀁输入模块间的优先规定,利用拓扑排序算法对模块进行拓扑排序,并以此顺序作为扩

充下一结点的次序。󰀁在探查ti的pk分枝时,若ti有优先模块,则将它在pk上的执行时间作如下调整:

q′i,k=qi,k+max{0,qj′,r-qj″,k}其中,tj′为分配在pr(r≠k)上的ti的优先模块,tj″为分配在pk上的tj的优先模块。这样,就可有效地实现模块间的优先级的规定。还可以利用试探法的合一算法,将提交的模块合一成n个模块簇,这样搜索空间可降为n。1.3　试探法试探法[3,4]与前两种方法不同,它以次最优解为目标,其基本思想是先选择具有最大通信开销的一对模块,若有一处理机能按一定的实时限制和存储限制处理这对模块,则将它们合一(形成模块簇,以准备进入下一轮迭代);否则选择下一对具有最大通信量的模块,重复上述过程,直至再无可合一的模块对,迭代过程结束,将同一模块簇中的模块指派给同一处理机。这种算法的特点是执行开销小,其最坏情况下的时间复杂度为O(m2logm)。由于把m

311期 何炎祥等:对三种典型分布式任务配算法的分析 个模块分配到n个处理机上有nm种分配方案,最优解通常是很难获得的,但当不要求最优分配或不可能实现最优分配时,这种方法还是很有吸引力的,这种方法的不足之处在于:󰀁若合一过程结束后,模块簇的数目仍大于处理机的数目(设为n+k),显然应把这k

个多余的模块簇分配给各处理机,必要时,可能还得对模块簇进行分裂,但该算法并未考虑这一点。󰀁它未考虑模块互斥以及处理机性能可能不同等情况,因此,难能满足实际分配问题的

需要。󰀁该算法开销中的很大一部分用来寻找通信量最大的模块对。

Efe[3]提出的试探法含两个阶段:合一和调整,基本思想是先对模块进行合一,然后,若发现处理机间负载不平衡,则改变相应参数后重新进行合一。它以模块为结点,通信量为边将任务分配问题表示成一个process图。Efe指出某些模块可能仅能分配给某一或某几个处理机,这类模块称为附属模块,合一过程此时改为按附属模块形成簇。然后,先把包含仅能分配给某个处理机的模块的模块簇分配给该处理机,再分配包含其它附属模块的模块簇,最后分配不包括附属模块的模块簇。每次分配都以使系统负载最平衡为目标,如可用best-fit方法。模块分配完后,检查负载是否平衡,若平衡,则算法停止;否则进入调整阶段。在调整阶段,先根据各处理机的负载状况,标记各处理机为平衡、超载、轻载;将已分配给平衡处理机的模块从原process图中去掉;照抄分配给超载处理机的所有模块;用一个结点代表分配给轻载处理机的模块,并用原来所有到该结点相关模块的边的权之和作为到该结点的边的权;然后,对每个超载处理机执行下面的动作:寻找分配给超载处理机pk的模块簇到分配给轻载处理机pm的模块簇的边,设这样的边的个数为nk,m,在每条这样的边的权上增加󰀁Lk-Lm󰀁/nk,m,其中Li为pi上的负载。对这个新形成的process图重新执行合一过程。显然这种方法通过把因某种分配方案引起的负载不平衡方面的开销转移到通信开销上,并进行重新合一来试图得到更合理的分配方案,因此,它同时兼顾了减少通信量和均衡负载这两个因素。对这个算法,还存在以下需改进处:󰀁在合一阶段考虑了对附属模块的处理方法,但在调整阶段并未考虑附属模块的特殊