对三种典型分布式任务分配算法的分析_何炎祥

　　第18卷　第11期

　　　1997年11月小型微型计算机系统M IN I -M I CR O SY ST EM S Vo l. 18N o. 11No v . 1997

对三种典型分布式任务分配算法的分析

何炎祥　罗先林　吴　思　彭堂玉　祝向幸

(武汉大学计算机科学与技术学院　武汉430072) *

摘　要　本文先分析了基于图论的分配算法, 整数规划方法和试探法等几种典型的分布式任务分配算法的基本思想、特点, 不足和算法复杂度, 以及可进一步改进之处, 然后给出了一种试探法的改进算法, 并简单讨论了其特点和性能, 最后指出了分布式任务分配的发展方向。

关键词　通信开销, 执行开销, 负载平衡, 合一, 试探法

在分布式系统中非同居模块间的数据传递产生处理机间的通信, 这种机间通信可能使得增加处理机数目反而会引起系统吞吐量的降低, 即产生“饱和效应”。为降低饱和效应, 人们倾向于把模块分配到尽可能少的处理机上, 但这又导致系统负载不平衡, 从而降低了系统的吞吐量。显然, 这是任务分配中相互冲突的两个方面, 不同的任务分配算法试图用不同的策略来平衡这两个方面。

传统的分布式任务分配算法大致可分为三类:基于图论的分配算法, 整数规划方法和试探法。这三类算法并非互斥的, 一类算法中往往可以借鉴其它方法中的某些技术。下面, 我们先对这三类典型算法进行分析和比较, 然后给出一种试探法的改进算法。

在讨论中, 我们假定提交的任务已分解成一组模块并使模块间的通信量尽可能小。还假定分配模式为:一任务被分解成m 个模块T ={t 1, t 2, …, t m }, 系统中有n 个可利用的处理机P={p 1, p 2, …, p n }。任务分配的目的就是将这m 个模块分配到n 个处理机上, 使预期的性能目标函数值最小。

1　对三种典型算法的分析

1. 1　基于图论的分配算法

基本思想是给定矩阵C mxm 表示模块间的通信开销:

C ={c i, j 1≤i ≤m&1≤j ≤m&ci, j 为t i 与t j 间的通信量}

给定矩阵Q mxn 表示模块的执行开销:

Q={q i, j 1≤i ≤m&1≤j ≤n&qi, j 为t i 在p j 上的执行开销}

将模块t 1, t 2, …, t m 作为图中结点, 若两模块间有数据传递, 则相应结点间有一条无向边, 1996-04-26收稿　*软件工程国家重点实验室开放基金部分资助。何炎祥, 教授, 研究方向:分布式OS 与分布信息处理, , ,

　　　　　　　　　　　　　　　小型微型计算机系统　　　　　　　　　　　　　　　1997年2

边上的权w i, j =c i, j ; 处理机p 1, p 2, …, p n 也作为图中结点, 若q i, k ≠∞, 则在t i 与p k 间有一

条边, 定义该边上的权为w i, k =∑q i, j -c i, k 。于是, 可将该图视为一个网络, 并定n-1j ≠k n-1

义n 度割集为将网络中各个结点分割成n 个不相交的子集, 使得每个子集中有且仅有一个处理机结点。可以证明, 每个切口的开销正好是执行开销和通信开销之和, 因此, 在图上执行M ax Flow /M inCut 算法, 就可得到任务的最优分配方案。在现阶段, 仅有多项式复杂度n=2的M ax Flow /M inCut 算法, 因此, 基于图论的分配算法仅限于在处理机数目小于3的环境中使用, 因而局限性较大。

Lo 在[1]中提出了一种改进算法。该算法分为迭代、汇总和贪心三个阶段。在第一阶段的每一轮迭代中, 依次考虑每个结点p 1, p 2, …, p n , 把p j 和-p j =P-{p j }作为两个独立的结点, 并将所有到P -{p j }的边用一个到-p j 的边代替, 该边上的权为所有到P -{p j }的边上的权之和。利用M axFlow /M inCut 算法, 可得到分配给p j 的模块的一个子集。删去在此轮迭代中已分配给p j 的那些模块结点, 并定义未删除的模块t j 与处理机p k 间的权为

q i, k [1]=q i, j +-t 为已分配给p 的某个处理机的模块j k ∑c i, j

若所有的模块结点已分配完, 或在最后一轮迭代中没有模块分配给某个处理机, 则迭代阶段结束。Lo 证明了迭代的终止性及若此时模块分配完则将获得最优解。

在汇总阶段, 首先计算一个优化的n 度割集的下界

L =∑m in (q

t ∈T ′j k i, k ) +min c(p j , p r ) j ≠r

