Параллельный предобусловливатель на основе степенного разложения обратной матрицы для решения разреженных линейных систем на графических процессорах

  • А.В. Юлдашев Уфимский государственный авиационный технический университет https://orcid.org/0000-0003-1063-2725
  • Н.В. Репин Государственный научно-исследовательский институт авиационных систем
  • В.В. Спеле Уфимский государственный авиационный технический университет
Ключевые слова:

архитектура CUDA, графические процессоры, итерационные методы, параллельные вычисления, предобусловливатели, разреженные матрицы, трехдиагональные системы.

Аннотация

Рассмотрена применимость метода AIPS, аппроксимирующего обратную матрицу на основе степенного разложения в ряд Неймана, в рамках двухступенчатого предобусловливателя CPR. Предложен ориентированный на архитектуру CUDA параллельный алгоритм решения линейных систем с трехдиагональной матрицей, состоящей из независимых блоков различного размера. Показано, что реализация предложенного алгоритма может более чем в 2 раза превосходить по быстродействию функции решения трехдиагональных систем из библиотеки cuSPARSE. Проведено тестирование метода BiCGStab с предобусловливателем CPR-AIPS на современных GPU, в том числе на гибридной вычислительной системе с 4 GPU NVIDIA Tesla V100, показавшее приемлемую масштабируемость данного предобусловливателя, а также возможность ускорить решение линейных систем, характерных для задачи гидродинамического моделирования нефтегазовых месторождений, по сравнению с CPR-AMG.

Об авторах

А.В. Юлдашев,

Уфимский государственный авиационный технический университет,
общенаучный факультет
ул. Карла Маркса, 12, 450008, Уфа
• старший преподаватель

Н.В. Репин,
В.В. Спеле,

Уфимский государственный авиационный технический университет,
общенаучный факультет
ул. Карла Маркса, 12, 450008, Уфа
• инженер-исследователь

Литература

  1. Топ50. http://top50.supercomputers.ru.
  2. Азиз Х., Сеттари Э. Математическое моделирование пластовых систем. М.: Институт компьютерных исследований, 2004.
  3. Газизов И.И., Юлдашев А.В. Разработка параллельного линейного решателя для задачи гидродинамического моделирования нефтегазовых месторождений // Эвристические алгоритмы и распределенные вычисления. 2014. 1, № 1. 88-96.
  4. AlgoWiki: Открытая энциклопедия свойств алгоритмов. Стабилизированный метод бисопряженных градиентов (BiCGStab). http://algowiki-project.org/en/Biconjugate_gradient_stabilized_method_(BiCGStab).
  5. Саад Ю. Итерационные методы для разреженных линейных систем. М.: Изд-во Моск. ун-та, 2013.
  6. Губайдуллин Р.Р., Репин Н.В., Сайфутдинов Р.Ф., Юлдашев А.В. Специализированный решатель разреженных систем линейных алгебраических уравнений на вычислительных кластерах, оснащенных графическими процессорами // Суперкомпьютерные дни в России: труды международной конференции (26-27 сентября 2016 г., Москва). М.: Изд-во МГУ, 2016. 673-682.
  7. Wallis J.R., Kendall R.P., Little T.E. Constrained residual acceleration of conjugate residual methods // Proc. SPE Reservoir Simulation Symposium. 1985. https://doi.org/10.2118/13536-MS. SPE 1353. 1985. 415-428.
  8. Ruge J.W., Stuben K. Algebraic multigrid (AMG) // Multigrid Methods. Vol. 3. Philadelphia: SIAM Press, 1987. 73-130.
  9. Недожогин Н.С., Копысов С.П., Новиков А.К. Параллельное формирование предобуславливателя на основе обращения Шермана-Моррисона // Параллельные вычислительные технологии (ПаВТ2015): труды международной научной конференции (31 марта-2 апреля 2015 г., г. Екатеринбург). Челябинск: Издательский центр ЮУрГУ, 2015. 436-441.
  10. Chen K. Matrix preconditioning techniques and applications. Cambridge: Cambridge University Press, 2005.
  11. Prabhu H., Edfors O., Rodrigues J., Liu L., Rusek F. Hardware efficient approximative matrix inversion for linear pre-coding in massive MIMO // IEEE International Symposium on Circuits and Systems (ISCAS). 2014. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6865481
  12. Fung L.S.K., Dogru A.H. Parallel unstructured solver methods for complex giant reservoir simulation // Proceedings of the SPE Reservoir Simulation Symposium. 2007. https://doi.org/10.2118/106237-MS.
  13. Боресков А.В., Харламов А.А., Марковский Н.Д. и др. Параллельные вычисления на GPU. Архитектура и программная модель CUDA. М.: Изд-во Моск. ун-та, 2012.
  14. AlgoWiki: Открытая энциклопедия свойств алгоритмов. Прогонка, точечный вариант. http://algowiki-project.org/ru/Прогонка,_точечный_вариант.
  15. Фролов А.В. Еще один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., Москва). М.: Изд-во МГУ, 2015. 151-162.
  16. cuSPARSE. https://docs.nvidia.com/cuda/cusparse/.
  17. Chang L.-W., Stratton J.A., Kim H.-S., Hwu W.-M.W. A scalable, numerically stable, high-performance tridiagonal solver using GPUs // The International Conference for High Performance Computing, Networking, Storage and Analysis. Los Alamitos: IEEE Press, 2012. doi 10.1109/SC.2012.12
  18. Хокни Р., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. М.: Радио и связь, 1986.
  19. Laszlo E., Giles M., Appleyard J. Manycore algorithms for batch scalar and block tridiagonal solvers // ACM Trans. Math. Softw. 2016. Vol. 42, N 4. doi 10.1145/2830568
  20. AlgoWiki: Открытая энциклопедия свойств алгоритмов. Классическая монотонная прогонка, повторный вариант. 2019. http://algowiki-project.org/ru/Классическая_монотонная_прогонка,_повторный_вариант.
  21. Суперкомпьютер УГАТУ. http://www.ugatu.su/supercomputer/.
  22. Вержбицкий В.М. Вычислительная линейная алгебра. М.: Директ-Медиа, 2013.
Опубликован
2020-01-11
Как цитировать
Юлдашев А.В., Репин Н.В., Спеле В.В. Параллельный предобусловливатель на основе степенного разложения обратной матрицы для решения разреженных линейных систем на графических процессорах // Вычислительные методы и программирование. 2020. 20. 444-456. doi 10.26089/NumMet.v20r439
Раздел 1. Вычислительные методы и приложения