基于DAG图解-重构的机群系统静态调度算法

机群系统静态任务调度是NP-完全问题,通常的算法是通过一些启发式算法得到多项式次优 解.该文提出的图解-子图重构算法实现了对分布在有向无环图(directed acyclic graph, 简称DAG)上的并行任务的快速有效调度.该算法的复杂性为O(log^|V|×(|V|+| E|)),采用递归方法实现了对任务图的有效分解和子图重构,生成任务群,完成任务调度,并 且初步实现了对处理机的优化.通过实例分析以及与其他启发式调度算法的性能比较,证明该 算法是一种快速、有效、可

A Static Scheduling Algorithm on DAG Partition-Reconfiguration in the Network of Workstations

Static task scheduling on network of workstations is well-known to be an NP-co mplete problem in a strong sense. Some heuristic algorithms have been proven to be sub-optimal under some restrictive conditions. In this paper, the authors pr esent a heuristic algorithm named DAG (directed acyclic graph) partition and sub -graph reconfiguration algorithm, which is a fast and effective one used in par allel task scheduling. The complexity of this algorithm is O(log^|V|I1518 ×(|V|+|E|)). It adopts recursion to implement DAG partition and sub-graph re configuration, then builds task clusters to carry out the task scheduling. At th e same time, it even optimizes the number of processors to some degree for it ha s not been solved before. The performance has been observed in a representative example compared with other existing scheduling schemes in terms of several valu able factors. The experimental results show that this algorithm is feasible.