Abstract
In this study, we present an efficient thread-adaptive sparse approximate inverse preconditioning algorithm on GPU, called GSPAI-Adaptive. For GSPAI-Adaptive, there are three novelties: (1) a thread-adaptive allocation strategy is presented for each column of the preconditioner, (2) a parallel framework of constructing the sparse approximate inverse preconditioner is proposed on GPU, (3) each component of the preconditioner is computed in parallel inside a thread group of GPU. Experimental results show that GSPAI-Adaptive is effective, and is advantageous over the popular preconditioning algorithms in two public libraries, and a latest parallel sparse approximate inverse preconditioning algorithm.
The research has been supported by the Natural Science Foundation of China under grant number 61872422, and the Natural Science Foundation of Zhejiang Province, China under grant number LY19F020028, and the Natural Science Foundation of Jiangsu Province, China under grant number BK20171480.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7, 856–869 (1986)
Van der Vorst, H.A.: Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems. SIAM J. Stat. Comput. 13(2), 631 (1992)
Kolotilina, L.Y., Yeremin, A.Y.: Factorized sparse approximate inverse preconditionings I: theory. Soc. Ind. Appl. Math. 14, 45–58 (1993)
Benzi, M., Meyer, C.D., Tuma, M.: A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput. 17, 1135–1149 (1996)
Grote, M.J., Huckle, T.: Parallel preconditioning with sparse approximate inverses. Soc. Ind. Appl. Math. 18, 838–853 (1997)
Chow, E.: A priori sparsity patterns for parallel sparse approximate inverse preconditioners. SIAM J. Sci. Comput. 21(5), 1804–1822 (2000)
Li, K., Yang, W., Li, K.: A hybrid parallel solving algorithm on GPU for quasi-tridiagonal system of linear equations. IEEE Trans. Parallel Distrib. Syst. 27(10), 2795–2808 (2016)
Gao, J., Zhou, Y., He, G., Xia, Y.: A multi-GPU parallel optimization model for the preconditioned conjugate gradient algorithm. Parallel Comput. 63, 1–16 (2017)
He, G., Gao, J., Wang, J.: Efficient dense matrix-vector multiplication on GPU. Concurr. Comput.: Pract. Exp. 30(19), e4705 (2018)
Gao, J., Wu, K., Wang, Y., Qi, P., He, G.: GPU-accelerated preconditioned GMRES method for two-dimensional Maxwell’s equations. Int. J. Comput. Math. 94(10), 2122–2144 (2017)
Lukash, M., Rupp, K., Selberherr, S.: Sparse approximate inverse preconditioners for iterative solvers on GPUs. In: Proceedings of the 2012 Symposium on High Performance Computing, pp. 1–8. Society for Computer Simulation International (2012)
Dehnavi, M.M., Fernandez, D.M., Gaudiot, J.L., Giannacopoulos, D.D.: Parallel sparse approximate inverse preconditioning on graphic processing units. IEEE Trans. Parallel Distrib. Syst. 24(9), 1852–1862 (2012)
He, G., Yin, R., Gao, J.: An efficient sparse approximate inverse preconditioning algorithm on GPU. Concurr. Comput.: Pract. Exp. 32(7), e5598 (2020)
Cusparse library, v10.1. https://docs.nvidia.com/cuda/cusparse/index.html
Rupp, K., et al.: ViennaCL–linear algebra library for multi-and many-core architectures. SIAM J. Sci. Comput. 38(5), S412–S439 (2016)
Davis, T.A., Hu, Y.: The university of Florida sparse matrix collection. ACM Trans. Math. Softw. (TOMS) 38(1), 1–25 (2011)
CUDA C programming guide, v10.1. https://docs.nvidia.com/cuda/cuda-c- programming-guide
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Chen, Q., Gao, J., Chu, X., He, G. (2021). Parallel Sorted Sparse Approximate Inverse Preconditioning Algorithm on GPU. In: Wolf, F., Gao, W. (eds) Benchmarking, Measuring, and Optimizing. Bench 2020. Lecture Notes in Computer Science(), vol 12614. Springer, Cham. https://doi.org/10.1007/978-3-030-71058-3_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-71058-3_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-71057-6
Online ISBN: 978-3-030-71058-3
eBook Packages: Computer ScienceComputer Science (R0)