mps上作业的分配和调度问题

《mps上作业的分配和调度问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2000年1月系统工程理论与实践第1期　MPS上作业的分配和调度问题黄干平,陈世鸿(武汉大学数学与计算机科学技术学院,湖北武汉430072)摘要　多处理机系统MPS(MultiprocessorSystem)上作业的分配和调度问题是其运行效率的关键.本文讨论的是具有不相容性作业集的作业分配和调度问题,提出了一种启发式方法及其定量分析技术,并证明了相关定理和若干推论.关键词:不相容作业;运行时间;启发式算法中图分类号:TP30211aTheSchedulingProblemforMPSwithInco

2、mpatibleJobsHUANGGan2ping,CHENShi2hong(CollegeofMaths.&ComputerScienceandTechnology,WuhanUniversity,Wuhan430072)AbstractInthispaper,wepresentaheuristicschedulingalgorithmforMPS(Multi2ProcessorSystem)withincompatiblejobs,andtheperformanceanalysisofthisa

3、lgorithm.Someschedulingproblemcanbesolvedbasedontheheuristicmethodinpolynomialtimecomplexitywhenthejobgraphshavesomespecialstructuressuchasbipartitegraph,treeandsoon.Keywordsincompatibility;schedulinglength;heuristicalgorithm1　引言多处理机系统MPS的作业分配问题是如何将一个给

4、定的集中作业分配到各个处理机上运行从而使整个作业集完成时间最短的问题.工程实际中的作业集一般都具有某种程度的不相容性(incompatibility).一个作业集是具有不相容性的,如果其中至少有一对作业是不相容的.一对作业ji,jk是“不相容的”,指的是以下一些情况:这两个作业是可并行的;这两个作业是同类受限的;这两个作业是通讯量很小的;等等.显然,一对“不相容”作业(例如,两个可并行的作业)应分到不同的处理机,才有利于缩短作业和作业集的运行时间.令P={p1,p2,⋯,pm)是m个处理机的集合,J

5、={j1,j2,⋯,jn}是n个作业的集合,ti(i=1,2,3⋯n)是作业ji的运行时间.MPS的作业分配问题可分两步进行.第一步,将作业集表示成一个无向图G=(J,E)(J是结点集,每个结点代表一个作业;E是结点间的无向边集),若两个作业ji,jk是不相容的,则其间有一条无向边.然后,对图G着色,使任一条边的两个端结点具有不同的颜色,从而获得K个着色类,每个着色类代表一个作业子集;第二步,将m个处理机按某种方法分成K组(这里假定m>K),并将一个作业子集分给一组处理机.一般而言,上述等价于着色问

6、题的作业分配问题是NP-完全性问题,不存在确定型多项式复杂性解法,但对于某些具有特殊性质的作业集(例如其图G是偶图、树形等)则可以找到多项式复杂性的启发式算法.a收稿日期:1998203217资助项目:湖北省自然科学基金资助项目©1995-2005TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.第1期MPS上作业的分配和调度问题103本文先对其图G的一个K—着色已知的不相容性作业集给出一个启发式分配和调度方法,并对其分配和调度性能作定量分析;

7、然后将这一方法推广到其图G具有某种特性的情况下,并对其性能作进一步讨论,从而为设计实际的MPS分配和调度算法提供思路和性能评价的基础.2　启发式分配和调度方法假定具有不相容性的作业集所对应的图G已有了一个k—着色(2≤k

8、x1,(2)k$k且使∩Mi′=5(Mi′表示Ci分得的处理机子集)i=12)对每个Ci中的作业和处理机,采用线性表调度方法LS(ListScheduling):它线性地扫描Ci中的每一个作业并把它分给M′i中当前“已分长度”最短的那个处理机——所谓“已分长度”是该处理机至今已分得的作业运行时间之和.3令S、HS分别表示在给定条件下最佳调度的“调度长度”和启发式调度的“调度长度”,(一般表示为3HS≤QS,Q是一个确定的系数),则上述调度方法的性能可用如下定理给出:定