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

DOI10.1006/JPDC.1994.1095MaRDI QIDQ1344545zbMATH OpenOpenAlexFDO

Authors V. Pereyra

Publication date 6 August 1995

Published in Journal of Parallel and Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jpdc.1994.1095

zbMATH Keywords

coloring problemconvergenceGauss-Seidel algorithmheuristic methodload-balancing processor scheduling algorithmparallel computationpower flow analysis

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Iterative numerical methods for linear systems (65F10) Parallel numerical computation (65Y05)

Review text

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.

Recommendations

• Comments on scheduling parallel iterative methods on multiprocessor systems
• Comments on scheduling parallel iterative methods on multiprocessor systems. II
• A distributed memory parallel Gauss-seidel algorithm for linear algebraic systems
• A Set of New Mapping and Coloring Heuristics for Distributed-Memory Parallel Processors
• Scheduling parallel iterative methods on multiprocessor systems

Cited in

(2)

• Asymptotic Analysis of an Algorithm for Balanced Parallel Processor Scheduling
• Static Scheduling with Load Balancing for Solving Triangular Band Linear Systems on Multicore Processors

This page was built for publication: An efficient load-balancing processor scheduling algorithm for parallelization of Gauss-Seidel type algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1344545)