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

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

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

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Рубрика: Информатика, вычислительная техника и управление

Статья в выпуске: 2 т.7, 2018 года.

Бесплатный доступ

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

Еще

Параллельное программирование, модель параллельных вычислений, фреймворк "мастер-рабочие", модель bsf, временная сложность, масштабируемость, многопроцессорные системы с распределенной памятью

Короткий адрес: https://sciup.org/147160642

IDR: 147160642   |   DOI: 10.14529/cmse180203

Список литературы Модель параллельных вычислений для многопроцессорных систем с распределенной памятью

  • TOP500 Supercomputer Sites. URL: https://www.top500.org (дата обращения: 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. P. 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. P. 4-27.
  • Leung J.Y.-T., Zhao H. Scheduling Problems in Master-Slave Model//Annals of Operations Research. 2008. Vol. 159, No. 1. P. 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. P. 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. P. 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. P. 870-875 DOI: 10.1145/508791.508960
  • Ершова А.В., Соколинская И.М. Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений//Вычислительные методы и программирование. 2011. Т. 12. С. 423-434.
  • Бурцев А.П. Параллельная обработка данных сейсморазведки с использованием расширенной модели Master-Slave//Суперкомпьютерные дни в России: Труды международной конференции (26-27 сентября 2016 г., г. Москва). М.: Изд-во МГУ, 2016. С. 887-895.
  • Sahni S. Scheduling Master-Slave Multiprocessor Systems//IEEE Transactions on Computers. 1996. Vol. 45, No. 10. P. 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. P. 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. P. 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. P. 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. P. 117-131 DOI: 10.1142/S0129626408003260
  • Padua D. et al. Models of Computation, Theoretical//Encyclopedia of Parallel Computing. Boston, MA: Springer US, 2011. P. 1150-1158. 4_218 DOI: 10.1007/978-0-387-09766-
  • 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. P. 543-551 DOI: 10.1007/3-540-48311-X_76
  • Соколинская И.М., Соколинский Л.Б. О решении задачи линейного программирования в эпоху больших данных//Параллельные вычислительные технологии -XI международная конференция, ПаВТ’2017, г. Казань, 3-7 апреля 2017 г. Короткие статьи и описания плакатов. Челябинск: Издательский центр ЮУрГУ, 2017. С. 471-484. http://omega.sp.susu.ru/pavt2017/short/014.pdf.
  • Костенецкий П.С., Сафонов А.Ю. Суперкомпьютерный комплекс ЮУрГУ//Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (28 марта -1 апреля 2016 г., г. Архангельск). Челябинск: Издательский центр ЮУрГУ, 2016. С. 561-573. http://ceur-ws.org/Vol-1576/119.pdf.
  • Sokolinskaya I., Sokolinsky L.B. Scalability Evaluation of the NSLP Algorithm for Solving Non-Stationary Linear Programming Problems On Cluster Computing Systems//Суперкомпьютерные дни в России: Труды международной конференции (25-26 сентября 2017 г., г. Москва). М.: Изд-во МГУ, 2017. С. 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. P. 30-39. http://ceur-ws.org/Vol-1990/paper-04.pdf.
Еще
Статья научная
QR-код для установки приложения SciUp Наведите камеру и скачайте бесплатное приложение SciUp