Load Balancing Optimizations for Distributed GMRES Algorithm

The Generalized Minimal Residual Method (GMRES) is one of the most important iterative algorithms for solving large-scale sparse linear systems, which are widely used in fields such as computational fluid dynamics and computational electromagnetics. As the scale of problems increases, multi-node distributed systems become one of the most popular running environments. Communication efficiency is usually the primary performance bottleneck for distributed GMRES. Traditional work reduces communication load mainly by balancing the computation load, while the balance of communication load is also important. This paper proposes a rule-based algorithm and a reinforcement learning (RL)-based algorithm to balance the communication load. By optimizing the partitioning of sparse matrices using the rule-based algorithm, the balance of both computation and communication loads among devices is improved. Experimental results show that the speedup can reach up to 1.34x. Moreover, RL-based algorithm improves the efficiency of the iterative algorithm by optimizing the task allocation of the partitioned sub-matrices. Experimental results present that the speedup can reach up to 1.30x.