Массовая синхронная параллель

с объемным синхронным параллельным ( BSP ) Абстрактные компьютеры — это связующая модель для разработки параллельных алгоритмов . Она похожа на модель параллельной машины произвольного доступа (PRAM), но, в отличие от PRAM, BSP не считает связь и синхронизацию чем-то само собой разумеющимся. Фактически, количественная оценка необходимой синхронизации и связи является важной частью анализа алгоритма BSP.

История

Модель BSP была разработана Лесли Валиантом из Гарвардского университета в 1980-х годах. Полная статья была опубликована в 1990 году. ^{[ 1 ]}

В период с 1990 по 1992 год Лесли Валиант и Билл Макколл из Оксфордского университета работали над идеями модели программирования BSP с распределенной памятью в Принстоне и Гарварде. В период с 1992 по 1997 год Макколл возглавлял большую исследовательскую группу в Оксфорде, которая разработала различные библиотеки, языки и инструменты программирования BSP, а также множество алгоритмов BSP с массовым параллелизмом, включая множество ранних примеров высокопроизводительных параллельных алгоритмов, избегающих взаимодействия. ^{[ 2 ]} и рекурсивные «бессмертные» параллельные алгоритмы, которые достигают максимально возможной производительности и оптимальных параметрических компромиссов. ^{[ 3 ]}

С ростом интереса и импульса Макколл затем возглавил группу из Оксфорда, Гарварда, Флориды, Принстона, Bell Labs, Колумбии и Утрехта, которые разработали и опубликовали стандарт BSPlib для программирования BSP в 1996 году. ^{[ 4 ]}

Компания Valiant разработала расширение модели BSP в 2000-х годах, что привело к публикации модели Multi-BSP в 2011 году. ^{[ 5 ]}

В 2017 году Макколл разработал новое крупное расширение модели BSP, которое обеспечивает отказоустойчивость и хвостоустойчивость для крупномасштабных параллельных вычислений в области искусственного интеллекта, аналитики и высокопроизводительных вычислений (HPC). ^{[ 6 ]} См. также ^{[ 7 ]}

Модель БСП

Обзор

Компьютер BSP состоит из следующего:

Компоненты, способные обрабатывать и/или транзакции в локальной памяти (т. е. процессоры),
Сеть, которая маршрутизирует сообщения между парами таких компонентов и
Аппаратное средство, позволяющее синхронизировать все или часть компонентов.

Обычно это интерпретируется как набор процессоров, которые могут выполнять разные потоки вычислений, причем каждый процессор оснащен быстрой локальной памятью и соединен между собой сетью связи.

Алгоритмы BSP во многом полагаются на третью особенность; Вычисление происходит в виде серии глобальных супершагов , которая состоит из трех компонентов:

Параллельные вычисления: каждый участвующий процессор может выполнять локальные вычисления, т. е. каждый процесс может использовать только значения, хранящиеся в локальной быстрой памяти процессора. Вычисления происходят асинхронно со всеми остальными, но могут перекрываться с обменом данными.
Связь: процессы обмениваются данными для облегчения удаленного хранения данных.
Синхронизация барьера : когда процесс достигает этой точки ( барьера ), он ждет, пока все другие процессы не достигнут того же барьера.

Действия по вычислениям и коммуникации не обязательно должны быть упорядочены во времени. Связь обычно принимает форму односторонних (RDMA) PUT и GET, вызовов удаленного прямого доступа к памяти а не парных двусторонних вызовов отправки и получения сообщений.

Супершаг BSP. Процессам не хватает линейного порядка, и они могут быть сопоставлены с процессорами любым способом.

Барьерная синхронизация завершает супершаг — она гарантирует правильное завершение всех односторонних коммуникаций. Системы, основанные на двусторонней связи, неявно включают стоимость синхронизации для каждого отправленного сообщения. Метод барьерной синхронизации основан на аппаратном обеспечении компьютера BSP. В оригинальной статье Valiant это средство периодически проверяет, достигнут ли глобально конец текущего супершага. Период этой проверки обозначается $L$ . ^{[ 1 ]}

Модель BSP также хорошо подходит для автоматического управления памятью для вычислений с распределенной памятью посредством чрезмерной декомпозиции задачи и переподписки процессоров. Вычисления делятся на большее количество логических процессов, чем физических процессоров, и процессы назначаются процессорам случайным образом. Статистически можно показать, что эта стратегия приводит к почти идеальному балансированию нагрузки, как рабочей, так и коммуникационной.

