An efficient load-balancing processor scheduling algorithm for parallelization of Gauss-Seidel type algorithms (Q1344545)

This paper is an extension of an earlier paper by the authors on the parallelization of Gauss-Seidel (G-S) algorithm for power flow analysis. In the earlier paper, the parallelizing process is formulated as a basic coloring problem, which satisfies the constraint that no directly connected vertices have the same color, without worrying about the constraint on the number of available processors. In this paper, the parallelization of G-S type algorithms which considers the number of available processors also as a constraint and maximizes the potential convergence rate of the G-S algorithms is presented. A heuristic approach which maximizes the efficiency of processor integration by using dishonest coloring and idling processor fall-ins is proposed. The algorithm is developed and tested on the power systems size ranging from 14 to the thousands. An example and list result on the IEEE 14 bus system are also given to demonstrate the heuristic process and its effect on the convergence behaviour of the G-S implementations.