Параллельное решение систем линейных уравнений на гибридной архитектуре CPU+GPU
Автор: Недожогин Никита Сергеевич, Копысов Сергей Петрович, Новиков Александр Константинович
Статья в выпуске: 2 т.9, 2020 года.
Бесплатный доступ
В статье рассматривается параллельная реализация решения систем линейных алгебраических уравнений на вычислительных узлах, содержащих центральный процессор (CPU) и графические ускорители (GPU). Производительность параллельных алгоритмов для классических схем метода сопряженных градиентов при совместном использовании CPU и GPU существенно ограничивается наличием точек синхронизации. В статье исследуется конвейерный вариант метода сопряженных градиентов с одной точкой синхронизации и возможностью распределения нагрузки между CPU и GPU при решении систем уравнений большой размерности. Численные эксперименты проведены на тестовых матрицах и вычислительных узлах разной производительности гетерогенного кластера, что позволило оценить вклад коммуникационных затрат. Алгоритмы реализованы при совместном использованием технологий MPI, OpenMP и CUDA. Предложенные алгоритмы, помимо сокращения времени выполнения, позволяют решать системы линейных уравнений и большего порядка, для которых не обеспечиваются необходимые ресурсы памяти одним GPU или вычислительным узлом. При этом, конвейерный блочный алгоритм сокращает общее время выполнения за счет уменьшения точек синхронизации и объединения коммуникаций в одно сообщение.
Параллельные вычисления, метод сопряженных градиентов, сокращение коммуникаций
Короткий адрес: https://sciup.org/147234271
IDR: 147234271 | УДК: 519.612, | DOI: 10.14529/cmse200203
Parallel solving of linear equations systems on hybrid architecture CPU+GPU
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.
Список литературы Параллельное решение систем линейных уравнений на гибридной архитектуре CPU+GPU
- Agullo Е., 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/sll227-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.
- Cornells 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. URL: http://jointlab.ncsa.illinois.edu/events/workshop3/pdf/presentations/Gropp-Update-on-Libraries.pdf (дата обращения: 07.11.2019).
- Кадыров И.Р., Копысов С.П., Новиков А.К. Разделение триангулированной многосвязной области на подобласти без ветвления внутренних границ // Ученые записки Казанского университета. Серия: Физико-математические науки. 2018. Т. 160. № 3. С. 544-560. DOI: 10.26907/2541-7746.