其中, c(p j , p r ) 为任意选择的处理机间最小切口的开销, T ′为所有第一阶段中没有分配的模块的集合。然后, 检查将剩余模块指派到某个处理机上是否更合适, 若是, 则算法结束, 也得到一个最优解。否则进入贪心阶段。将相互通信开销大的模块汇集成簇, 同一簇中的模块分配到同一个处理机上, 这样得到的结果是次最优的。

这个改进算法解决了基本算法在处理机数目上的限制。为使此算法更能反映真实情况, Lo 还考虑了每个处理机上可利用资源的限制和同居模块间的通信开销, 并引入了冲突开销的因素。此外, Lo 提出了一种限制各处理机上模块数的方法, 其基本思想是:若m >2n , 则先进行合一, 并保证合一后的簇中模块数目不超过[B/2](B 为一处理机上最大允许的模块数) 。重复这种合一过程, 直至模块簇数目m ′≤2n, 然后再用适当算法将m ′个模块簇按最小执行开销分配到n 个处理机上。

这个改进算法利用了试探法中对模块进行合一的思想, 并直接利用了现有的网络算法, 因此实现较简单, 但算法开销大, 因为M ax Flo w /MinCut 算法的时间复杂度为O (a 2lo g 2+a/n b) , 其中a, b 分别为边数和结点数。每次迭代中, 每获得分配给一个处理机的模块子集的复杂度为O(m log 2m) (设系统为全互连的) , 这样, 每次迭代的开销为O(nm log 2m ) , 而最坏迭代次数为m 。因此, 最坏情况下的复杂度为O(nm lo g 2m ) 。此外, 该算法没有明确反映实时性和存储方面的限制, 没有提供保护模块优先关系的机制, 也不能衡量排队延迟对吞吐量的影响。

1. 2　整数规划方法

基本思想是仍用前面定义的Q 矩阵表示执行开销, 但用V m ×m 表示模块间的通信开销:v i t 544

11期　　　　　　　　　　　　何炎祥等:对三种典型分布式任务配算法的分析　　　　3同时引进一个距离矩阵D nxn :

D ={d i, j 1≤i ≤n&1≤j ≤n&di, j 为p i 与p j 间的距离}

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

