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

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

Авторы

  • Н.А. Ежова
  • Л.Б. Соколинский

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

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

Аннотация

Статья посвящена разработке методики исследования масштабируемости ресурсоемких итерационных алгоритмов, применяемых в моделировании сложных физических процессов на суперкомпьютерных системах. В основе предлагаемой методики лежит модель параллельных вычислений BSF (Bulk Synchronous Farm), позволяющая на ранней стадии разработки итерационного алгоритма определить границу его масштабируемости. Модель BSF предполагает представление алгоритма в виде операций над списками с использованием функций высшего порядка. При этом рассматривается два класса представлений: BSF-M (Map BSF) и BSF-MR (Map-Reduce BSF). Предлагаемая методика описывается на примере решения систем линейных алгебраических уравнений методом Якоби. Для метода Якоби строится два итерационных алгоритма: Jacobi-M на основе представления BSF-M и Jacobi-MR на основе представления BSF-MR. Для указанных алгоритмов с помощью стоимостных метрик модели BSF даются аналитические оценки для ускорения, эффективности распараллеливания и верхней границы масштабируемости для многопроцессорных вычислительных систем с распределенной памятью. Приводится информация о реализации этих алгоритмов на языке C++ с использованием программного шаблона BSF и библиотеки параллельного программирования MPI. Демонстрируются результаты масштабных вычислительных экспериментов, выполненных на кластерной вычислительной системе. На основе экспериментальных результатов дается анализ адекватности оценок, полученных аналитическим путем с помощью стоимостных метрик модели BSF.

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

Загрузки

Опубликован

2018-12-24

Выпуск

Том 19 (2018): Выпуск 4.

Раздел

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

Авторы

Н.А. Ежова

Южно-Уральский государственный университет,
Высшая школа электроники и компьютерных наук
просп. Ленина, 76, 454080, Челябинск
• преподаватель

Л.Б. Соколинский

Южно-Уральский государственный университет,
Высшая школа электроники и компьютерных наук
просп. Ленина, 76, 454080, Челябинск
• проректор по информатизации

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

  1. K. Borodulin et al., “Towards Digital Twins Cloud Platform,” in Proc. 10th Int. Conf. on Utility and Cloud Computing (ACM Press, New York, 2017), pp. 209-210.
  2. G. Bilardi and A. Pietracaprina, “Models of Computation, Theoretical,” in Encyclopedia of Parallel Computing (Springer, Boston, 2011), pp. 1150-1158.
  3. J. F. JaJa, “PRAM (Parallel Random AccessMachines),” in Encyclopedia of Parallel Computing (Sptinger, Boston, 2011), pp. 1608-1615.
  4. L. G. Valiant, “A Bridging Model for Parallel Computation,” Commun. ACM 33 (8), 103-111.
  5. D. Culler, R. Karp, D. Patterson, et al., “LogP: Towards a Realistic Model of Parallel Computation,” in Proc. 4th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, San Diego, USA, May 19-22, 1993 (ACM Press, New York, 1993),
    doi 10.1145/155332.155333
  6. M. Forsell and V. Lepp854nen, “An Extended PRAM-NUMA Model of Computation for TCF Programming,” in Proc. 2012 IEEE 26th International Parallel and Distributed Processing Symp. Workshops, Shanghai, China, May 21-25, 2012 (IEEE Press, Washington, DC, 2012), pp. 786-793.
  7. A. V. Gerbessiotis, “Extending the BSP Model for Multi-Core and Out-of-Core Computing: MBSP,” Parallel Comput. 41, 90-102 (2015).
  8. F. Lu , J. Song, and Y. Pang, “HLognGP: A Parallel Computation Model for GPU Clusters,” Concurr. Comp-Pract. E. 27 (17), 4880-4896 (2015).
  9. N. A. Ezhova and L. B. Sokolinsky, “Parallel Сomputational Model for Multiprocessor Systems with Distributed Memory,” Vestn. South Ural State Univ. Ser. Vychisl. Mat. Inf. 7 (2), 32-49 (2018).
  10. L. B. Sokolinsky, “Analytical Estimation of the Scalability of Iterative Numerical Algorithms on Distributed Memory Multiprocessors,” Lobachevskii J. Math. 39 {4), 571-575 (2018).
  11. L. M. Silva and R. Buyya, “Parallel Programming Models and Paradigms,” in High Performance Cluster Computing: Architectures and Systems (Prentice Hall, Upper Saddle River, 1999), Vol. 2, pp. 4-27.
  12. F. Darema, “SPMD Computational Model,” in Encyclopedia of Parallel Computing (Springer, Boston, 2011), pp. 1933-1943.
  13. S. Sahni and G. Vairaktarakis, “The Master-Slave Paradigm in Parallel Computer and Industrial Settings,” J. Global Optim. 9 (3-4}, 357-377 (1996).
  14. I. M. Sokolinskaya and L. B. Sokolinsky, “Scalability Evaluation of the NSLP Algorithm for Solving Non-Stationary Linear Programming Problems on Cluster Computing Systems,” in Proc. Int. Conf. on Russian Supercomputing Days, Moscow, Russia, September 25-26, 2017 (Mosk. Gos. Univ., Moscow, 2017), pp. 319-332.
  15. M. I. Cole, “Parallel Programming with List Homomorphisms,” Parallel Proc. Lett. 5 (2), 191-203 (1995).
  16. H. Rutishauser, “The Jacobi Method for Real Symmetric Matrices,” in Handbook for Automatic Computation. Vol 2. Linear Algebra (Springer, Heidelberg, 1971), pp. 202-211.
  17. C. G. J. Jacobi, “Ueber eine neue Auflösungsart der bei der Methode der kleinsten Quadrate vorkommenden line854ren Gleichungen,” Astronomische Nachrichten 22 (20), 297-306 (1845).
  18. H. H. Goldstine, F. J. Murray, and J. von Neumann, “The Jacobi Method for Real Symmetric Matrices,” J. ACM 6 (1), 59-96 (1959).
  19. X. I. A. Yang and R. Mittal, “Acceleration of the Jacobi Iterative Method by Factors Exceeding 100 Using Scheduled Relaxation,” J. Comput. Phys. 274, 695-708 (2014).
  20. J. E. Adsuara et al., “Scheduled Relaxation Jacobi Method: Improvements and Applications,” J. Comput. Phys. 321, 369-413 (2016).
  21. P. S. Kostenetskiy and A. Y. Safonov, “SUSU Supercomputer Resources,” in Proc. 10th Annual Int. Scientific Conf. on Parallel Computing Technologies (PCT 2016), Arkhangelsk, Russia, March 29-31, 2016 CEUR Workshop Proc. 1576, 561-573 (2016).