Параллельное решение систем линейных уравнений на гибридной архитектуре CPU+GPU
DOI:
https://doi.org/10.14529/cmse200203Ключевые слова:
параллельные вычисления, метод сопряженных градиентов, сокращение коммуникацийАннотация
В статье рассматривается параллельная реализация решения систем линейных алгебраических уравнений на вычислительных узлах, содержащих центральный процессор (CPU) и графические ускорители (GPU). Производительность параллельных алгоритмов для классических схем метода сопряженных градиентов при совместном использовании CPU и GPU существенно ограничивается наличием точек синхронизации. В статье исследуется конвейерный вариант метода сопряженных градиентов с одной точкой синхронизации и возможностью распределения нагрузки между CPU и GPU при решении систем уравнений большой размерности. Численные эксперименты проведены на тестовых матрицах и вычислительных узлах разной производительности гетерогенного кластера, что позволило оценить вклад коммуникационных затрат. Алгоритмы реализованы при совместном использованием технологий MPI, OpenMP и CUDA. Предложенные алгоритмы, помимо сокращения времени выполнения, позволяют решать системы линейных уравнений и большего порядка, для которых не обеспечиваются необходимые ресурсы памяти одним GPU или вычислительным узлом. При этом, конвейерный блочный алгоритм сокращает общее время выполнения за счет уменьшения точек синхронизации и объединения коммуникаций в одно сообщение.
Библиографические ссылки
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.
