Parallel Solving of Linear Equations Systems on Hybrid Architecture CPU+GPU
DOI:
https://doi.org/10.14529/cmse200203Keywords:
parallel calculations, the method of conjugate gradients, reduction of communicationsAbstract
The article discusses the parallel implementation of solving systems of linear algebraic equations on computational nodes containing a central processing unit (CPU) and graphic accelerators (GPU). The performance of parallel algorithms for the classical conjugate gradient method schemes when using the CPU and GPU together is significantly limited by the synchronization points. The article investigates the pipeline version of the conjugate gradient method with one synchronization point, the possibility of asynchronous calculations, load balancing between the CPU and GPU when solving the large linear systems. Numerical experiments were carried out on test matrices and computational nodes of different performance of a heterogeneous cluster, which allowed us to estimate the contribution of communication costs. The algorithms are implemented with the joint use of technologies: MPI, OpenMP and CUDA. The proposed algorithms, in addition to reducing the execution time, allow solving large linear systems, for which there are not enough memory resources of one GPU or a computing node. At the same time, block algorithm with the pipelining decreases the total execution time by reducing synchronization points and aggregating some messages in one.
References
Agullo E., Giraud L., Guermouche A., Roman J. Parallel hierarchical hybrid linear solvers for emerging computing platforms. Comptes Rendus Mecanique. 2011. Vol. 333. P. 96–103. DOI: 10.1016/j.crme.2010.11.005.
Gaidamour J., Henon P. A parallel direct/iterative solver based on a Schur complement approach. 11th IEEE International Conference on Computational Science and Engineering (San Paulo, Brazil, July, 16–18, 2008). IEEE. 2008. P. 98–105. DOI: 10.1109/CSE.2008.36.
Giraud L., Haidar A., Saad Y. Sparse approximations of the Schur complement for parallel algebraic hybrid solvers in 3D. Numerical Mathematics. 2010. Vol. 3, no. 3. P. 276–294. DOI: 10.4208/nmtma.2010.33.2.
Rajamanickam S., Boman E.G., Heroux M.A. ShyLU: A Hybrid-Hybrid Solver for Multicore Platforms. IEEE 26th International Parallel and Distributed Processing Symposium (Shanghai, China, May, 21–25, 2012). 2012. P. 631–643. DOI: 10.1109/IPDPS.2012.64.
Yamazaki I., Rajamanickam S., Boman E., Hoemmen M., Heroux M., Tomov S. Domain decomposition preconditioners for communication-avoiding Krylov methods on a hybrid CPU/GPU cluster. Proceedings of International Conference for High Performance Computing, Networking, Storage and Analysis (SC14). 2014. P. 933–944. DOI: 10.1109/SC.2014.81.
Kopysov S., Kuzmin I., Nedozhogin N., Novikov A., Sagdeeva Y. Scalable hybrid implementation of the Schur complement method for multi-GPU systems. The Journal of Supercomputing. 2014. Vol. 69. P. 81–88. DOI: 10.1007/s11227-014-1209-7.
Hestenes M.R., Stiefel E. Methods of Conjugate Gradients for Solving Linear Systems. Journal of Research of the National Bureau of Standards. 1952. Vol. 49. P. 409—436. DOI: 10.6028/jres.049.044.
Cornelis J., Cools S., Vanroose W. The Communication-Hiding Conjugate Gradient Method with Deep Pipelines. CoRR abs/1801.04728. 2018. https://arxiv.org/abs/1801.04728.
D’Azevedo E.F., Romine C.H. Reducing communcation costs in the conjugate gradient algorithm on distributed memory multiprocessors. Technical Report ORNL/TM-12192, Oak Ridge National Lab, 1992. DOI: 10.2172/10176473.
Wilkinson J.H., Reinsch C. Linear Algebra. Springer, Berlin, Heidelberg, 1971. 441 p. DOI: 10.1007/978-3-662-39778-7
Chronopoulos A.T., Gear C.W. s-step iterative methods for symmetric linear systems. Journal of Computational and Applied Mathematics. 1989. Vol. 25, no. 2. P. 153–168. DOI: 10.1016/0377-0427(89)90045-9.
Ghysels P., Vanroose W. Hiding global synchronization latency in the preconditioned Conjugate Gradient algorithm. Parallel Computing. 2014. Vol. 40, no. 7. P. 224–238. DOI: 10.1016/j.parco.2013.06.001.
Gropp W. Update on libraries for blue waters. Bordeaux. France. 2010. Available at: http://jointlab.ncsa.illinois.edu/events/workshop3/pdf/presentations/Gropp-Update-on-Libraries.pdf (accessed: 07.11.2019).
Kadyrov I.R., Kopysov S.P., Novikov А.К. Partitioning of triangulated multiply connected domain into subdomains without branching of inner boundaries. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki. 2018. Vol. 160, no. 3. P. 544–560. (in Russian) DOI: 10.26907/2541-7746.
