A parallel iterative linear system solver with dynamic load balancing

Abstract

This paper describes the design and implementation of a parallel iterative linear system solver for distributed memory multicomputers and workstation clusters. It is capable of applying heterogeneous data distribution and dynamic load balancing within an iterative solver routine at matrix level. Matrices as well as vectors are distributed heterogeneously according to the available performances of the processors, and redistributions are carried out at run time if the load of the processors changes. We present the concepts behind the chosen matrix data structures and load measurements, and discuss our dynamic load balancing algorithm. The results show the suitability of our approach.