Коммуникация

Во многих системах параллельного программирования связь рассматривается на уровне отдельных действий, таких как отправка и получение сообщения или передача из памяти в память. С этим сложно работать, поскольку в параллельной программе одновременно выполняется множество коммуникационных действий, и их взаимодействия обычно сложны. В частности, трудно сказать много о времени, которое потребуется для завершения любого отдельного коммуникационного действия.

Модель BSP рассматривает коммуникационные действия в целом . Это приводит к тому, что может быть задана верхняя граница времени, необходимого для передачи набора данных. BSP рассматривает все коммуникационные действия супершага как одну единицу и предполагает, что все отдельные сообщения, отправленные как часть этой единицы, имеют фиксированный размер.

Максимальное количество входящих или исходящих сообщений для супершага обозначается $h$ . Способность сети связи доставлять данные фиксируется параметром $g$ , определено так, что требуется время $hg$ чтобы процессор доставил $h$ сообщения размера 1.

Сообщение длиной $m$ очевидно, что отправка сообщения размера 1 занимает больше времени. Однако модель BSP не делает различия между длиной сообщения $m$ или $m$ сообщения длиной 1. В любом случае говорят, что стоимость равна $mg$ .

Параметр $g$ зависит от следующего:

Протоколы, используемые для взаимодействия внутри сети связи.
Управление буфером как процессорами, так и сетью связи.
Стратегия маршрутизации, используемая в сети.
BSP Система времени выполнения .

На практике, $g$ определяется эмпирически для каждого параллельного компьютера. Обратите внимание, что $g$ — это не нормализованное время доставки одного слова, а время доставки одного слова в условиях непрерывного трафика.

Барьеры

Односторонняя коммуникация модели BSP требует барьерной синхронизации . Барьеры потенциально дорогостоящие, но они позволяют избежать возможности тупиковой или активной блокировки, поскольку барьеры не могут создавать циклические зависимости данных . Инструменты для их обнаружения и борьбы с ними не нужны. Барьеры также допускают новые формы отказоустойчивости. ^{[ нужна ссылка ]}.

На стоимость барьерной синхронизации влияет несколько факторов:

Стоимость, вызванная изменением времени завершения участвующих параллельных вычислений. Возьмем пример, когда все процессы, кроме одного, завершили свою работу для этого супершага и ждут последнего процесса, которому еще предстоит завершить много работы. Лучшее, что может сделать реализация, — это гарантировать, что каждый процесс работает примерно с одинаковым размером задачи.
Стоимость достижения глобально согласованного состояния во всех процессорах. Это зависит от сети связи, а также от наличия специального оборудования для синхронизации и от способа обработки прерываний процессорами.

Стоимость барьерной синхронизации обозначается $l$ . Обратите внимание, что $l<L$ если механизм синхронизации компьютера BSP соответствует предложению Valiant. ^{[ 1 ]} На практике значение $l$ определяется эмпирически.

На больших компьютерах барьеры стоят дорого, и в больших масштабах это становится все более ощутимо. Существует большое количество литературы по удалению точек синхронизации из существующих алгоритмов в контексте вычислений BSP и за его пределами. Например, многие алгоритмы позволяют локально обнаружить глобальное завершение супершага, просто сравнивая локальную информацию с количеством уже полученных сообщений. Это сводит к нулю стоимость глобальной синхронизации по сравнению с минимально необходимой задержкой связи. ^{[ 8 ]} Однако ожидается, что эта минимальная задержка еще больше увеличится для будущих суперкомпьютерных архитектур и сетевых соединений; Модель BSP, как и другие модели параллельных вычислений, требует адаптации, чтобы справиться с этой тенденцией. Multi-BSP — это одно из решений на базе BSP. ^{[ 5 ]}

Алгоритмическая стоимость

Стоимость супершага определяется как сумма трех слагаемых:

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

Таким образом, стоимость одного супершага для $p$ процессоры:

$max_{i=1}^{p}(w_{i})+max_{i=1}^{p}(h_{i}g)+l$ где $w_{i}$ стоимость локальных вычислений в процессе $i$ , и $h_{i}$ количество сообщений, отправленных или полученных процессом $i$ . Обратите внимание, что здесь предполагаются однородные процессоры. Чаще всего выражение записывается как $w+hg+l$ где $w$ и $h$ являются максимумами. Стоимость всего алгоритма BSP представляет собой сумму стоимости каждого супершага.

