并行任务调度算法研究

《并行任务调度算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、收稿日期:2003207225;修返日期：2003211230并行任务调度算法研究马丹1，张薇1，2，李肯立1(1.华中科技大学计算机学院，湖北武汉430074;2.武汉军械士官学校，湖北武汉430075)摘要：对己有的并行任务调度研究方法进行了分类，并对各种并行任务图模型进行了阐述。在此基础上主要介绍了表调度、基于任务复制以及基于集群等的调度技术思想，进而对这儿种调度技术的典型算法作了简略的分析。最后对并行任务调度问题的未来研究方向进行/展望。关键词：并行计算；任务调度中图法分类号：TP316文献标识码：A文章编号：100123695(2004

2、)1120091204StudyonDispatchAlgorithmofParldclFashMADanl,ZHANGWeil,2,LIKen21il(.SchoolofComputer,HuazhongUniversityofSciencetechnology,WuhanHubei430074，China;2.WuhanOrdnanceN.0.C.AcademyofPLAfWuhanHubei430075，China)Abstract:Classifiesexistparalleltaskschedulingmethodsandsomemo

3、delsofparalleltaskgraphs.Itmainlyintroducesthebasicideasoflistscheduling,taskduplication2basedschedulingandcluster2basedscheduling.Furtheritfocusesontheanalysistotypicalalgorithmofabovebasicschedulingtechnologies.Finallyitprospectsthedirectionofparalleltaskschedulinginthefutu

4、re.Keywords:ParallelComputing;TaskScheduling1.引言在并行计算与处理中，如何把复杂应用程序的所有任务调度到多处理器系统,并追求最小的整个执行时间的问题一直是众所周知的难题。一般来说，对该问题寻求最优解在绝大多数的情况下是NP完全问题。但少数情况例外，当任务图是自由树结构而所有任务节点是相同权值并且处理器数目不限时，Hu［l］提出了一个线性时间复杂度的最优解。当任务图是任意结构节点拥有相同权值而处理器个数限定为两个吋,Coffman等［2］提出了0(M)吋间复杂度(/?代表任务节点的个数)的最优解;随后S

5、ethi［3的算法进行了改进得到了几乎是线性复杂度的最优解。上述三种情况都没有考虑节点之间的通信情况。另外在一些限制条件下基于任务复制的调度算法也可以得到非指数时间复杂度的最优解。相反，Ullrnan［4］证明了把单位节点权重的任务图调度到P个处理器的问题以及任务节点权重限于一个或两个单位组成的任务图到两个处理器的问题都是NP完全问题;Papadimitriou等人［5］证明了即使允许任务复制的前提下调度单位权重节点的任意任务图到P个处理器的问题也是NP完全问题。由于在大多数现实的条件下不可能得到非指数时间复杂度的最优解，所以对该问题的大多数研宄

6、侧重于如何在满足时间复杂度的前提下获取近似最优解的启发式算法。一般来说,并行任务的调度问题可以看作两个逻辑上相对独立的阶段：①所谓的任务映射(Map)或任务调度(Assign)，即确定任务节点映射到哪一个只体的处理单元上，简单表述为：=其中乃.代表任务节点，"代表处理单元，77表示任务节点的个数，々代表处理单元的个数。②任务的具体调度，即对于所有的处理单元，映射在其上的相应任务节点具体何时开始执行，可以表述为SchMb)s：^L^UtT,)}W屮STY仏:衣示任务7；的开始执行时间。在调度算法中，这两个阶段可以显式地反映出来，如基于Cluste

7、r的调度算法;也可能根本看不出这W个阶段的分界，如基于表的调度算法。考虑到任务图的基本信息以及处理单元本身和其互连结构的基本信息是否在应用程序执行前可以得到，已经调度好的任务是否可以由于其处理单元失效而实吋迁移等因数可以把并行任务调度算法分为两大类。一类假设任务图和处理单元相关的信息在程序执行前可以精确获取，调度好的任务节点不能迁移，基于这类假设的调度算法称为静态调度算法，也叫编译时间调度算法;反之则称为动态调度算法，也叫实时调度算法。前者存在如何精确获取所需信息的问题，但其可凭借成熟的模型组织有效而具体的启发式算法，文献屮人多数算法均属于此类算

8、法;后者需要程序实吋执行期间得到相应调度信息来调度任务，右许多不确定因数存在，调度开销一般较大，但在大型分布式系统如网格计算中该类算法不