Geodesic
Parallel computational model for multiprocessor systems with distributed memory
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 2, pp. 32-49 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The emergence of powerful multiprocessor computing systems brings to the fore issues related to the development of frameworks (templates) that allow creating high-scalable parallel programs oriented to systems with distributed memory. In this case, the most important problem is the development of parallel computing models that allow us to assess its scalability at an early stage of the program design. General requirements for computational models are described and a new high-level parallel computing model called BSF is derived, which is an extension of the BSP model, and is based on the SPMD programming method and the «master-workers» framework. The BSF-model is oriented to computational systems with massive parallelism on distributed memory, including hundreds of thousands of processor nodes, and having an exaflop level of performance and numerical iterative methods with high time complexity. The BSF-computer architecture is defined, and the structure of the BSF-program is described. The formal cost metric, which provides parallel BSF-programs scalability upper bounds in context of distributed memory computing systems, is described. Also, formula for BSF-programs parallel efficiency are derived.
Keywords: parallel programming, parallel computation model, master-workers framework, BSF-model, time complexity, Bulk Synchronous Farm, scalability, multiprocessor systems with distributed memory. 
@article{VYURV_2018_7_2_a2,
     author = {N. A. Ezhova and L. B. Sokolinsky},
     title = {Parallel computational model for multiprocessor systems with distributed memory},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {32--49},
     year = {2018},
     volume = {7},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a2/}
}
TY  - JOUR
AU  - N. A. Ezhova
AU  - L. B. Sokolinsky
TI  - Parallel computational model for multiprocessor systems with distributed memory
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2018
SP  - 32
EP  - 49
VL  - 7
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a2/
LA  - ru
ID  - VYURV_2018_7_2_a2
ER  - 
%0 Journal Article
%A N. A. Ezhova
%A L. B. Sokolinsky
%T Parallel computational model for multiprocessor systems with distributed memory
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2018
%P 32-49
%V 7
%N 2
%U http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a2/
%G ru
%F VYURV_2018_7_2_a2
N. A. Ezhova; L. B. Sokolinsky. Parallel computational model for multiprocessor systems with distributed memory. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 7 (2018) no. 2, pp. 32-49. http://geodesic.mathdoc.fr/item/VYURV_2018_7_2_a2/

[1] TOP500 Supercomputer Sites., } {\tt https://www.top500.org

[2] S. Sahni, G. Vairaktarakis, “The Master-Slave Paradigm in Parallel Computer and Industrial Settings”, Journal of Global Optimization, 9:3–4 (1996), 357–377 | DOI

[3] L. M. Silva, R. Buyya, “Parallel Programming Models and Paradigms”, High Performance Cluster Computing: Architectures and Systems. Vol, 2 (1999), 4–27

[4] J. Y. Leung, H. Zhao, “Scheduling Problems in Master-Slave Model”, Annals of Operations Research, 159:1 (2008), 215–231 | DOI

[5] R. Bouaziz, “Efficient Parallel Multi-Objective Optimization for Real-Time Systems Software Design Exploration”, Proceedings of the 27th International Symposium on Rapid System Prototyping, RSP’16 (October 1–7, 2016, Pittsburgh, Pennsylvania, USA), 58–64 | DOI

[6] E. Cantú-Paz, D. E. Goldberg, “On the Scalability of Parallel Genetic Algorithms”, Evolutionary Computation, 1999, 429–449 | DOI

[7] M. Depolli, R. Trobec, B. Filipič, “Asynchronous Master-Slave Parallelization of Differential Evolution for Multi-Objective Optimization”, Evolutionary Computation, 21:2 (2012), 1–31 | DOI

[8] E. N. Mathias, et al., “DEVOpT: A Distributed Architecture Supporting Heuristic and Metaheuristic Optimization Methods”, Proceedings of the ACM Symposium on Applied Computing (March 11–14, 2002, Madrid, Spain), ACM Press, 2002, 870–875 | DOI

[9] A. V. Ershova, I. M. Sokolinskaya, “Parallel Algorithm for Solving the Strong Separability Problem on the Basis of Fejér Mappings”, Numerical Methods and Programming, 12 (2011), 423–434

[10] A. P. Burtsev, “Parallel Processing of Seismic Data Using the Extended Master-Slave Model”, Russian Supercomputing Days: Proceedings of the International Scintific Conference (Moscow, Russia, September 26 –27, 2016), Publishing House of Moscow State University, Moscow, 2016, 887–895

[11] S. Sahni, “Scheduling Master-Slave Multiprocessor Systems”, IEEE Transactions on Computers, 45:10 (1996), 1195–1199 | DOI

[12] F. Darema, et al., “et al. A Single-Program-Multiple-Data Computational Model for EPEX/FORTRAN”, Parallel Computing, 7:1 (1988), 11–24 | DOI

[13] W. Gropp, E. Lusk, A. Skjellum, Using MPI: Portable Parallel Programming with the Message-Passing Interface, Second Edition, MIT Press, 1999

[14] L. G. Valiant, “A Bridging Model for Parallel Computation”, Communications of the ACM, 33:8 (1990), 103–111 | DOI

[15] M. Goudreau, et al., “Towards Efficiency and Portability: Programming with the BSP Model”, Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA’96. (New York, NY, USA: ACM Press, 1996), 1996, 1–12 | DOI

[16] M. I. Cole, Algorithmic Skeletons: Structured Management of Parallel Computation, MIT Press, Cambridge, MA, USA, 1991, 170 pp.

[17] M. Poldner, H. Kuchen, “On Implementing the Farm Skeleton”, Parallel Processing Letters, 18:1 (2008), 117–131 | DOI

[18] D. Padua, et al., “et al. Models of Computation, Theoretical”, Encyclopedia of Parallel Computing., 2011, 1150–1158, Springer US, Boston, MA | DOI

[19] G. Bilardi, A. Pietracaprina, G. Pucci, “A Quantitative Measure of Portability with Application to Bandwidth-Latency Models for Parallel Computing”, Euro-Par’99 Parallel Processing (Toulouse, France, August 31 – September 3, 1999), Lecture Notes in Computer Science, 1685, Springer, Berlin, Heidelberg, 1999, 543–551 | DOI

[20] I. M. Sokolinskaya, L. B. Sokolinsky, “On the Solution of the Problem of Linear Programming in the Era of Large Data”, PCT'2017 (Kazan, 3–7 April 2017), Publishing Center of the South Ural State University, Chelyabinsk, 2017, 471–484 } {\tt http://omega.sp.susu.ru/pavt2017/short/014.pdf

[21] P. S. Kostenetskiy, A. Y. Safonov, “SUSU Supercomputer Resources”, CEUR Workshop Proceedings, Proceedings of the 10th Annual International Scientific Conference on Parallel Computing Technologies (PCT 2016) (Arkhangelsk, Russia, March 29–31, 2016), 2016, 561–573 } {\tt http://ceur-ws.org/Vol-1576/119.pdf

[22] P. S. Kostenetskiy, A. Y. Safonov, “Scalability Evaluation of the NSLP Algorithm for Solving Non-Stationary Linear Programming Problems On Cluster Computing Systems”, CEUR Workshop Proceedings, Russian Supercomputing Days: Proceedings of the International Scintific Conference (Moscow, September 25–26, 2017), 2017, 319–332 } {\tt http://russianscdays.org/files/pdf17/319.pdf

[23] N. Ezhova, “Verification of BSF Parallel Computational Model”, 3rd Ural Workshop on Parallel, Distributed, and Cloud Computing for Young Scientists (Ural-PDC). CEUR Workshop Proceedings, 1990, 30–39 } {\tt http://ceur-ws.org/Vol1990/paper-04.pdf