X={x i, j 1≤i ≤m &1≤j ≤n&

该分配方法的目标函数定义为:

T (X) =x i, j =1　表示t i 分配到p j 上x i, j =0　否则i, k ∑∑{q k i x i, k +∑∑w v r

其中, 常数w 用来调节通信开销和执行开销间的差异。

此时任务分配即要找使T 最小的那个X 的指派。因此, 这种方法实质上是带有某些限制条件的隐式枚举算法, 其时间复杂度随问题规模成指数增长。这显然限制了算法的实用性。这种方法的优点是很容易加入适当的限制条件, 以满足实际环境的需要。

[2]提出了一种分支界限法, 它用一棵搜索树来表示分配问题, 每个叶子结点处表示一, 它还引入了以下限制条件:

p i, j =1　表示t i 不能分配给p j ; *模块优先矩阵P mxn i, j =0　否则

e i, j =1　表示t i 和t j 不能分配给同一处理机; 模块互斥矩阵E mxm e i, j =0　否则

并允许一个任务(模块) 的多份拷贝, 以提高系统的可靠性。

该算法在每个分支处检查P , E 关系和存储及实时限制条件, 若不满足, 则剪枝; 若满足, 则检查这次分配后的部分开销是否超过已得到的最小全部开销, 若超过, 则剪枝; 否则就分配, 并选择下一扩充结点。若全部可能的路径都被探查完, 或规定的执行时间已到, 则算法结束。

该算法的空间复杂度较小, 只需记录当前最小开销的分配方案和此开销即可, 约为O (mn ) 。但时间复杂度仍可能是指数级的, 而且没有保护模块优先规定的机制和实施负载平衡的机制。

对该算法, 还可以进行如下改进:

输入模块间的优先规定, 利用拓扑排序算法对模块进行拓扑排序, 并以此顺序作为扩充下一结点的次序。

在探查t i 的p k 分枝时, 若t i 有优先模块, 则将它在p k 上的执行时间作如下调整:

q ′i, k =q i, k +max {0, q j ′, r -q j ″, k }

其中, t j ′为分配在p r (r ≠k ) 上的t i 的优先模块, t j ″为分配在p k 上的t j 的优先模块。这样, 就可有效地实现模块间的优先级的规定。

还可以利用试探法的合一算法, 将提交的模块合一成n 个模块簇, 这样搜索空间可降为n 。

1. 3　试探法

试探法[3, 4]与前两种方法不同, 它以次最优解为目标, 其基本思想是先选择具有最大通信开销的一对模块, 若有一处理机能按一定的实时限制和存储限制处理这对模块, 则将它们合一(形成模块簇, 以准备进入下一轮迭代) ; 否则选择下一对具有最大通信量的模块, 重复上述过程, 直至再无可合一的模块对, 迭代过程结束, 将同一模块簇中的模块指派给同一处*

　　　　　　　　　　　　　　　小型微型计算机系统　　　　　　　　　　　　　　　1997年4

个模块分配到n 个处理机上有n 种分配方案, 最优解通常是很难获得的, 但当不要求最优分配或不可能实现最优分配时, 这种方法还是很有吸引力的, 这种方法的不足之处在于:

若合一过程结束后, 模块簇的数目仍大于处理机的数目(设为n+k) , 显然应把这k 个多余的模块簇分配给各处理机, 必要时, 可能还得对模块簇进行分裂, 但该算法并未考虑这一点。

它未考虑模块互斥以及处理机性能可能不同等情况, 因此, 难能满足实际分配问题的需要。

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

Efe [3]提出的试探法含两个阶段:合一和调整, 基本思想是先对模块进行合一, 然后, 若发现处理机间负载不平衡, 则改变相应参数后重新进行合一。它以模块为结点, 通信量为边将任务分配问题表示成一个process 图。

Efe 指出某些模块可能仅能分配给某一或某几个处理机, 这类模块称为附属模块, 合一过程此时改为按附属模块形成簇。然后, 先把包含仅能分配给某个处理机的模块的模块簇分配给该处理机, 再分配包含其它附属模块的模块簇, 最后分配不包括附属模块的模块簇。每次分配都以使系统负载最平衡为目标, 如可用best-fit 方法。模块分配完后, 检查负载是否平衡, 若平衡, 则算法停止; 否则进入调整阶段。在调整阶段, 先根据各处理机的负载状况, 标记各处理机为平衡、超载、轻载; 将已分配给平衡处理机的模块从原pr ocess 图中去掉; 照抄分配给超载处理机的所有模块; 用一个结点代表分配给轻载处理机的模块, 并用原来所有到该结点相关模块的边的权之和作为到该结点的边的权; 然后, 对每个超载处理机执行下面的动作:寻找分配给超载处理机p k 的模块簇到分配给轻载处理机p m 的模块簇的边, 设这样的边的个数为n k, m , 在每条这样的边的权上增加 L k -L m /n k, m , 其中L i 为p i 上的负载。对这个新形成的pr ocess 图重新执行合一过程。

显然这种方法通过把因某种分配方案引起的负载不平衡方面的开销转移到通信开销上, 并进行重新合一来试图得到更合理的分配方案, 因此, 它同时兼顾了减少通信量和均衡负载这两个因素。

对这个算法, 还存在以下需改进处:

在合一阶段考虑了对附属模块的处理方法, 但在调整阶段并未考虑附属模块的特殊性;

应扩充, 以允许加入多种限制条件。m

2　一个改进的试探算法

2. 1　算法输入

通信开销矩阵C mxm , 执行开销矩阵Q mxn , 模块优先矩阵P *mxn , 模块互斥矩阵E mxm , 以及每个处理机的实时限制R k 和S k 。

2. 2　算法描述及简单分析

2. 2. 1　第一阶段: fo r k=1to n do

k P 1k 0

11期　　　　　　　　　　　　何炎祥等:对三种典型分布式任务配算法的分析　　　　

*5块得到(实际上, 首先搜索P , 将此类模块形成链更合适, 其复杂度为O(nm ) ) 。将此类模块

标记为附属模块。

根据处理机的现有负载建堆或调整堆, 堆顶为负载最轻的处理机p k 。若堆不空, 则选p k ; 否则第一阶段结束。

若所有模块已分配, 则第一阶段结束; 否则, 若p k 不带有附属模块, 则在未分配的模块中任选一个为t i ; 否则, 选一个附属模块为t i 。

寻找与t i 有最大通信量的未分配的模块t j (复杂度为O (m ) ) 。若t j 的加入仍能满足以下条件:

a) 实时限制R k 和存储限制S k ;

b) p j, k =0, 即t j 能分配到p k 上;

c) t j 不与任何已分配给p k 的模块互斥。

则将t j 分配到p k 上, 否则取下一个与t j 通信量最大的模块为t j , 重复 。

由于第一阶段可能多次执行, 因此, 对C [i , 1…m ]先排序可以提高动态执行的效率。此阶段的复杂度最坏为O(m) , 但平均情况下为O(1) 。

若没有t j 能分配给p k , 则将p k 从堆中删去; 否则修改p k 的负载, 返到 。

不难得知, 第一阶段的最坏复杂度不超过O(m 2) , 因为, 最多可能循环m ′次(这里m ′为非附属模块的数目) 。

2. 2. 2　第二阶段

