Scheduling DAGs on a Bounded Number of Processors

A new DAG scheduling algorithm named Reverse Clustering has been introduced in this paper. The load balancing problem has been handled in this approach in a more natural way than the edge-zeroing based clustering algorithms. This approach can be applied directly to systems with bounded numbers of processors, thus avoided the multistage scheduling strategy used in most of the state-of-the-art clustering based scheduling algorithms and resulted in a one-step, consistent method with less complexity than former approaches. Initial experimental results with reverse clustering algorithms showed promising potentials as an emerging technique. Keywords: Task scheduling; Multistage method; Clustering; DAG; Kernighan-Lin heuristic; Task allocation. 1. Introduction Task graph partitioning with applications in multiprocessor programming have received considerable attention in recent years. Many terms and techniques such as graph partitioning, grain packing, task allocation, task assignment, tas..