摘要
网格环境下的任务调度是一个NP完全问题.为了确保每一步都能优先调度影响调度长度最大的就绪任务,提出一种采用动态任务优先级策略的任务调度算法.在进行任务调度的过程中,通过动态计算任务图DAG的关键路径并有效地利用处理器的空闲时间段来复制任务,使任务节点之间的通信开销尽可能降低,进而缩短整个任务图的完成时间.大量的模拟实验结果表明,所提的算法在任务完成时间上明显优于HEFT算法和DDS算法.
Task scheduling is a NP-complete problem in the grid environment.To ensure that the task most significantly affects the makespan can be scheduled in each scheduling step,the task scheduling algorithm by using dynamic task priority is proposed.The critical path of directed acyclic graph(DAG) is dynamically determined and the idle time slots of nodes are effectively utilized to replicate task for reducing the communication overhead and shortening the overall execution time.Extensive experiments are carried out and the research results show that the proposed algorithm outperforms the HEFT algorithm and the DDS algorithm in execution time.
出处
《大连理工大学学报》
EI
CAS
CSCD
北大核心
2012年第2期277-284,共8页
Journal of Dalian University of Technology
基金
国家自然科学基金资助项目(60973014)
关键词
网格环境
任务调度
动态任务优先级
任务复制
调度长度
grid environment task scheduling dynamic task priority task duplication scheduling length