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

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

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

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