异构计算环境下一种新型的多DAG任务调度算法
|
摘要
随着计算机技术的发展与用户需求的不断提升,多有向无环图(DAG)共享一组异构计算资源的问题受到广泛的关注。但由于实际任务的复杂多变,多个DAG之间存在一定的差异,导致多DAG调度策略存在公平性问题。为此,提出一种改进的启发式公平调度算法IFairness。在选择待调度DAG阶段采用一种新的评判指标DAG完成度,代替原Fairness算法中的剩余Makespan作为DAG选择依据,在计算每个DAG的滞后程度阶段,采用"向后看"一步的原则,解决某些DAG在初期得不到调度的问题。仿真结果表明,与原Fairness算法相比,IFairness算法不公平程度降低了7.28%,资源利用率提升了11.97%,有效提高了调度算法的公平性及资源利用率。
With the development of computer technology and the continuous improvement of user needs,the problem of multiple Directed Acyclic Graph(DAG) sharing the same group of heterogeneous computing resources has attracted wide attention.However,due to the complexity and change of the actual tasks,there are certain differences between multiple DAG,which lead to the fairness problem of multiple DAG scheduling strategies.Therefore,this paper proposes an improved heuristic fair scheduling algorithm,IFairness.In selecting the DAG phase to be scheduled,a new evaluation index DAG completion degree is adopted,which replaces the remaining Makespan in the original Fairness algorithm as the DAG selection basis.In the calculation phase of the lag degree of each DAG,the principle of "looking forward one step"is adopted to solve the problem that some DAG cannot be scheduled at the initial stage.Simulation results show that compared with the original Fairness algorithm,the unfairness degree of the IFairness algorithm is reduced by 7.28%,and the resource utilization rate is improved by 11.97%,which effectively improves the fairness and resource utilization rate of the scheduling algorithm.
With the development of computer technology and the continuous improvement of user needs,the problem of multiple Directed Acyclic Graph(DAG) sharing the same group of heterogeneous computing resources has attracted wide attention.However,due to the complexity and change of the actual tasks,there are certain differences between multiple DAG,which lead to the fairness problem of multiple DAG scheduling strategies.Therefore,this paper proposes an improved heuristic fair scheduling algorithm,IFairness.In selecting the DAG phase to be scheduled,a new evaluation index DAG completion degree is adopted,which replaces the remaining Makespan in the original Fairness algorithm as the DAG selection basis.In the calculation phase of the lag degree of each DAG,the principle of "looking forward one step"is adopted to solve the problem that some DAG cannot be scheduled at the initial stage.Simulation results show that compared with the original Fairness algorithm,the unfairness degree of the IFairness algorithm is reduced by 7.28%,and the resource utilization rate is improved by 11.97%,which effectively improves the fairness and resource utilization rate of the scheduling algorithm.
引文
[1] WU An,YU Han,JIN Shiyuan,et al.An incremental genetic algorithm approach to multiprocessor scheduling[J].IEEE Transactions on Parallel and Distributed Systems,2004,15(9):824-834.
[2] SIH G C,LEE E A.A compile-time scheduling heuristic for interconnection constrained heterogeneous processor architectures[J].IEEE Transactions on Parallel and Distributed Systems,1993,4(2):175-187.
[3] TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.
[4] WU Minyou,GAJSKI D D.Hypertool:a programming aid for message-passing systems[J].IEEE Transactions on Parallel and Distributed Systems,1990,1(3):330-343.
[5] 刘亚秋,邵洪润,景维鹏.云环境下融合安全与可用性的DAG任务调度[J].计算机工程,2014,40(12):12-18.
[6] XU Yuming,LI Kenli,HU Jingtong,et al.A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues[J].Information Sciences,2014,270(6):255-287.
[7] WEN Yun,XU Hua,YANG Jiadong.A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system[J].Information Sciences,2011,181(3):567-581.
[8] 赵瑞姣,朱怡安,李联.基于异构多核系统的混合关键任务调度算法[J].计算机工程,2018,44(2):51-55.
[9 ] YU Zhifeng,SHI Weisong.A planner-guided scheduling strategy for multiple workflow applications[C]//Proceedings of IEEE International Conference on Parallel Processing.Washington D.C.,USA:IEEE Press,2008:1-8.
[10] FHRINGER T,PRODAN R,DUAN R,et al.ASKALON:a grid application development and computing environment[C]//Proceedings of IEEE International Workshop on Grid Computing.Washington D.C.,USA:IEEE Press,2005:10-21.
[11] 田国忠.多DAG共享资源调度的若干问题研究[D].北京:北京工业大学,2013.
[12] HONIG U,SCHIFFMANN W.A meta-algorithm for scheduling multiple DAGs in homogeneous system environments[C]//Proceedings of the 18th International Conference on Parallel and Distributed Computing and Systems.Piscataway,USA:[s.n.],IEEE Press,2006:147-152.
[13] ZHAO Henan,SAKELLARIOU R.Scheduling multiple DAGs onto heterogeneous systems[C]//Proceedings of International Conference on Parallel and Distributed Processing Symposium.Washington D.C.,USA:IEEE Press,2006:14-21.
[14] 任丰玲,于炯,杨兴耀.基于最小化传输和完成时间的多DAG调度[J].计算机工程,2012,38(23):287-290.
[15] 田国忠,肖创柏,徐竹胜,等.异构分布式环境下多DAG工作流的混合调度策略[J].软件学报,2012,23(10):2720-2734.
[2] SIH G C,LEE E A.A compile-time scheduling heuristic for interconnection constrained heterogeneous processor architectures[J].IEEE Transactions on Parallel and Distributed Systems,1993,4(2):175-187.
[3] TOPCUOGLU H,HARIRI S,WU M Y.Performance-effective and low-complexity task scheduling for heterogeneous computing[J].IEEE Transactions on Parallel and Distributed Systems,2002,13(3):260-274.
[4] WU Minyou,GAJSKI D D.Hypertool:a programming aid for message-passing systems[J].IEEE Transactions on Parallel and Distributed Systems,1990,1(3):330-343.
[5] 刘亚秋,邵洪润,景维鹏.云环境下融合安全与可用性的DAG任务调度[J].计算机工程,2014,40(12):12-18.
[6] XU Yuming,LI Kenli,HU Jingtong,et al.A genetic algorithm for task scheduling on heterogeneous computing systems using multiple priority queues[J].Information Sciences,2014,270(6):255-287.
[7] WEN Yun,XU Hua,YANG Jiadong.A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system[J].Information Sciences,2011,181(3):567-581.
[8] 赵瑞姣,朱怡安,李联.基于异构多核系统的混合关键任务调度算法[J].计算机工程,2018,44(2):51-55.
[9 ] YU Zhifeng,SHI Weisong.A planner-guided scheduling strategy for multiple workflow applications[C]//Proceedings of IEEE International Conference on Parallel Processing.Washington D.C.,USA:IEEE Press,2008:1-8.
[10] FHRINGER T,PRODAN R,DUAN R,et al.ASKALON:a grid application development and computing environment[C]//Proceedings of IEEE International Workshop on Grid Computing.Washington D.C.,USA:IEEE Press,2005:10-21.
[11] 田国忠.多DAG共享资源调度的若干问题研究[D].北京:北京工业大学,2013.
[12] HONIG U,SCHIFFMANN W.A meta-algorithm for scheduling multiple DAGs in homogeneous system environments[C]//Proceedings of the 18th International Conference on Parallel and Distributed Computing and Systems.Piscataway,USA:[s.n.],IEEE Press,2006:147-152.
[13] ZHAO Henan,SAKELLARIOU R.Scheduling multiple DAGs onto heterogeneous systems[C]//Proceedings of International Conference on Parallel and Distributed Processing Symposium.Washington D.C.,USA:IEEE Press,2006:14-21.
[14] 任丰玲,于炯,杨兴耀.基于最小化传输和完成时间的多DAG调度[J].计算机工程,2012,38(23):287-290.
[15] 田国忠,肖创柏,徐竹胜,等.异构分布式环境下多DAG工作流的混合调度策略[J].软件学报,2012,23(10):2720-2734.