A New Scheduling Algorithm for Digraph-Based Parallel Computing
Zhang Ai · Chinese Journal of Computers · 2009
The scheduling algorithm is crucial for the efficiency of the digraph-based parallel computing. However,it is classically NP-complete to find a schedule with the shortest duration for a given digraph partition. In this paper,a new heuristic algorithm is presented using the well known forward-backward iterations. It is proved that this new algorithm is convergent locally under some conditions. Furthermore,the parallel implementation of the algorithm is given in detail. On hundreds processors,the benchmark results suggest that the new algorithm outperforms many scheduling algorithms widely used now.