基于异构环境的Out-Tree任务图的调度算法  

Heterogeneity Based Algorithm for Scheduling Out-Tree Task Graphs

作　　者：张建军[1] 宋业新[1] 旷文[1] 

机构地区：[1]海军工程大学理学院,武汉430033

出　　处：《计算机科学》2013年第4期107-110,146,共5页Computer Science

基　　金：国家自然科学基金项目(71171198);海军工程大学科学基金项目(HGDJJ05005)资助

摘　　要：分布式应用程序的有效调度是异构计算系统中的一个关键问题。目前已有的Out-Tree任务图的调度算法大多基于同构环境而开发,未考虑处理机的异构性,导致调度的效率较低。针对异构计算环境,提出一个基于列表和任务复制的Out-Tree任务图的静态启发式贪心调度算法,其时间复杂度为O(hv2 p),其中h、v和p分别表示任务图的高度、任务个数和调度使用的处理机个数。实验结果表明,相比其他算法,该算法能提供调度长度较短、处理机使用较少的有效调度,其应用性更强。Effective scheduling of a distributed application is one of the critical issues in heterogeneous computing systems.Many previous algorithms are developed based on homogeneous systems and neglect the heterogeneity of processors,which results in poor schedule efficiency.This paper proposed a heterogeneity,list and task duplication based static heuristics greedy algorithm for scheduling Out-Tree task graphs,the time complexity of which is O（hv2p） where h,v and p are the height of the DAG,the number of tasks in the task graph and the number of processors required respectively.The experimental results show that the proposed algorithm produces an efficient schedule which has shorter schedule length and less number of used processors in comparison with other related algorithms and so is more practical.

关 键 词：任务调度 Out-Tree任务图 异构性 任务复制 列表调度 调度长度 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]