多DAG任务调度算法  

Multi-DAG task scheduling algorithms

作　　者：刘林东 邬依林 LIU Lindong;WU Yilin(Department of Computer Science, Guangdong University of Education,Guangzhou 510303, China)

机构地区：[1]广东第二师范学院计算机科学系

出　　处：《中山大学学报（自然科学版）》2019年第4期99-107,共9页Acta Scientiarum Naturalium Universitatis Sunyatseni

基　　金：国家自然科学基金(61070015);广东省普通高校特色创新项目(自然科学类)(2018KTSCX163);广东省科技计划(2016A010106007,2016B090927010);广东第二师范学院网络工程重点学科项目(ZD2017004);广东第二师范学院计算机实践教学示范中心(2018sfzx01);广东第二师范学院高等教育教学改革项目(2019jxgg04)

摘　　要：多DAG任务调度问题是当前研究的热点,为了提高任务调度的效率以及资源利用率,各个DAG的调度顺序以及每个DAG内部任务之间的调度顺序成为研究任务调度问题的关键。提出了一种基于分布式异构计算环境的多DAG任务调度模型和多DAG任务调度算法MDTS(multi-dags task scheduling algorithm)算法。算法首先对多个DAG任务进行合并,通过增加一个入口任务节点和出口任务节点的方法将多个DAG合并为一个DAG;然后根据每个任务节点的计算代价的方差以及平均通信开销对任务进行排序;最后基于HEFT算法降序对各个任务进行处理机调度。实验证明,MDTS算法在任务调度跨度、任务调度平均等待时间以及平均Slack方面均优于Sequential、Interleave算法。Multi-DAG task scheduling problem is a hotspot of current research in distributed heterogeneous environment. In order to improve the efficiency of task scheduling and resource utilization, the scheduling order of each DAG and the scheduling order between tasks within each DAG become the key task scheduling problem. A multi-DAG task scheduling model based on distributed heterogeneous computing environment and multi-DAG task scheduling algorithm MDTS(Multi-Dags Task Scheduling algorithm) are proposed. Firstly, multiple DAG tasks are merged into one DAG by adding an entry task node and an exit task node. secondly tasks are sorted according to the variance of computing cost and average communication cost of each task node. Finally, processors are scheduled according to the order from high to low based on HEFT algorithm. Experiments show that MDTS algorithm is superior to Sequential and Interleave algorithm in task scheduling makespan, average waiting time and average Slack.

关 键 词：任务调度 跨度 平均等待时间 DAG 

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