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

Task Scheduling Algorithm of Dynamic Unrestricted Node Lag

作　　者：王涛[1] 曾志文[1] 陈志刚[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083

出　　处：《计算机工程》2009年第12期38-40,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60573127);湖南省自然科学基金资助项目(06JJ30032;05JJ40131)

摘　　要：任务调度是异构计算系统的核心问题之一。调度问题是一个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.

关 键 词：动态自由节点 滞后 任务调度 异构计算系统 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]