若第一阶段结束时所有模块已分配完, 则直接进入第三阶段; 否则, 说明剩余模块由于模块互斥条件和优先关系的限制, 以及实时和存储限制, 不能分配给任一处理机。在此, 逐个检查这些模块, 设当前的一个为t i , 并设t i 的一个优先模块为t j , 它已分配到p k 上, 则从p k 中取出t j , 而将t i 分配给p k , 并寻找可接收t j 的处理机(这种试探法在实际情况中可能很有效) 。

注意, 当模块互斥关系和优先关系比较稀疏时, 不会出现这种情况。这种情况的出现会影响算法的效率。

2. 2. 3　第三阶段

n

设处理机p i (i =1, 2, …, n ) 的负载为L i , 计算L =

若1-d ≤q k ≤1+d, 标记p k 为平衡; ∑L , k=1k Lave =L /n 。用q k =L k /Lave 表示处理机p k 上的负载状况。选择一个适当的常数d 并定义:

若q k

若q k >1+d , 标记p k 超载。

去掉分配给平衡处理机的模块, 拷贝超载处理机上的模块, 用一个模块代替轻载处理机上的模块, 并用所有到其中原有模块的边的权之和代替到该新模块的边的权; 去掉在超载处理机上所有附属模块到轻载处理机上模块的边; 去掉超载处理机上与轻载处理机中某个模块互斥的模块到该轻载处理机模块的边。

按Efe 的方法修改边上的权, 即在从超载处理机模块t k 到轻载处理机模块t m 的边的权上加上 L k -L m /n k, m 。 从第一阶段的 开始重新进行分配, 此时已不再包括平衡处理机及其上的模块。若此) 2

　　　　　　　　　　　　　　　小型微型计算机系统　　　　　　　　　　　　　　　1997年6

与Efe 相比, 本算法有如下特点:

本算法引入了模块间互斥的限制, 以及模块不能分配到某处理机的限制, 因而更符合实际;

Efe 算法是对模块簇执行best-fit 算法, 而本算法总是把合一后的一对模块分配到负载最轻的处理机, 本算法第一阶段结束时负载平衡性能更好, 重新调整的次数也少些;

Efe 算法中每次调整的算法复杂度约为O (n 2) +O (m 2) , 而本算法约为2O (m 2) 。

3　结束语

一般说来, 在由任意多个处理机组成的分布式系统中实现最优的任务分配是一个NP 完全问题, 因此, 传统分配算法一般都局限于寻找满足一个或几个性能目标函数的次最优解, 这是不能令人满意的, 解决途径之一是利用基于知识处理的智能化任务分配算法, 这是分布式任务分配的发展方向。

关于分布式任务分配问题尚存大量研究课题, 我们不仅要考虑任务分配本身, 还应从全局着手综合考虑诸如任务定义、任务分解、任务迁移、负载平衡等方面, 即应考虑分布式系统中任务的整个生命期。

参　考　文　献

〔1〕　V. M. Lo, Heuris tic Algorithms for Task As signm ent in Distribu ted S ysems, IE EE T rans . on Computer , Vol. 37,

No . 11, Nov . 1988.

〔2〕　P. R. M a et al. , A T as k Allocation M odel for Distrib uted Computing S ystem s, IE EE Tr ans . on Compu ter, Vol.

31, No. 1, Jan. 1982.

〔3〕　K . Efe , Heuristic M odels of T ask As sign ment S cheduling in Distrib uted S ystem s . I EE E Tr ans . on Computer , Vol .

15, No. 6, Jun. 1982.

〔4〕　何炎祥. 分布式系统中的“合一——阈值”任务分配算法, 计算机工程与应用, 1990, 10.

〔5〕　G. S. Blair et al. , A Know ledge-bas ed Operating System, The Computer Jour nal, Vol. 30, No. 3, 1987. 〔6〕　何炎祥. 分布式操作系统设计. 海洋出版社, 北京, 1993.

〔7〕　何炎祥等. 一种分布式OS 自动生成系统模型. 高技术通讯, Vol. 5, No. 4, 1995. 4. [7][5, 6]

ANALYSIS AND IMPROVEMENT ON THREE TYPES TYPICAL

ALGORITHMS FOR TASK ASSIGNMENT IN DISTR IBU TED SYSTEMS

HE Yanxiang 　LU O Xianlin 　WU Si 　PENG T ang yu 　ZH U Xiang xing

(Comp uter Colleg e o f W uhan Univ ersity , W uhan 430072)

Abstract 　T his paper fir st analysises the basic ideas , characteristics and improvements on thr ee ty pes ty pical algorithms fo r task assignment in distributed systems that they are g raph theory -based assignment algo rithms, integer planning method and heur istic mo dels, then we pr esent an improved heuristic alg orithm and discuss its disting uishing features and perfor-mances , finally , w e point out development trend of task assignment in distributed sy stems . Key words 　Co mmunicat ion costs, Executio n co sts, L oad balance, M erg er , Heuristic method