Одержано 20.10.2025; Виправлено 11.11.2025; Прийнято 18.11.2025

Надруковано 08.12.2025; Вперше Online 15.12.2025

https://doi.org/10.34229/2707-451X.25.4.6

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.6

Multi-GPU двовимірний блочно-циклічний алгоритм LU-факторизації щільних матриць

О.М. Хіміч ,   В.А. Сидорук ^* ,   А.В. Павлюк

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

^* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Представлено ефективний паралельний алгоритм для LU-факторизації великих щільних матриць на основі двовимірного блочно-циклічного розподілу даних, розроблений для обчислювальних систем з декількома графічними процесорами. Запропонована методологія вирішує ключові проблеми великомасштабних обчислень лінійної алгебри, включаючи балансування навантаження, мінімізацію накладних витрат на комунікацію та максимізацію обчислювальної локальності. Завдяки циклічному розподілу блоків матриць по сітці графічних процесорів алгоритм забезпечує рівномірний розподіл навантаження навіть для дуже великих розмірів задач, тим самим уникаючи простоїв і скорочуючи затримки синхронізації.

Реалізація використовує найсучасніші технології обчислень на GPU, включаючи потоки CUDA, бібліотеки cuBLAS і cuSolver для локальних обчислювальних ядер, а також NCCL для високопродуктивних колективних комунікацій з використанням міжмережевих з'єднань NVLink. Стратегія планування на випередження та перекриття комунікацій з обчисленнями ще більше підвищує ступінь паралелізму, забезпечуючи стабільно високе використання ресурсів GPU у всьому процесі факторизації.

Для аналізу прискорення, масштабованості, витрат на комунікацію та впливу розміру блоку на загальний час виконання розроблено детальну теоретичну модель продуктивності. Чисельні експерименти, проведені на вузлі з 8 NVIDIA RTX 2080 Ti, демонструють високу масштабованість, досягаючи до 95 % ефективності паралельної обробки для матриць розміром до N = 20 000. Результати підтверджують, що запропонований підхід до LU-факторизації з використанням декількох GPU наближається до теоретичних меж продуктивності та значно перевершує традиційні схеми на базі CPU та гібридні схеми на базі CPU+GPU.

Цей метод дуже добре підходить для великомасштабних наукових і інженерних застосувань, що вимагають швидкого і надійного вирішення лінійних систем, включаючи обчислювальну гідродинаміку, механіку конструкцій, чисельне моделювання фізичних процесів і робочі навантаження машинного навчання. Майбутні напрямки досліджень включають розширення на розріджені матриці з адаптивним балансуванням навантаження, прискорення зі змішаною точністю з корекцією помилок і узагальнення на інші факторизації матриць, такі як Cholesky, QR і LDLᵀ.

 

Ключові слова: LU факторизація, мульти-GPU система, блочно-циклічний розподіл даних, паралельні обчислення, CUDA, cuBLAS, cuSolver, NCCL.

 

Цитувати так: Хіміч О.М., Сидорук В.А., Павлюк А.В. Multi-GPU двовимірний блочно-циклічний алгоритм LU-факторизації щільних матриць. Cybernetics and Computer Technologies. 2025. 4. С. 55–64. https://doi.org/10.34229/2707-451X.25.4.6

 

Список літератури

           1.     Dongarra J., Whaley R.C., Petitet A. A ScaLAPACK User’s Guide: Solving Linear Algebra Problems on Distributed Memory Computers. 1998. SIAM, Philadelphia. https://www.netlib.org/scalapack/slug/scalapack_slug.html

           2.     Химич А.Н., Молчанов И.Н, Мова В.И. и др. Численное программное обеспечение MIMD-компьютера Инпарком. Киев: Наук. думка, 2007. 222 с.

           3.     Химич А.Н., Молчанов И.Н., Попов А.В., Чистякова Т.В., Яковлев М.Ф. Параллельные алгоритмы решения задач вычислительной математики. Киев: Наук. думка, 2008. 247 с.

           4.     Volkov V., Demmel J. LU, QR and Cholesky Factorizations Using Vector Capabilities of GPUs. University of California, Berkeley, 2008. https://www.netlib.org/lapack/lawnspdf/lawn202.pdf

           5.     Dongarra J., Tomov S., Haidar A. MAGMA: Matrix Algebra on GPU and Multicore Architectures. Innovative Computing Laboratory, University of Tennessee. 2012.

           6.     Хіміч О.М., Полянко В.В., Чистякова Т.В. Паралельні алгоритми розв’язування лінійних систем на гібридних комп’ютерах. Cybernetics and Computer Technologies. 2020. № 2. С. 3–66. https://doi.org/10.34229/2707-451X.20.2.6

           7.     Khimich O.M., Popov O.V., Chistyakov, O.V. et al. A Parallel Algorithm for Solving a Partial Eigenvalue Problem for Block-Diagonal Bordered Matrices. Cybern Syst Anal. 2020. Vol. 56. P. 913–923. https://doi.org/10.1007/s10559-020-00311-z

           8.     Baranov A.Y., Popov A.V., Slobodyan Y.E., Khimich A.N. Mathematical modeling of building con-structions using hybrid computing systems. Journal of Automation and Information Sciences. 2017. Vol. 49, Iss. 7. P. 18–32. https://doi.org/10.1615/JAutomatInfScien.v49.i7.20

           9.     Haidar A., Tomov S., Dongarra J. Towards Batched Dense Linear Algebra Routines on GPUs: Reduction and Factorization. Concurrency and Computation: Practice and Experience. 2019. 31 (6), e4965.

       10.     NVIDIA Corporation. CuSolver and cuBLAS Libraries Documentation. NVIDIA Developer Portal. 2023.

       11.     Михалевич В.С., Бик Н.А., Брусникин Б.Н., Химич А.Н. и др. Численные методы для многопроцессорного вычислительного комплекса ЕС. Под редакцией И.Н. Молчанова. М.: Издание ВВИА им. проф. Н.Е. Жуковского, 1986. 401 с.

       12.     NVIDIA Corporation. NCCL 2.15: Multi-GPU Collective Communication Library. NVIDIA Developer Documentation. 2022.

       13.     Обчислювальний комплекс СКІТ ІК НАН України. http://icybcluster.org.ua/index.php?lang_id=2&menu_id=5 (звернення: 20.10.2025)

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна