Parallel Сomputational Model for Multiprocessor Systems with Distributed Memory
DOI:
https://doi.org/10.14529/cmse180203Keywords:
parallel programming, parallel computation model, master-workers framework, BSF-model, time complexity, Bulk Synchronous Farm, scalability, multiprocessor systems with distributed memoryAbstract
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.
References
TOP500 Supercomputer Sites. Available at: https://www.top500.org (accessed: 03.04.2017).
Sahni S., Vairaktarakis G. The Master-Slave Paradigm in Parallel Computer and Industrial Settings. Journal of Global Optimization. 1996. vol. 9, no. 3–4. pp. 357–377. DOI: 10.1007/BF00121679.
Silva L.M., Buyya R. Parallel Programming Models and Paradigms. High Performance Cluster Computing: Architectures and Systems. vol. 2. 1999. pp. 4–27.
Leung J.Y.-T., Zhao H. Scheduling Problems in Master-Slave Model. Annals of Operations Research. 2008. vol. 159, no. 1. pp. 215–231. DOI: 10.1007/s10479-007-0271-4.
Bouaziz R. et al. 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. pp. 58-64. DOI: 10.1145/2990299.2990310.
Cantú-Paz E., Goldberg D.E. On the Scalability of Parallel Genetic Algorithms. Evolutionary Computation. 1999. vol. 7, no. 4. pp. 429–449. DOI: 10.1162/evco.1999.7.4.429.
Depolli M., Trobec R., Filipič B. Asynchronous Master-Slave Parallelization of Differential Evolution for Multi-Objective Optimization. Evolutionary Computation. 2012. vol. 21, no. 2. pp. 1–31. DOI: 10.1162/EVCO_a_00076.
Mathias E.N. 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. pp. 870–875. DOI: 10.1145/508791.508960.
Ershova A.V., Sokolinskaya I.M. Parallel Algorithm for Solving the Strong Separability Problem on the Basis of Fejér Mappings. Numerical Methods and Programming. 2011. vol. 12. pp. 423–434. (in Russian)
Burtsev A.P. Parallel Processing of Seismic Data Using the Extended Master-Slave Model. Supercomputernie dni v Rossii: Trudy meghdunarodnoj konferentsii (Moscva, 26–27 sentyabra 2016) [Russian Supercomputing Days: Proceedings of the International Scintific Conference (Moscow, Russia, September 26 –27, 2016)]. Moscow, Publishing House of Moscow State University, 2016. pp. 887–895. (in Russian)
Sahni S. Scheduling Master-Slave Multiprocessor Systems. IEEE Transactions on Computers. 1996. vol. 45, no. 10. pp. 1195–1199. DOI: 10.1109/12.543712.
Darema F. et al. A Single-Program-Multiple-Data Computational Model for EPEX/FORTRAN. Parallel Computing. 1988. vol. 7, no. 1. pp. 11–24. DOI: 10.1016/0167-8191(88)90094-4.
Gropp W., Lusk E., Skjellum A. Using MPI: Portable Parallel Programming with the Message-Passing Interface. Second Edition. MIT Press, 1999.
Valiant L.G. A Bridging Model for Parallel Computation. Communications of the ACM. 1990. vol. 33, no. 8. pp. 103–111. DOI: 10.1145/79173.79181.
Goudreau M. 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. pp. 1–12. DOI: 10.1145/237502.237503.
Cole M.I. Algorithmic Skeletons: Structured Management of Parallel Computation. Cambridge, MA, USA: MIT Press, 1991. 170 p.
Poldner M., Kuchen H. On Implementing the Farm Skeleton. Parallel Processing Letters. 2008. vol. 18, no. 1. pp. 117–131. DOI: 10.1142/S0129626408003260.
Padua D. et al. Models of Computation, Theoretical. Encyclopedia of Parallel Computing. Boston, MA: Springer US, 2011. pp. 1150–1158. DOI: 10.1007/978-0-387-09766-4_218.
Bilardi G., Pietracaprina A., Pucci G. 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, Proceedings. Lecture Notes in Computer Science, vol. 1685. Springer, Berlin, Heidelberg, 1999. pp. 543–551. DOI: 10.1007/3-540-48311-X_76.
Sokolinskaya I.M., Sokolinsky L.B. On the Solution of the Problem of Linear Programming in the Era of Large Data. Parallel'nye vychislitel'nye tekhnologii — XI mezhdunarodnaya konferentsiya, PaVT'2017, g. Kazan, 3–7 aprelya 2017 g. Korotkie stat'i i opisaniya plakatov. [Short Articles and Posters of the XI International Conference on Parallel Computational Technologies (PCT'2017), Kazan, 3–7 April 2017]. Chelyabinsk, Publishing Center of the South Ural State University, 2017. pp. 471–484. http://omega.sp.susu.ru/pavt2017/short/014.pdf. (in Russian)
Kostenetskiy P.S., Safonov A.Y. SUSU Supercomputer Resources. Proceedings of the 10th Annual International Scientific Conference on Parallel Computing Technologies (PCT 2016). Arkhangelsk, Russia, March 29–31, 2016. CEUR Workshop Proceedings. 2016. vol. 1576. pp. 561–563. http://ceur-ws.org/Vol-1576/119.pdf. (in Russian)
Sokolinskaya I., Sokolinsky L.B. Scalability Evaluation of the NSLP Algorithm for Solving Non-Stationary Linear Programming Problems on Cluster Computing Systems. Supercomputernie dni v Rossii: Trudy meghdunarodnoj konferentsii (Moscva, 25–26 sentyabra 2017) [Russian Supercomputing Days: Proceedings of the International Scintific Conference (Moscow, Russia, September 25–26, 2017)]. Moscow, Publishing House of Moscow State University, 2017. pp. 319–332. http://russianscdays.org/files/pdf17/319.pdf.
Ezhova N. Verification of BSF Parallel Computational Model. 3rd Ural Workshop on Parallel, Distributed, and Cloud Computing for Young Scientists (Ural-PDC). CEUR Workshop Proceedings. Vol-1990. CEUR-WS.org. pp. 30–39. http://ceur-ws.org/Vol1990/paper-04.pdf.
