Модель параллельного программирования
В вычислительной технике модель параллельного программирования — это абстракция параллельной компьютерной архитектуры, с помощью которой удобно выражать алгоритмы и их композицию в программах . О ценности модели программирования можно судить по ее общности : насколько хорошо может быть выражен ряд различных проблем для множества различных архитектур, и по ее производительности : насколько эффективно могут выполняться скомпилированные программы. [1] Реализация модели параллельного программирования может принимать форму библиотеки , вызываемой из языка программирования в качестве расширения существующих языков.
Консенсус вокруг конкретной модели программирования важен, поскольку он приводит к созданию различных параллельных компьютеров с поддержкой этой модели, тем самым облегчая переносимость программного обеспечения. В этом смысле модели программирования называются мостом между аппаратным и программным обеспечением. [2]
Классификация моделей параллельного программирования [ править ]
Классификации моделей параллельного программирования можно разделить на две области: взаимодействие процессов и декомпозиция задач. [3] [4] [5]
Взаимодействие процессов [ править ]
Взаимодействие процессов относится к механизмам, с помощью которых параллельные процессы могут взаимодействовать друг с другом. Наиболее распространенными формами взаимодействия являются общая память и передача сообщений, но взаимодействие также может быть неявным (невидимым для программиста).
[ править ]
Общая память — это эффективное средство передачи данных между процессами. В модели с общей памятью параллельные процессы совместно используют глобальное адресное пространство, в котором они читают и записывают асинхронно. Асинхронный одновременный доступ может привести к состояниям гонки такие механизмы, как блокировки , семафоры и мониторы , и чтобы избежать этого, можно использовать . Обычные многоядерные процессоры напрямую поддерживают разделяемую память, многие языки и библиотеки параллельного программирования, такие как Cilk , OpenMP и Threading Building Blocks для использования которой предназначены .
Передача сообщений [ править ]
В модели передачи сообщений параллельные процессы обмениваются данными посредством передачи сообщений друг другу. Эти коммуникации могут быть асинхронными, когда сообщение может быть отправлено до того, как получатель будет готов, или синхронными, когда получатель должен быть готов. Формализация передачи сообщений Communicating Sequential Processes (CSP) использует синхронные каналы связи для соединения процессов и привела к появлению таких важных языков, как Occam , Limbo и Go . Напротив, модель актера использует асинхронную передачу сообщений и использовалась при разработке таких языков, как D , Scala и SALSA.
Разделенное глобальное адресное пространство [ править ]
Модели разделенного глобального адресного пространства (PGAS) обеспечивают золотую середину между общей памятью и передачей сообщений. PGAS предоставляет абстракцию глобального адресного пространства памяти, которая логически разделена, где часть является локальной для каждого процесса. Параллельные процессы взаимодействуют посредством асинхронного выполнения операций (например, чтения и записи) в глобальном адресном пространстве, что напоминает модели общей памяти. Однако за счет семантического разделения глобального адресного пространства на части, связанные с конкретными процессами, они позволяют программистам использовать локальность ссылок и обеспечивают эффективную реализацию на параллельных компьютерах с распределенной памятью . PGAS предлагается многими языками и библиотеками параллельного программирования, такими как Fortran 2008 , Chapel , UPC++ и SHMEM .
Неявное взаимодействие [ править ]
В неявной модели программист не видит взаимодействия процессов, и вместо этого за его выполнение отвечает компилятор и/или среда выполнения. Двумя примерами неявного параллелизма являются языки, специфичные для предметной области, где предписывается параллелизм в операциях высокого уровня, и языки функционального программирования, поскольку отсутствие побочных эффектов позволяет независимым функциям выполняться параллельно. [6] Однако с таким параллелизмом трудно справиться. [7] а функциональные языки, такие как Concurrent Haskell и Concurrent ML, предоставляют функции для явного и правильного управления параллелизмом.
Декомпозиция задачи [ править ]
Параллельная программа состоит из одновременно выполняемых процессов. Декомпозиция проблемы связана со способом формулировки составляющих процессов. [8] [5]
Параллелизм задач [ править ]
Модель параллельного выполнения задач фокусируется на процессах или потоках выполнения. Эти процессы часто будут поведенчески различны, что подчеркивает необходимость общения. Параллелизм задач — это естественный способ выразить коммуникацию посредством передачи сообщений. В таксономии Флинна параллелизм задач обычно классифицируется как MIMD / MPMD или MISD .
Параллелизм данных [ править ]
Модель с параллельными данными фокусируется на выполнении операций с набором данных, обычно с регулярно структурированным массивом. С этими данными будет работать набор задач, но независимо на непересекающихся разделах. В таксономии Флинна параллелизм данных обычно классифицируется как MIMD / SPMD или SIMD .
Параллелизм потоков [ править ]
Потоковый параллелизм, также известный как конвейерный параллелизм, фокусируется на разделении вычислений на последовательность этапов, где каждый этап обрабатывает часть входных данных данные. Каждая ступень работает независимо и одновременно, а выход одной ступени этап служит входом для следующего этапа. Параллелизм потоков особенно удобен для приложений с непрерывными потоками данных или конвейерными вычислениями.
Неявный параллелизм [ править ]
Как и в случае неявного взаимодействия процессов, неявная модель параллелизма ничего не раскрывает программисту, поскольку ответственность за это несут компилятор, среда выполнения или оборудование. Например, в компиляторах автоматическое распараллеливание — это процесс преобразования последовательного кода в параллельный код, а в компьютерной архитектуре суперскалярное выполнение — это механизм, посредством которого параллелизм на уровне команд используется для параллельного выполнения операций.
Терминология [ править ]
Модели параллельного программирования тесно связаны с моделями вычислений . Модель параллельных вычислений — это абстракция , используемая для анализа стоимости вычислительных процессов, но она не обязательно должна быть практичной, поскольку ее можно эффективно реализовать в аппаратном и/или программном обеспечении. Модель программирования, напротив, конкретно подразумевает практические соображения по реализации аппаратного и программного обеспечения. [9]
Язык параллельного программирования может быть основан на одной модели программирования или на их комбинации. Например, высокопроизводительный язык Fortran основан на взаимодействиях с общей памятью и декомпозиции задач с параллельными данными, а Go предоставляет механизм для взаимодействия с общей памятью и передачи сообщений.
Примеры моделей параллельного программирования [ править ]
| Имя | Класс взаимодействия | Класс разложения | Пример реализации |
|---|---|---|---|
| Модель актера | Асинхронная передача сообщений | Задача | D , Эрланг , Скала , САЛЬСА |
| Массовая синхронная параллель | Общая память | Задача | Apache Giraph , Apache Hama , BSPlib |
| Коммуникация последовательных процессов | Синхронная передача сообщений | Задача | Ада , Оккам , VerilogCSP , Го |
| Схемы | Передача сообщений | Задача | Верилог , VHDL |
| Поток данных | Передача сообщений | Задача | Блеск , TensorFlow , Apache Flink |
| Функциональный | Передача сообщений | Задача | Параллельный Haskell , Параллельное машинное обучение |
| ЛогП-машина | Синхронная передача сообщений | Не указан | Никто |
| Параллельная машина произвольного доступа | Общая память | Данные | Cilk , CUDA , OpenMP , строительные блоки многопоточности , XMTC |
| СПМД ПГАС | Разделенное глобальное адресное пространство | Данные | Фортран 2008 , унифицированный параллельный C , UPC++ , SHMEM |
| Глобальный параллелизм задач | Разделенное глобальное адресное пространство | Задача | Часовня , X10 |
См. также [ править ]
- Автоматическое распараллеливание
- Модель моста
- Параллелизм
- Степень параллелизма
- Явный параллелизм
- Список параллельных и параллельных языков программирования
- Оптическое многодерево с произвольным обменом
- Параллельная внешняя память (модель)
Ссылки [ править ]
- ^ Скиликорн, Дэвид Б., «Модели для практических параллельных вычислений», Международный журнал параллельного программирования, 20.2 133–158 (1991), https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf
- ^ Лесли Г. Валиант, «Модульная модель для параллельных вычислений», Communications of ACM, том 33, выпуск 8, август 1990 г., страницы 103–111.
- ^ Джон Э. Сэвидж, Модели вычислений: исследование возможностей вычислений, 2008, Глава 7 (Параллельные вычисления), http://cs.brown.edu/~jes/book/. Архивировано 5 ноября 2016 г. в Wayback Machine.
- ^ «1.3 Модель параллельного программирования» . www.mcs.anl.gov . Проверено 21 марта 2024 г.
- ^ Перейти обратно: а б «Учебное пособие «Введение в параллельные вычисления | HPC @ LLNL»» . hpc.llnl.gov . Проверено 21 марта 2024 г.
- ^ Хаммонд, Кевин. Параллельное функциональное программирование: Введение. На Международном симпозиуме по параллельным символьным вычислениям, стр. 46. 1994.
- ^ Макберни, Д.Л., и М. Ронан Сон. «Транспьютерные эксперименты с архитектурой ZAPP». PARLE Параллельные архитектуры и языки Европы. Шпрингер Берлин Гейдельберг, 1987.
- ^ «2.2 Разделение» . www.mcs.anl.gov . Проверено 21 марта 2024 г.
- ^ Скилликорн, Дэвид Б. и Доменико Талия, Модели и языки для параллельных вычислений, ACM Computing Surveys, 30.2 123–169 (1998), https://www.cs.utexas.edu/users/browne/CS392Cf2000/papers/ ModelsOfParallelComputation-Skillicorn.pdf
Дальнейшее чтение [ править ]
- Блез Барни, Введение в параллельные вычисления , Ливерморская национальная лаборатория Лоуренса, заархивировано из оригинала 10 июня 2013 г. , получено 22 ноября 2015 г.
- Мюррей И. Коул, Алгоритмические скелеты: структурированное управление параллельными вычислениями (PDF) , Университет Глазго
- Дж. Дарлинтон; М. Ганем; Х.В. То (1993). «Структурированное параллельное программирование». Материалы семинара по моделям программирования для массово-параллельных компьютеров . стр. 160–169. дои : 10.1109/PMMP.1993.315543 . ISBN 0-8186-4900-3 . S2CID 15265646 .
{{cite book}}:|journal=игнорируется ( помощь ) CS1 maint: дата и год ( ссылка ) - Ян Фостер, Проектирование и реализация параллельных программ , Аргоннская национальная лаборатория
| Общий | |
|---|---|
| Уровни | |
| Многопоточность | |
| Теория | |
| Элементы | |
| Координация | |
| Программирование | |
| Аппаратное обеспечение | |
| API | |
| Проблемы | |
