An efficient task allocation algorithm and its use to parallelize irregular Gauss-Seidel type algorithms

The parallelization and implementation of Gauss-Seidel power flow analysis have been investigated. The desired properties to maximize the speedup, such as minimum communication overhead and balanced computational load, have been described. In this paper, we investigate a two-stage parallelization scheme to achieve the desired properties for distributed memory machines. In the first stage, we introduce a new efficient heuristic clustering algorithm which reduces the communication time and balances the computational load. In the second stage, we devise a coloring algorithm whose purpose is to minimize the synchronization overhead and coordinate the information exchange among processors. It is shown that the parallelization scheme effectively increases the speedup and the associated upper bound of the Gauss-Seidel algorithm on the nCUBE2 machine