Scalability evaluation of iterative algorithms for supercomputer simulation of physical processes

Authors

DOI:

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

Keywords:

iterative algorithm, BSF parallel computation model, scalability estimation, speedup, parallel efficiency, Jacobi method, cluster computing systems

Abstract

This paper is devoted to the development of a methodology for evaluating the scalability of compute-intensive iterative algorithms used for simulating complex physical processes on supercomputer systems. The proposed methodology is based on the BSF (Bulk Synchronous Farm) parallel computation model, which makes it possible to predict the upper scalability bound of an iterative algorithm in early stages of its design. The BSF model assumes the representation of the algorithm in the form of operations on lists using high-order functions. Two classes of representations are considered: BSF-M (Map BSF) and BSF-MR (Map-Reduce BSF). The proposed methodology is described by the example of solving a system of linear equations by the Jacobi method. For the Jacobi method, two iterative algorithms are constructed: Jacobi-M based on the BSF-M representation and Jacobi-MR based on the BSF-MR representation. Analytical estimations of the speedup, parallel efficiency and upper scalability bound are obtained for these algorithms using the BSF cost metrics on multi-processor computing systems with distributed memory. These algorithms are implemented on C++ language using the BSF program skeleton and MPI parallel programming library. The results of large-scale computational experiments performed on a cluster computing system are discussed. Based on the experimental results, an analysis of the adequacy of estimations obtained analytically using the BSF cost metric is made.

Author Biographies

N.A. Ezhova

L.B. Sokolinsky

References

  1. Borodulin K. et al. Towards digital twins cloud platform // Proceedings of the 10th International Conference on Utility and Cloud Computing. New York: ACM Press, 2017. 209-210.
  2. Bilardi G., Pietracaprina A. Models of computation, theoretical // Encyclopedia of Parallel Computing. Boston: Springer, 2011. 1150-1158.
  3. JaJa J.F. PRAM (Parallel Random Access Machines) // Encyclopedia of Parallel Computing. Boston: Springer, 2011. 1608-1615.
  4. Valiant L.G. A bridging model for parallel computation // Communications of the ACM. 1990. 33, №8. 103-111.
  5. Culler D. et al. LogP: towards a realistic model of parallel computation // Proc. of the Fourth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. New York: ACM Press, 1993.
  6. Forsell M., Leppänen V. An extended PRAM-NUMA model of computation for TCF programming // Proc. of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops. Washington, DC: IEEE Press, 2012. 786-793.
  7. Gerbessiotis A.V. Extending the BSP model for multi-core and out-of-core computing: MBSP // Parallel Computing. 2015. 41. 90-102.
  8. Lu F., Song J., Pang Y. HLognGP: A parallel computation model for GPU clusters // Concurrency and Computation: Practice and Experience. 2015. 27, N 17. 4880-4896.
  9. Ежова Н.А., Соколинский Л.Б. Модель параллельных вычислений для многопроцессорных систем с распределенной памятью // Вестник ЮУрГУ. Серия: Вычислительная математика и информатика. 2018. 7, №2. 32-49.
  10. Sokolinsky L.B. Analytical estimation of the scalability of iterative numerical algorithms on distributed memory multiprocessors // Lobachevskii Journal of Mathematics. 2018. 39, №4. 571-575.
  11. Silva L.M., Buyya R. Parallel programming models and paradigms // High Performance Cluster Computing: Architectures and Systems. Vol. 2. Upper Saddle River: Prentice Hall, 1999. 4-27.
  12. Darema F. SPMD computational model // Encyclopedia of Parallel Computing. Boston: Springer, 2011. 1933-1943.
  13. Sahni S., Vairaktarakis G. The master-slave paradigm in parallel computer and industrial settings // Journal of Global Optimization. 1996. 9, №3-4. 357-377.
  14. Sokolinskaya I., Sokolinsky L.B. Scalability evaluation of the NSLP algorithm for solving non-stationary linear programming problems on cluster computing systems // Тр. Международной научной конференции "Суперкомпьютерные дни в России". М.: Изд-во МГУ, 2017. 319-332.
  15. Cole M.I. Parallel programming with list homomorphisms // Parallel Processing Letters. 1995. 5, N 2. 191-203.
  16. Rutishauser H. The Jacobi method for real symmetric matrices // Handbook for Automatic Computation. Vol. 2. Linear Algebra Heidelberg: Springer, 1971. 202-211.
  17. Jacobi C.G. J. Ueber eine neue Auflösungsart der bei der Methode der kleinsten Quadrate vorkommenden lineären Gleichungen // Astronomische Nachrichten. 1845. 22, N 20. 297-306.
  18. Goldstine H.H., Murray F.J., von Neumann J. The Jacobi method for real symmetric matrices // Journal of the ACM. 1959. 6, N 1. 59-96.
  19. Yang X.I. A., Mittal R. Acceleration of the Jacobi iterative method by factors exceeding using scheduled relaxation // Journal of Computational Physics. 2014. 274. 695-708.
  20. Adsuara J.E. et al. Scheduled relaxation Jacobi method: improvements and applications // Journal of Computational Physics. 2016. 321. 369-413.
  21. Kostenetskiy P.S., Safonov A.Y. SUSU supercomputer resources// Proc. of the 10th Annual International Scientific Conference on Parallel Computing Technologies (PCT 2016). CEURWorkshop Proceedings. Vol. 1576. 2016. 561-573.

Published

2018-12-24

How to Cite

Ежова Н.А., Соколинский Л.Б. Scalability Evaluation of Iterative Algorithms for Supercomputer Simulation of Physical Processes // Numerical methods and programming. 2018. 19. 416-430. doi 10.26089/NumMet.v19r437

Issue

Section

Section 1. Numerical methods and applications