异构计算环境下一种新型的多DAG任务调度算法  

A New Multiple DAG Task Scheduling Algorithm in Heterogeneous Computing Environment

作　　者：焦一鸣 周川[1] 郭健 崔玉伟 JIAO Yiming;ZHOU Chuan;GUO Jian;CUI Yuwei(School of Automation,Nanjing University of Science and Technology,Nanjing 210094,China;AVIC Xi’an Flight Automatic Control Research Institute,Xi’an 710065,China)

机构地区：[1]南京理工大学自动化学院,南京210094 [2]中航工业西安飞行自动控制研究所,西安710065

出　　处：《计算机工程》2019年第7期1-5,共5页Computer Engineering

基　　金：国家重点研发计划(2017YFB1001801);“十三五”装备预研公用技术项目(41412040101);江苏省重点研发计划(BE2017161)

摘　　要：随着计算机技术的发展与用户需求的不断提升,多有向无环图(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.

关 键 词：多有向无环图 公平性 启发式 完成度 资源利用率 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]