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

A Clustering and Scheduling Algorithm Based on Task Duplication

针对并行与分布式系统中相关任务的静态调度问题,以最小化调度长度为主要目标,以减少资源数为次要目标,对待复制的重要祖先集定义了新的选择策略,提出了基于任务复制的动态关键前驱调度算法.改进了粒度的定义,证明了对任意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.