DOI: https://doi.org/10.26089/NumMet.v20r439

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

Авторы

  • А.В. Юлдашев
  • Н.В. Репин
  • В.В. Спеле

Ключевые слова:

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

Аннотация

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

Новые вычислительные технологии

Загрузки

Опубликован

2020-01-11

Выпуск

Том 20 (2019): Выпуск 4.

Раздел

Раздел 1. Вычислительные методы и приложения

Авторы

А.В. Юлдашев

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

Н.В. Репин

Государственный научно-исследовательский институт авиационных систем
ул. Викторенко, 7, 125319, г. Москва
• инженер

В.В. Спеле

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

Библиографические ссылки

  1. Топ50.
    http://top50.supercomputers.ru . Cited October 25, 2019.
  2. K. Aziz and A. Settari, Petroleum Reservoir Simulation (Appl. Sci. Publ., London, 1979; Comput. Sci. Inst., Moscow, 2004).
  3. I. I. Gazizov and A. V. Yuldashev, “Development of Parallel Linear Solver for Hydrodynamic Modeling of Oil and Gas Fields,” Evristich. Algortmy i Raspredel. Vychisl. 1 (1), 88-96 (2014).
  4. AlgoWiki: Open Encyclopedia of Parallel Algorithmic Features. Biconjugate gradient stabilized method (BiCGStab).
    |
    http://algowiki-project.org/en/Biconjugate_gradient_stabilized_method_(BiCGStab)|. Cited October 15, 2019.
  5. Y. Saad, Iterative Methods for Sparse Linear Systems (SIAM, Philadelphia, 2003; Mosk. Gos. Univ., Moscow, 2013).
  6. R. R. Gubaidullin, N. V. Repin, R. F. Sayfutdinov, and A. V. Yuldashev, “Specialized Solver of Sparse Linear Systems of Algebraic Equations on GPU Clusters,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 26-27, 2016 (Mosk. Gos. Univ., Moscow, 2016), pp. 673-682.
  7. J. R. Wallis, R. P. Kendall, and T. E. Little, “Constrained Residual Acceleration of Conjugate Residual Methods,” in Proc. SPE Reservoir Simulation Symposium, Dallas, USA, February 10-13, 1985 ,
    doi 10.2118/13536-MS
  8. J. W. Ruge and K. Stüben, “Algebraic Multigrid (AMG),” in Multigrid Methods (SIAM Press, Philadelphia, 1987), Vol. 3, pp. 73-130.
  9. N. S. Nedozhogin, S. P. Kopysov, and A. K. Novikov., “Parallel Formation of a Preconditioner Based on the Sherman-Morrison Inversion,” in Proc. Int. Conf. on Parallel Computing Technologies, Ekaterinburg, Russia, March 31-April 2, 2015 (South Ural State Univ., Chelyabinsk, 2015), pp. 436-441.
  10. K. Chen, Matrix Preconditioning Techniques and Applications (Cambridge Univ. Press, Cambridge, 2005).
  11. H. Prabhu, O. Edfors, J. Rodrigues, et al., “Hardware Efficient Approximative Matrix Inversion for Linear Pre-coding in Massive MIMO,” in IEEE Int. Symp. on Circuits and Systems (ISCAS), Melbourne, Australia, June 1-5, 2014
    |
    https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6865481|
  12. L. S. K. Fung and A. H. Dogru, “Parallel Unstructured Solver Methods for Complex Giant Reservoir Simulation,” in Proc. SPE Reservoir Simulation Symposium, Houston USA, February 26-28, 2007 ,
    doi 10.2118/106237-MS
  13. A. V. Boreskov, A. A. Charlamov, N. D. Markovskii, et al., Parallel Computing on GPU. Architecture and CUDA Programming Model (Mosk. Gos. Univ., Moscow, 2012) [in Russian].
  14. AlgoWiki: Open Encyclopedia of Parallel Algorithmic Features. Thomas Algorithm, Pointwise Version.
    |
    http://algowiki-project.org/en/Thomas_algorithm, _pointwise_version.| Cited October 15, 2019.
  15. A. V. Frolov, “Yet Another Tridiagonal Matrix Algorithm Parallelizing Method,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 28-29, 2015 (Mosk. Gos. Univ., Moscow, 2015), pp. 151-162.
  16. cuSPARSE. The API Reference Guide for cuSPARSE, the CUDA Sparse Matrix Library.
    https://docs.nvidia.com/cuda/cusparse/. Cited October 25, 2019.
  17. L.-W. Chang, J. A. Stratton, H.-S. Kim, and W.-M. W. Hwu, “A Scalable, Numerically Stable, High-Performance Tridiagonal Solver Using GPUs,” in Proc. Int. Conf. on High Performance Computing, Networking, Storage and Analysis, Salt Lake City, November 10-16, 2012 (IEEE Press, Los Alamitos, 2012),
    doi 10.1109/SC.2012.12
  18. R. W. Hockney and C. R. Jesshope, Parallel Computers: Architecture, Programming and Algorithms (Adam Hilger, Bristol 1981; Radio i Svyaz’, Moscow, 1986).
  19. E. László, M. Giles, and J. Appleyard, “Manycore Algorithms for Batch Scalar and Block Tridiagonal Solvers,” ACM Trans. Math. Softw. 42 (2016).
    doi 10.1145/2830568
  20. AlgoWiki: Open Encyclopedia of Parallel Algorithmic Features. Repeated Thomas Algorithm, Pointwise Version.
    |
    http://algowiki-project.org/en/Repeated_Thomas_algorithm, _pointwise_version|. Cited October 15, 2019.
  21. USATU’s Supercomputer.
    https://www.ugatu.su/en/research/supercomputer/. Cited October 15, 2019.
  22. V. M. Verzhbitskii, Numerical Linear Algebra (Direkt-Media, Moscow, 2013) [in Russian].