Domain Decomposition Preconditioners for Communication-Avoiding Krylov Methods on a Hybrid CPU/GPU Cluster
Authors:
- Ichitaro YamazakiIYIchitaro Yamazaki
- Sivasankaran RajamanickamSRSivasankaran Rajamanickam
- Erik G. BomanEBErik G. Boman
- Mark HoemmenMHMark Hoemmen
- Michael A. HerouxMHMichael A. Heroux
- Stanimire TomovSTStanimire Tomov
- 1 November 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21674329,p. 933-944
Abstract
Krylov subspace projection methods are widely used iterative methods for solving large-scale linear systems of equations. Researchers have demonstrated that communication avoiding (CA) techniques can improve Krylov methods' performance on modern computers, where communication is becoming increasingly expensive compared to arithmetic operations. In this paper, we extend these studies by two major contributions. First, we present our implementation of a CA variant of the Generalized Minimum Residual (GMRES) method, called CAGMRES, for solving no symmetric linear systems of equations on a hybrid CPU/GPU cluster. Our performance results on up to 120 GPUs show that CA-GMRES gives a speedup of up to 2.5x in total solution time over standard GMRES on a hybrid cluster with twelve Intel Xeon CPUs and three Nvidia Fermi GPUs on each node. We then outline a domain decomposition framework to introduce a family of preconditioners that are suitable for CA Krylov methods. Our preconditioners do not incur any additional communication and allow the easy reuse of existing algorithms and software for the sub domain solves. Experimental results on the hybrid CPU/GPU cluster demonstrate that CA-GMRES with preconditioning achieve a speedup of up to 7.4x over CAGMRES without preconditioning, and speedup of up to 1.7x over GMRES with preconditioning in total solution time. These results confirm the potential of our framework to develop a practical and effective preconditioned CA Krylov method.Keywords
This publication has 11 references indexed in Scilit:
- Communication lower bounds and optimal algorithms for numerical linear algebraActa Numerica, 2014
- Improving the Performance of CA-GMRES on Multicores with Multiple GPUs2014
- Minimizing communication in sparse matrix solvers2009
- A Block Orthogonalization Procedure with Constant Synchronization RequirementsSIAM Journal on Scientific Computing, 2002
- A Restricted Additive Schwarz Preconditioner for General Sparse Linear SystemsSIAM Journal on Scientific Computing, 1999
- A Newton basis GMRES implementationIMA Journal of Numerical Analysis, 1994
- On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchyParallel Computing, 1989
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear SystemsSIAM Journal on Scientific and Statistical Computing, 1986
- Practical Use of Polynomial Preconditionings for the Conjugate Gradient MethodSIAM Journal on Scientific and Statistical Computing, 1985
- Reducing the bandwidth of sparse symmetric matrices1969