$W+Hg+Sl=\sum _{s=1}^{S}w_{s}+g\sum _{s=1}^{S}h_{s}+Sl$ где $S$ это количество супершагов.

$W$ , $H$ , и $S$ обычно моделируются как функции, которые изменяются в зависимости от размера задачи. Эти три характеристики алгоритма BSP обычно описываются в терминах асимптотических обозначений , например: $H\in O(n/p)$ .

Расширения и использование

Интерес к BSP резко возрос, поскольку Google принял его в качестве основной технологии для графовой аналитики в больших масштабах с помощью Pregel и MapReduce . Кроме того, поскольку следующее поколение Hadoop отделяет модель MapReduce от остальной инфраструктуры Hadoop, теперь существуют активные проекты с открытым исходным кодом для добавления явного программирования BSP, а также других высокопроизводительных моделей параллельного программирования поверх Hadoop. Примерами являются Apache Hama и Apache Giraph . ^{[ 9 ]}

Многие авторы расширяли BSP, чтобы устранить опасения по поводу непригодности BSP для моделирования конкретных архитектур или вычислительных парадигм. Одним из примеров этого является разложимая модель BSP. Модель также использовалась при создании ряда новых языков программирования и интерфейсов, таких как Bulk Synchronous Parallel ML (BSML), BSPLib, Apache Hama , ^{[ 9 ]} и Прегель. ^{[ 10 ]}

Известными реализациями стандарта BSPLib являются библиотека BSP Университета Падерборна. ^{[ 11 ]} и набор инструментов Oxford BSP Джонатана Хилла. ^{[ 12 ]} Современные реализации включают BSPonMPI. ^{[ 13 ]} (который имитирует BSP поверх интерфейса передачи сообщений ) и MulticoreBSP ^{[ 14 ]}^{[ 15 ]} (новая реализация, ориентированная на современные архитектуры с общей памятью). MulticoreBSP для C особенно примечателен своей способностью запускать вложенные прогоны BSP, что позволяет явно программировать Multi-BSP.

См. также

Ссылки

^ Jump up to: ^а ^б ^с Лесли Г. Валиант, Модель моста для параллельных вычислений, Communications of the ACM, том 33, выпуск 8, август 1990 г. [1]
^ У. Ф. Макколл. Масштабируемые вычисления. Информатика сегодня: последние тенденции и разработки. Дж ван Леувен (редактор). LNCS, том 1000, Springer-Verlag, стр. 46–61 (1995) [2]
^ У. Ф. Макколл и А. Тискин. Матричное умножение с эффективным использованием памяти в модели BSP. Алгоритмика 24(3), стр.287-297 (1999) [3]
^ JMD Hill, WF McColl, DC Stefanescu, MW Goudreau, K Lang, SB Rao, T Suel, T Tsantilas и RH Bisseling. BSPlib: Библиотека программирования BSP. Параллельные вычисления 24 (14) стр. 1947-1980 (1998) [4]
^ Jump up to: ^а ^б Валиант, LG (2011). Модель моста для многоядерных вычислений. Журнал компьютерных и системных наук , 77(1), 154-166 [5]
^ Модель моста для высокопроизводительных облачных вычислений Билла Макколла на 18-й конференции SIAM по параллельной обработке для научных вычислений (2018), http://meetings.siam.org/sess/dsp_talk.cfm?p=88973 . Архивировано 2019-12- 11 в Wayback Machine .
^ Билл Макколл. Математика, модели и архитектуры. Глава 1, стр. 6–53. Математика для будущих вычислений и коммуникаций под редакцией Ляо Хэна и Билла Макколла. Издательство Кембриджского университета (2022). [6]
^ Альперт Р. и Филбин Дж. (1997). cBSP: синхронизация с нулевой стоимостью в модифицированной модели BSP. Исследовательский институт NEC, 4 Independent Way, Princeton NJ, 8540, [7] .
^ Jump up to: ^а ^б Апач Хама
^ Прегель
^ Библиотека BSP (PUB) Университета Падерборна - Проектирование, реализация и производительность Институт Хайнца Никсдорфа, факультет компьютерных наук, Университет Падерборна, Германия, технический отчет . Архивировано 5 июня 2001 г. в Wayback Machine .
^ Джонатан Хилл: Набор инструментов Oxford BSP , 1998.
^ Вейнанд Дж. Суйлен: BSPonMPI , 2006.
^ MulticoreBSP для C: высокопроизводительная библиотека для параллельного программирования с общей памятью. А.Н. Изельман, Р.Х. Бисселинг, Д. Руз и К. Меерберген в Международном журнале параллельного программирования, в печати (2013), doi:10.1109/TPDS.2013.31 .
^ Объектно-ориентированная пакетная синхронная параллельная библиотека для многоядерного программирования А. Н. Айзельман и Роб Х. Бисселинг в книге «Параллелизм и вычисления: практика и опыт», 24(5), стр. 533–553 (2012), doi:10.1002/cpe.1843 .

