中山大学学报自然科学版 ›› 2019, Vol. 58 ›› Issue (4): 99-107.doi: 10.13471/j.cnki.acta.snus.2019.04.010

• 论文 • 上一篇    下一篇

多DAG任务调度算法

刘林东,邬依林   

  1. 广东第二师范学院计算机科学系,广东 广州 510303
  • 收稿日期:2019-04-10 出版日期:2019-07-25 发布日期:2019-07-25
  • 通讯作者: 邬依林(1970年生),男;研究方向:大数据分析与处理;E-mail: lyw@gdei.edu.cn

Multi-DAG task scheduling algorithms

LIU Lindong, WU Yilin   

  1. Department of Computer Science, Guangdong University of Education,Guangzhou 510303, China
  • Received:2019-04-10 Online:2019-07-25 Published:2019-07-25

摘要:

多DAG任务调度问题是当前研究的热点,为了提高任务调度的效率以及资源利用率,各个DAG的调度顺序以及每个DAG内部任务之间的调度顺序成为研究任务调度问题的关键。提出了一种基于分布式异构计算环境的多DAG任务调度模型和多DAG任务调度算法MDTS(multi-dags task scheduling algorithm)算法。算法首先对多个DAG任务进行合并,通过增加一个入口任务节点和出口任务节点的方法将多个DAG合并为一个DAG;然后根据每个任务节点的计算代价的方差以及平均通信开销对任务进行排序;最后基于HEFT算法降序对各个任务进行处理机调度。实验证明,MDTS算法在任务调度跨度、任务调度平均等待时间以及平均Slack方面均优于Sequential、Interleave算法。

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

Abstract:

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.

Key words: task scheduling, makespan, average waiting time, directed acyclic graph

中图分类号: