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

Метод двухуровневого распараллеливания прогонки для решения трехдиагональных линейных систем на гибридных ЭВМ с многоядерными сопроцессорами

Авторы

  • А.А. Федоров

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

системы линейных алгебраических уравнений
трехдиагональные матрицы
метод прогонки
распараллеливание прогонки
параллельно-конвейерный метод
метод Яненко
параллельные ЭВМ
Intel Xeon Phi

Аннотация

Приводится описание метода двухуровневого распараллеливания прогонки (на общей памяти средствами OpenMP и на распределенной памяти средствами MPI) для решения трехдиагональных линейных систем, возникающих при моделировании двумерных и трехмерных физических процессов. Анализируются особенности реализации метода как на ЭВМ с универсальными процессорами, так и на гибридных ЭВМ с многоядерными сопроцессорами Intel Xeon Phi. Оценивается арифметическая сложность реализованного метода. Обсуждаются результаты численных экспериментов по исследованию масштабируемости метода.

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

Загрузки

Опубликован

2016-06-14

Выпуск

Том 17 (2016): Выпуск 3.

Раздел

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

Автор

А.А. Федоров

Российский федеральный ядерный центр – Всероссийский научно-исследовательский институт экспериментальной физики
пр. Мира, 37, 607188, Саров
• младший научный сотрудник

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

  1. A. N. Bykov, V. A. Veselov, B. L. Voronin, and A. M. Erofeev, “RAMZES-KP Technique for Computation of Multicomponent Heat-Conducting Space Motions in Euler-Lagrange Coordinates,” in Proc. Russian Federal Nuclear Center (Russian Federal Nuclear Center, Sarov, 2008), Issue 13, pp. 50-57.
  2. J. Jeffers and J. Reinders, Intel Xeon Phi Coprocessor High-Performance Programming (Morgan Kaufmann, San Francisco, 2013).
  3. NVIDIA. Tesla GPU Accelerators for Servers.
    http://www.nvidia.ru/object/tesla-server-gpus-ru.html . Cited June 17, 2016.
  4. A. Davidson, Y. Zhang, and J. D. Owens, “An Auto-Tuned Method for Solving Large Tridiagonal Systems on the GPU,” in IPDPS’11 Proc. 2011 IEEE Int. Parallel & Distributed Processing Symp., Anchorage, USA, May 16-20, 2011 (IEEE Press, Washington, DC, 2011), pp. 956-965.
    http://idav.ucdavis.edu/func/return_pdf?pub_id=1052 . Cited June 17, 2016.
  5. H.-S. Kim, S. Wu, L.-W. Chang, and W.-M. Hwu, “A Scalable Tridiagonal Solver for GPUs,” in ICPP ’11 Proc. 2011 Int. Conf. on Parallel Processing, Taipei, Taiwan, September 13-16, 2011 (IEEE Press, Washington, DC, 2011), pp. 444-453.
  6. R. W. Hockney and C. R. Jesshope, Parallel Computers: Architecture, Programming, and Algorithm (Hilger, Bristol, 1988).
  7. A. A. Samarskii, Introduction to Numerical Methods (Nauka, Moscow, 1982) [in Russian].
  8. NVIDIA Corporation. NVIDIA CUDA Sparse Matrix Library (cuSPARSE).
    https://developer.nvidia.com/cusparse . Cited June 17, 2016.
  9. S. Sengupta, M. Harris, Y. Zhang, and J. D. Owens, “Scan Primitives for GPU Computing,”
    http://www.idav.ucdavis.edu/func/return_pdf?pub_id=915 . Cited June 17, 2016.
  10. D. Goddeke and R. Strzodka, “Cyclic Reduction Tridiagonal Solvers on GPUs Applied to Mixed-Precision Multigrid,” IEEE Trans. Parallel Distrib. Syst. 22 (1), 22-32 (2011).
  11. A. Davidson and J. D. Owens, “Register Packing for Cyclic Reduction: A Case Study,”
    http://idav.ucdavis.edu/func/return_pdf?pub_id=1053 . Cited June 17, 2016.
  12. D. Egloff, “High Performance Finite Difference PDE Solvers on GPUs,”
    http://www.gpucomputing.net/
    sites/default/files/papers/1380/fdm_gpu.pdf . Cited June 17, 2016.
  13. N. Sakharnykh, “Efficient Tridiagonal Solvers for ADI Methods and Fluid Simulation,”
    http://on-demand.gputechconf.com/gtc/2010/presentations/
    S12015-Tridiagonal-Solvers-ADI-Methods-Fluid-Simulation.pdf . Cited June 17, 2016.
  14. Y. Zhang, J. Cohen, and J. D. Owens, “Fast Tridiagonal Solvers on the GPU,” ACM SIGPLAN Notices 45 (5), 127-136 (2010).
  15. H. S. Stone, “An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations,” J. ACM 20 (1), 27-38 (1973).
  16. 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 SC’12 Proc. Int. Conf. on High Performance Computing, Networking, Storage and Analysis, Salt Lake City, USA, November 11-15, 2012 (IEEE Press, Los Alamitos, 2012), Article No. 27.
  17. E. Polizzi and A. H. Sameh, “A Parallel Hybrid Banded System Solver: The SPIKE Algorithm,” Parallel Comput. 32 (2), 177-194 (2006).
  18. E. Polizzi and A. Sameh, “SPIKE: A Parallel Environment for Solving Banded Linear Systems,” Comput. Fluids 36 (1), 113-120 (2007).
  19. I. E. Venetis, A. Sobczyk, A. Kouris, et al., “A General Tridiagonal Solver for Coprocessors: Adapting g-SPIKE for the Intel Xeon Phi,”
    http://www.researchgate.net/publication/282286515 . Cited June 17, 2016.
  20. N. N. Yanenko, A. N. Konovalov, A. N. Bugrov, and G. V. Shustov, “Organization of Parallel Computing and the Thomas Algorithm Parallelization,” in Numerical Methods in Continuum Mechanics (Comput. Center Sib. Branch of USSR Acad. Sci., Novosibirsk, 1978), Vol. 9, Issue 7, pp. 139-146.
  21. A. Povitsky, Parallelization of the Pipelined Thomas Algorithm , ICASE Report No. 98-48 (NASA Langley Research Center, Hampton, 1998).
  22. I. S. Sapronov and A. N. Bykov, “A Parallel-Pipelined Algorithm,” Atom, No. 4, 24-25 (2009).
  23. A. N. Bykov, A. M. Erofeev, E. A. Sizov, and A. A. Fedorov, “A parallel Sweep Method for Hybrid Supercomputers,” Vychisl. Metody Programm. 14, 43-47 (2013).
  24. S. A. Il’in and A. V. Starchenko, “Parallelization of a Componentwise Splitting for the Numerical Solution of the Heat Conduction Equation,” in Proc. Int. Conf. on Parallel Computational Technologies, Ekaterinburg, Russia, March 30-April 3, 2015 (Inst. of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg, 2015), pp. 399-402.
  25. V. M. Verzhbitskii, Numerical Linear Algebra (Direkt-Media, Moscow, 2013) [in Russian].
  26. Education Center.
    http://compcenter.org/predostavlenie-vychislitelnyh-resur . Cited June 17, 2016.
  27. Top-50.
    http://top50.supercomputers.ru/?page=archive&rating=23 . Cited June 17, 2016.
  28. G. I. Voronov, V. D. Trushchin, V. V. Shumilin, and D. V. Yezhov, “S-MPI Software System for the Development, Optimization and Execution of Parallel Applications on Supercomputer Clusters,” Voprosy Atomnoi Nauki i Tekhniki, Ser.: Mat. Mod. Fiz. Proc., No. 3, 55-60 (2013).