一种基于分簇复制的DAG任务图调度算法  

A Scheduling Algorithm for Directed Acyclic Graph Based on Task Clustering and Duplication

作　　者：乔伟光[1] 曾国荪[2] 

机构地区：[1]同济大学计算机科学及技术系,上海200092 [2]国家高性能计算机工程技术中心同济分中心,上海200092

出　　处：《计算机工程》2006年第17期126-128,134,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(60173026);教育部科研基金资助重点项目(105071);上海高校网格技术E-研究院资助项目(200301-1)

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

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

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