基于时隙堆栈搜索的异构集群DAG调度策略  

DAG scheduling strategy for heterogeneous cluster based on deterministic search of slot stack

作　　者：薛亚非[1,2] 冯钧 XUE Ya-fei;FENG Jun(North Central College,Nanjing Normal University,Nanjing 210046,China;College of Computer and Information,Hohai University,Nanjing 210098,China)

机构地区：[1]南京师范大学中北学院,江苏南京210046 [2]河海大学计算机与信息学院,江苏南京210098

出　　处：《计算机工程与设计》2020年第6期1725-1732,共8页Computer Engineering and Design

基　　金：国家自然科学基金项目(51420105014、51505408);江苏省高等学校自然科学研究基金项目(18KJB520050)。

摘　　要：为提高异构集群应用程序有向无环图(directed acyclic graph,DAG)系统调度性能,利用传统列表式启发式算法作为基线算法获得异构集群DAGs任务调度方案初始解,在调度方案初始解中反复在初始方案时隙中迭代地推送和填充应用程序任务,实现初始解调度效果改进。其在改善诸如HEFT或HCPT等列表调度算法生成的初始解方面效果很好,保持了列表式调度算法较高的计算效率。在随机图形生成器创建各种DAGs应用程序任务调度模型中的仿真实验,其结果表明,所提算法在关键路径调度长度性能指标上具有显著优势。To improve the scheduling performance of the directed acyclic graph(DAG)system for heterogeneous cluster applications,the traditional list heuristic algorithm was used as the baseline algorithm to obtain the initial solution of the DAGs task scheduling scheme for heterogeneous clusters.In the initial solution of the scheduling scheme,the application tasks were iteratively pushed and filled in the slot of the initial scheme repeatedly,and the effect of the initial demodulation was improved.It is very effective to improve the initial solution generated using list scheduling algorithms such as HEFT or HCPT,while maintaining the high computational efficiency of list scheduling algorithms.The simulation experiments of various DAGs application task scheduling models created by random graph generator show that the proposed algorithm has significant advantages in the performance index of critical path scheduling length.

关 键 词：时隙 堆栈 确定性 异构集群 有向无环图 调度策略 

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