多DAG任务调度算法

摘要

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