Chinese Journal of Computers   Full Text
Title	A New Scheduling Algorithm for Digraph-Based Parallel Computing
Authors	ZHANG Ai-Qing MO Ze-Yao
Address	(High Performance Computing Center, Institution of Applied Physics and Computational Mathematics, Beijing 100094)
Year	2009
Issue	No.11(2178—2186)
Abstract &   Background	Abstract 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. Keywords digraph; parallel computing; scheduling algorithm; forward-backward iterations Backgound This paper is supported by a grant from the National Key Basic Research Special Fund (2005CB321702), and the National Natural Science Foundation of China (Nos.60533020, 60603050, 90718029). The projects mainly focus on the parallel algorithms for large scale scientific numerical simulations. A closely related work of the research group is the development of a parallel framework of grid-based numerical algorithms where data dependencies between grid zones can be modeled by a directed acyclic graph. The parallel framework consists of three parts on how to partition, order and calculate the vertices of digraph. This paper focuses on the second part, and proposes a new scheduling algorithm to improve the parallel efficiency of the numerical algorithms based on the digraphs.