Mixed-Precision Orthogonalization Scheme and Adaptive Step Size for Improving the Stability and Performance of CA-GMRES on GPUs

The Generalized Minimum Residual (GMRES) method is a popular Krylov subspace projection method for solving a nonsymmetric linear system of equations. On modern computers, communication is becoming increasingly expensive compared to arithmetic operations, and a communication-avoiding variant (CA-GMRES) may improve the performance of GMRES. To further enhance the performance of CA-GMRES, in this paper, we propose two techniques, focusing on the two main computational kernels of CA-GMRES, tall-skinny QR (TSQR) and matrix powers kernel (MPK). First, to improve the numerical stability of TSQR based on the Cholesky QR (CholQR) factorization, we use higher-precision arithmetic at carefully-selected steps of the factorization. In particular, our mixed-precision CholQR takes the input matrix in the standard \(64\)-bit double precision, but accumulates some of its intermediate results in a software-emulated double-double precision. Compared with the standard CholQR, this mixed-precision CholQR requires about \(8.5\times \) more computation but a much smaller increase in communication. Since the computation is becoming less expensive compared to the communication on a newer computer, the relative overhead of the mixed-precision CholQR is decreasing. Our case studies on a GPU demonstrate that using higher-precision arithmetic for this small but critical segment of the algorithm can improve not only the overall numerical stability of CA-GMRES but also, in some cases, its performance. We then study an adaptive scheme to dynamically adjust the step size of MPK based on the static inputs and the performance measurements gathered during the first restart loop of CA-GMRES. Since the optimal step size of MPK is often much smaller than that of the orthogonalization kernel, the overall performance of CA-GMRES can be improved using different step sizes for these two kernels. Our performance results on multiple GPUs show that our adaptive scheme can choose a near optimal step size for MPK, reducing the total solution time of CA-GMRES.

1. 1.

   In the current implementation, the numbers of rows and columns in \(X\) and \(Y\) are a multiple of \(h\), and multiples of \(m_b\) and \(n_b\), respectively, where \(n_b\) is a multiple of \(n_r\).

2. 2.

   http://mplapack.sourceforge.net.

3. 3.

   http://www.cise.ufl.edu/research/sparse/matrices/.

4. 4.

   http://www.eecs.berkeley.edu/~hdnguyen/rblas.

5. 5.

   http://crd.lbl.gov/groups-depts/ftg/projects/current-projects/corvette/precimonious.

This material is based upon work supported by the U.S. Department of Energy (DOE), Office of Science, Office of Advanced Scientific Computing Research (ASCR), and was founded in part by National Science Foundation under Grant No. ACI-1339822, DOE Grant #DE-SC0010042: “Extreme-scale Algorithms & Solver Resilience (EASIR),” Russian Scientific Fund, Agreement N14-11-00190, and NVIDIA. This research used resources of the Keeneland Computing Facility at the Georgia Institute of Technology, which is supported by the National Science Foundation under Contract OCI-0910735. We thank Maho Nakata, Daichi Mukunoki, and the members of the DOE EASIR project for helpful discussions.

Authors and Affiliations

1. Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, USA

   Ichitaro Yamazaki, Stanimire Tomov, Tingxing Dong & Jack Dongarra

Corresponding author

Correspondence to Ichitaro Yamazaki .

Editors and Affiliations

1. IRIT, ENSEEIHT, Toulouse Cedex, France

   Michel Daydé

2. Lawrence Berkeley National Laboratory, Berkeley, California, USA

   Osni Marques

3. Information Technology Center, The University of Tokyo, Tokyo, Japan

   Kengo Nakajima

Reprints and permissions

© 2015 Springer International Publishing Switzerland

Policies and ethics