Внешние ссылки

Д.Б. Скилликорн, Джонатан Хилл, У.Ф. Макколл, Вопросы и ответы о BSP ^{[ постоянная мертвая ссылка ]} (1996)
БСП по всему миру
Документы, связанные с BSP
(на французском языке) Bulk Synchronous Parallel ML ( (на английском языке) официальный сайт )
Апач Хама
Апач Жираф
Библиотека BSP Падерборнского университета
БСПонМПИ
МногоядерныйBSP

[CACM_Valiant-1] Jump up to: ^а ^б ^с Лесли Г. Валиант, Модель моста для параллельных вычислений, Communications of the ACM, том 33, выпуск 8, август 1990 г. [1]

[scalable-computing-2] У. Ф. Макколл. Масштабируемые вычисления. Информатика сегодня: последние тенденции и разработки. Дж ван Леувен (редактор). LNCS, том 1000, Springer-Verlag, стр. 46–61 (1995) [2]

[mccoll-tiskin-3] У. Ф. Макколл и А. Тискин. Матричное умножение с эффективным использованием памяти в модели BSP. Алгоритмика 24(3), стр.287-297 (1999) [3]

[bsplib-4] JMD Hill, WF McColl, DC Stefanescu, MW Goudreau, K Lang, SB Rao, T Suel, T Tsantilas и RH Bisseling. BSPlib: Библиотека программирования BSP. Параллельные вычисления 24 (14) стр. 1947-1980 (1998) [4]

[JCSS_Valiant-5] Jump up to: ^а ^б Валиант, LG (2011). Модель моста для многоядерных вычислений. Журнал компьютерных и системных наук , 77(1), 154-166 [5]

[McC2017-6] Модель моста для высокопроизводительных облачных вычислений Билла Макколла на 18-й конференции SIAM по параллельной обработке для научных вычислений (2018), http://meetings.siam.org/sess/dsp_talk.cfm?p=88973 . Архивировано 2019-12- 11 в Wayback Machine .

[math-models-arch-7] Билл Макколл. Математика, модели и архитектуры. Глава 1, стр. 6–53. Математика для будущих вычислений и коммуникаций под редакцией Ляо Хэна и Билла Макколла. Издательство Кембриджского университета (2022). [6]

[Alpert-8] Альперт Р. и Филбин Дж. (1997). cBSP: синхронизация с нулевой стоимостью в модифицированной модели BSP. Исследовательский институт NEC, 4 Independent Way, Princeton NJ, 8540, [7] .

[hama-9] Jump up to: ^а ^б Апач Хама

[10] Прегель

[PUB-11] Библиотека BSP (PUB) Университета Падерборна - Проектирование, реализация и производительность Институт Хайнца Никсдорфа, факультет компьютерных наук, Университет Падерборна, Германия, технический отчет . Архивировано 5 июня 2001 г. в Wayback Machine .

[hill-12] Джонатан Хилл: Набор инструментов Oxford BSP , 1998.

[13] Вейнанд Дж. Суйлен: BSPonMPI , 2006.

[Yze13-14] MulticoreBSP для C: высокопроизводительная библиотека для параллельного программирования с общей памятью. А.Н. Изельман, Р.Х. Бисселинг, Д. Руз и К. Меерберген в Международном журнале параллельного программирования, в печати (2013), doi:10.1109/TPDS.2013.31 .

[Yze12-15] Объектно-ориентированная пакетная синхронная параллельная библиотека для многоядерного программирования А. Н. Айзельман и Роб Х. Бисселинг в книге «Параллелизм и вычисления: практика и опыт», 24(5), стр. 533–553 (2012), doi:10.1002/cpe.1843 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]