动态自由节点滞后的任务调度算法

Task Scheduling Algorithm of Dynamic Unrestricted Node Lag

任务调度是异构计算系统的核心问题之一。调度问题是一个NP完全问题,为获得次优解,出现了很多启发式的算法。分析表调度的典型算法,发现存在一些不足,提出一种新的方法——动态自由节点滞后调度算法,采用动态判断自由节点并对它们滞后调度,让对任务图调度长度影响更大的节点被优先调度,从而缩短调度长度,分析和实验结果表明该算法要优于ETF,MCP和BDCP算法。

Task scheduling is an integral part of parallel and distributed computing and one of the important problems in Heterogeneous Computing System（HCS）. The tasks scheduling problem is an NP-hard in general. In order to obtain better solutions, many scheduling heuristics are presented in the literature. This paper analyzes the typical algorithms of list scheduling, and there are some disadvantages of them. It proposes a new algorithm, Dynamic Unrestricted Node Lag（DUNL） that can generate an optimal scheduling. The algorithm selects the Unrestricted Nodes（UN） dynamically and then schedules them after all the other nodes, so it can schedule the nodes that have more influence on the schedule length in the Direct Acyclic Graph（DAG） first, and then the schedule length is shorter. The result of experiments shows that this algorithm is obviously better than ETF, MCP and BDCP algorithms.