基于任务复制的分簇与调度算法  

A Clustering and Scheduling Algorithm Based on Task Duplication

作　　者：何琨[1] 赵勇[2] 黄文奇[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074 [2]华中科技大学控制科学与工程系,武汉430074

出　　处：《计算机学报》2008年第5期733-740,共8页Chinese Journal of Computers

基　　金：国家自然科学基金(70471077);国家“九七三”重点基础研究发展规划项目基金(2004CB318000);中国博士后科学基金(20070420174)资助

摘　　要：针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法.改进了粒度的定义,证明了对任意DAG,算法有优于前人的性能下界.实验结果优于典型任务复制算法,特别是对经典EZ算例的解(调度长度为8)好于前人认为的理论最优解(调度长度为8.5),并证明了新的解为最优解.定义了DAG的补图,讨论了不允许任务复制时树型DAG的2-优度算法.This paper addresses an important and classic scheduling problem, the static scheduling of dependent tasks in homogeneous environment. It is NP hard even when the resources are unbounded, and finds many applications in the parallel and distributed computation area. Depend- ent tasks are usually denoted by Directed Acyclic Graph （DAG）, and solving heuristics are commonly categorized to priority list based, cluster based and task duplication based schemes. Taskduplication-based （TDB） algorithms are of better performance than non-duplication ones. A new TDB clustering and scheduling algorithm, called the dynamic critical predecessor （DCP） algo- rithm, is proposed in this paper. DCP algorithm defines a new selective strategy for important an- cestors to be duplicated. The primary aim is to get the shortest schedule length, and the next is to utilize as less resources as possible. Based on an improved definition of granularity, DCP algo- rithm achieves a better performance guarantee for arbitrary DAG than relative works reported in the literature. Experimental results on several benchmarks show that DCP algorithm is quite effective and it exceeds other classic TDB algorithms. Especially for the classic EZ benchmark, DCP algorithm gets an optimal solution with 8 makespan, which is better than the optimal result taken for before with 8. 5 makespan. Complement graph of a DAG is defined, and a similar algorithm is developed to produce a 2-optimal schedule for tree graph if task duplication is not allowed for the tasks.

关 键 词：任务复制 任务分簇 调度算法 DAG任务粒度 

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