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

Heterogeneity Based Algorithm for Scheduling Out-Tree Task Graphs

分布式应用程序的有效调度是异构计算系统中的一个关键问题。目前已有的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.