摘要：

并行任务调度是影响机群计算效率的关键因素之一，机群环境DAG(Directed Acyclic Graph)任务图调度是一个NP完全问题，只能寻求启发式算法。已有的研究中，图解重构算法在允许任务复制的条件下，通过对DAG图递归分解与子图重构，初步实现了一个可行的调度方案。该文在此基础上，提出了以调度长度增量为依据的任务复制策略，利用该策略调整受制约节点的同簇前驱，解决了任务簇间的时间制约问题，缩短了调度长度；通过合理地选择任务簇进行合并，增大任务簇的粒度，提高了处理器的利用率。提出的以任务簇扩展-合并为特征、以分簇复制为手段的DAG图调度算法，改进和拓展了图解重构方法。实例分析表明本算法复杂度与TDS (Task Duplication Scheduling)相同，但性能更优。

关键词: 机群计算, 任务图, 任务调度, 分簇复制

Abstract: Parallel task scheduling is one of the key factors influencing the efficiency of clusters, and it is also a well-known strong NP-hard problem. Zhou and Zheng have proposed a task duplication based algorithm, which adopts recursion to implement DAG partition and sub-graph reconfiguration, then builds task clusters to carry out scheduling. This paper further exploits their method and proposes a task duplication strategy emphasizing the increment of scheduling length. Using this strategy, the restriction problem between clusters is effectively solved by adjusting the predecessors of the restricted task in the same cluster; besides, appropriate task clusters are selected and merged, leading to coarse-grained clusters and better processor utilization. Furthermore, a DAG scheduling algorithm based on task clustering and duplication is presented in this paper, which is characterized by expanding and merging clusters, and has advantages in both scheduling length and processor utilization over the original algorithm. Experiment results show that the algorithm has the same complexity with TDS (task duplication scheduling) and achieves better performance.

Key words: Cluster computing, Task graph, Task scheduling, Clustering and duplication

中图分类号: 

• TP338