The Communication-Hiding Conjugate Gradient Method with Deep Pipelines

Abstract

Krylov subspace methods are among the most efficient solvers for large scale linear algebra problems. Nevertheless, classic Krylov subspace algorithms do not scale well on massively parallel hardware due to synchronization bottlenecks. Communication-hiding pipelined Krylov subspace methods offer increased parallel scalability by overlapping the time-consuming global communication phase with computations such as spmvs, hence reducing the impact of the global synchronization and avoiding processor idling. One of the first published methods in this class is the pipelined Conjugate Gradient method (p-CG). However, on large numbers of processors the communication phase may take much longer than the computation of a single spmv. This work extends the pipelined CG method to deeper pipelines, denoted as p(l)-CG, which allows further scaling when the global communication phase is the dominant time-consuming factor. By overlapping the global all-to-all reduction phase in each CG iteration with the next l spmvs (deep pipelining), the method hides communication latency behind additional computational work. The p(l)-CG algorithm is derived from similar principles as the existing p(l)-GMRES method and by exploiting operator symmetry. The p(l)-CG method is also compared to other Krylov subspace methods, including the closely related classic CG and D-Lanczos methods and the pipelined CG method by Ghysels et al.. By analyzing the maximal accuracy attainable by the p(l)-CG method it is shown that the pipelining technique induces a trade-off between performance and numerical stability. A preconditioned version of the algorithm is also proposed and storage requirements and performance estimates are discussed. Experimental results demonstrate the possible performance gains and the attainable accuracy of deeper pipelined CG for solving large scale symmetric linear systems.

34 pages (incl. 6 pages appendix), 12 figures, 2 tables, 5 algorithms

Cited by in corpus (9)

• Predict-and-recompute conjugate gradient variants
• Scalable Resilience Against Node Failures for Communication-Hiding Preconditioned Conjugate Gradient and Conjugate Residual Methods
• Improving strong scaling of the Conjugate Gradient method for solving large linear systems using global reduction pipelining
• Numerical analysis of the maximal attainable accuracy in communication hiding pipelined Conjugate Gradient methods
• Parallel Multiphysics Simulation for the Stabilized Optimal Transportation Meshfree (OTM)
• Hardware-Oriented Krylov Methods for High-Performance Computing
• White Paper from Workshop on Large-scale Parallel Numerical Computing Technology (LSPANC 2020): HPC and Computer Arithmetic toward Minimal-Precision Computing
• Numerically Stable Recurrence Relations for the Communication Hiding Pipelined Conjugate Gradient Method
• Analyzing and improving maximal attainable accuracy in the communication hiding pipelined BiCGStab method