Managing the bottlenecks in parallel Gauss-Seidel type algorithms for power flow analysis

In previous papers, the parallelization and implementations of Gauss-Seidel (G-S) algorithms for power flow analysis have been investigated on a Sequent Balance shared memory (SM) machine. In this paper, the authors generalize the idea to more general computer architectures and demonstrate how to effectively increase the speed-up upper bounds of G-S algorithms by properly managing the bottlenecks on both Sequent Balance SM and nCUBE2 distributed memory (DM) machines. For G-S algorithms, when the coloring process is used to schedule the processors, there is almost no sequential portion. Thus, the only decisive factor left, which has a direct impact on the speed-up upper bound, is the synchronization overhead. Accordingly, the authors propose a new synchronization scheme which can reduce the synchronization overhead on the Sequent Balance machine. Also, on the nCUBE2 machine, a new clustered G-S algorithm is proposed and implemented. The algorithm carefully schedules their processors, computational loads and communication overheads for the best performance. In addition, the synchronization overheads and speed-up upper bounds on both machines are analyzed in terms of power system size and number of processors. The competitiveness of G-S type algorithms is also discussed