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

计算机科学 ›› 2013, Vol. 40 ›› Issue (4): 107-110.

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

张建军,宋业新,旷文

海军工程大学理学院武汉430033;海军工程大学理学院武汉430033;海军工程大学理学院武汉430033

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金项目(71171198),海军工程大学科学基金项目(HGDJJ05005)资助

Heterogeneity Based Algorithm for Scheduling Out-Tree Task Graphs

ZHANG Jian-jun,SONG Ye-xin and KUANG Wen

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 分布式应用程序的有效调度是异构计算系统中的一个关键问题。目前已有的Out-Tree任务图的调度算法大多基于同构环境而开发,未考虑处理机的异构性,导致调度的效率较低。针对异构计算环境,提出一个基于列表和任务复制的Out-Tree任务图的静态启发式贪心调度算法,其时间复杂度为O(hv^2p),其中h、v和p分别表示任务图的高度、任务个数和调度使用的处理机个数。实验结果表明,相比其他算法,该算法能提供调度长度较短、处理机使用较少的有效调度,其应用性更强。

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

Abstract: 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(hv^2p) 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.

Key words: Task scheduling,Out-Tree task graph,Heterogeneity,Task duplication,List scheduling,Schedule length

张建军,宋业新,旷文. 基于异构环境的Out-Tree任务图的调度算法[J]. 计算机科学, 2013, 40(4): 107-110. https://doi.org/

ZHANG Jian-jun,SONG Ye-xin and KUANG Wen. Heterogeneity Based Algorithm for Scheduling Out-Tree Task Graphs[J]. Computer Science, 2013, 40(4): 107-110. https://doi.org/

参考文献

[1] Lotfifar F,Shahhoseini H S．A Low-Complexity Task Scheduling Algorithm for Heterogeneous Computing Systems[C]∥Third Asia International Conference on Modelling & Simulation．2009(5):596-601
[2] Hagras T,Janecek J．An approach to compile-time task scheduling in heterogeneous computing systems[C]∥Proc．International Conf．on Parallel Processing Workshops．2004:182-189
[3] Topcuoglu H,Hariri S,Wu M Y．Performance-effective and low-complexity task scheduling for heterogeneous computing[J]．IEEE Trans．Parallel and Distributed Systems,2002,13(3):260-274
[4] Kwok Y-K,Ahmad I．Dynamic Critical-Path Scheduling:An Effective Technique for Allocating Task Graphs to Multiprocessors[J]．Parallel and Distributed Systems,1996(7):506-521
[5] Darbha S,Agrawal D P．Optimal Scheduling Algorithm for Distributed-Memory Machines[J]．IEEE Trans．Parallel and Distributed Systems,1998,9(1):87-95
[6] Liu Zhen-ying,Fang Bin-xing,Zhang Yi．TSA-OT,An Algo-rithm Scheduling An Out-Tree DAG[J]．Chinese Journal of Computers,2001,24(4):1-5
[7] 张建军,李庆华,瞿勇．基于任务复制的调度算法[J]．计算机工程与设计,2009,30(8):1896-1899
[8] Omara F A,Arafa M M．Genetic Algorithms for Task Scheduling Problem[J]．Journal of Parallel and Distributed Computing,2010,0(1):13-22
[9] Zhong Yi-wen,Yang Jian-gang,Qia Heng-nian．Hybrid Genetic Algorithm for Tasks Scheduling in Heterogeneous Computing Systems[C]∥Proceedings of the Third International Conference on Machine Learning and Cybernetics．Shanghai．2004(8):26-29
[10] Darbha S,Agrawal D P．A task duplication based scalable schedu-ling algorithm for distributed memory systems[J]．Journal of parallel and Distributed Computing,1997,46(1):15-27
[11] Yang Jia-dong,Xu Hua,Jia Pei-fa．Task Scheduling for Heterogeneous Computing based on Bayesian Optimization Algorithm[C]∥2009International Conference on Computational Intelligence and Security．2009:112-117

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed