BSF: модель параллельных вычислений для многопроцессорных систем с распределенной памятью

Надежда Александровна Ежова, Леонид Борисович Соколинский

Аннотация


Появление мощных многопроцессорных вычислительных систем выдвигает на первый план вопросы, связанные с разработкой фреймворков (шаблонов), позволяющих создавать высокомасштабируемые параллельные программы, ориентированные на системы с распределенной памятью. При этом особенно важной является проблема разработки моделей параллельных вычислений, позволяющих на ранней стадии проектирования программы оценить ее масштабируемость. В статье приводятся общие требования к модели вычислений и строится новая высокоуровневая модель параллельных вычислений Bulk Synchronous Farm (BSF), являющаяся расширением модели BSP, и основанная на методе программирования SPMD и парадигме «мастер-рабочие». Модель BSF ориентирована на вычислительные системы с массовым параллелизмом на распределенной памяти, включающие в себя сотни тысяч процессорных узлов, и имеющие экзафлопный уровень производительности и на численные итерационные методы с высокой временной сложностью. Определяется архитектура BSF-компьютера и описывается структура BSF-программы. Описывается формальная стоимостная метрика, с помощью которой получаются верхние оценки масштабируемости параллельных BSF-программ применительно к вычислительным системам с распределенной памятью. Также выводятся формулы для оценки эффективности распараллеливания BSF-программ и даются аналитические оценки масштабируемости BSF-приложений.


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


параллельное программирование; модель параллельных вычислений; фреймворк «мастер-рабочие»; модель BSF; временная сложность; Bulk Synchronous Farm; масштабируемость; многопроцессорные системы с распределенной памятью

Полный текст:

PDF

Литература


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.




DOI: http://dx.doi.org/10.14529/cmse180203