"Scalability evaluation of iterative algorithms for supercomputer simulation
of physical processes"
Ezhova N.A. and Sokolinsky L.B. 
This paper is devoted to the development of a methodology for evaluating the scalability of computeintensive 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 highorder functions. Two classes of representations are considered: BSFM (Map BSF) and BSFMR (MapReduce 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: JacobiM based on the BSFM representation and JacobiMR based on the BSFMR representation. Analytical estimations of the speedup, parallel efficiency and upper scalability bound are obtained for these algorithms using the BSF cost metrics on multiprocessor 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 largescale 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. Keywords: iterative algorithm, BSF parallel computation model, scalability estimation, speedup, parallel efficiency, Jacobi method, cluster computing systems.

