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

Насыпной синхронный параллельный ( BSP ) абстрактный компьютер является шунтирование модели для разработки параллельных алгоритмов . Он служит цели, аналогичной модели параллельной машины с произвольным доступом (PRAM). BSP отличается от PRAM тем, что не воспринимает связь и синхронизацию как должное. Важная часть анализа алгоритма BSP заключается в количественной оценке необходимой синхронизации и обмена данными.

История [ править ]

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

Между 1990 и 1992 годами Лесли Вэлиант и Билл Макколл из Оксфордского университета работали над идеями модели программирования BSP с распределенной памятью в Принстоне и Гарварде. В период с 1992 по 1997 год МакКолл возглавлял большую исследовательскую группу в Оксфорде, которая разработала различные библиотеки, языки и инструменты программирования BSP, а также многочисленные массивно-параллельные алгоритмы BSP. С ростом интереса и импульса Макколл возглавил группу из Оксфорда, Гарварда, Флориды, Принстона, Bell Labs, Колумбии и Утрехта, которые разработали и опубликовали стандарт BSPlib для программирования BSP в 1996 году.

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

В 2017 году МакКолл разработал новое крупное расширение модели BSP, которое обеспечивает отказоустойчивость и устойчивость для крупномасштабных параллельных вычислений в AI, Analytics и HPC. ^[3]

Модель [ править ]

Компьютер BSP состоит из

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

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

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

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

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

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

Связь [ править ]

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

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

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

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

Параметр зависит от следующих факторов: ${\ displaystyle g}$

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

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

Барьеры [ править ]

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

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

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

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

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

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

Стоимость алгоритма BSP [ править ]

Стоимость супершага определяется как сумма трех членов; стоимость самого длительного локального вычисления, стоимость глобальной связи между процессорами и стоимость барьерной синхронизации в конце супершага. Стоимость одного супершага для процессоров: ${\ displaystyle p}$

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

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

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

Расширения и способы использования [ править ]

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

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

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

См. Также [ править ]

Автоматическое взаимное исключение
Апач Хама
Apache Giraph
Компьютерный кластер
Параллельные вычисления
Параллелизм
Программирование потока данных
Грид-вычисления
Машина LogP
Параллельные вычисления
Модель параллельного программирования
Научный Питон
Массовое синхронное параллельное машинное обучение

Ссылки [ править ]

^ a b c Лесли Г. Валиант, Модель моста для параллельных вычислений, Сообщения ACM, том 33, выпуск 8, август 1990 г. [1]
^ a b Valiant, LG (2011). Модель моста для многоядерных вычислений. Журнал компьютерных и системных наук, 77 (1), 154-166 [2]
^ Модель моста для высокопроизводительных облачных вычислений Билла Макколла на 18-й конференции SIAM по параллельной обработке для научных вычислений (2018 г.), http://meetings.siam.org/sess/dsp_talk.cfm?p=88973 Архивировано 12декабря2019 г. 11 у Wayback Machine .
Перейти ↑ Alpert, R., & Philbin, J. (1997). cBSP: синхронизация с нулевой стоимостью в модифицированной модели BSP. Исследовательский институт NEC, улица Независимости, 4, Принстон, штат Нью-Джерси, 8540, [3] .
^ а б Апач Хама
^ BSPlib
^ Прегель
^ Библиотека BSP (PUB) Университета Падерборна - Дизайн, реализация и производительность Институт Хайнца Никсдорфа, Департамент компьютерных наук, Университет Падерборна, Германия, технический отчет. Архивировано 05 июня 2001 г. на Wayback Machine .
↑ Джонатан Хилл: Набор инструментов Oxford BSP , 1998.
^ Wijnand J. Suijlen: BSPonMPI , 2006.
^ MulticoreBSP для C: высокопроизводительная библиотека для параллельного программирования с разделяемой памятью, написанная А. Н. Изельманом, Р. Х. Бисселингом, Д. Рузом и К. Меербергеном в Международном журнале параллельного программирования, в печати (2013), doi: 10.1109 / TPDS. 2013.31 .
^ Объектно-ориентированная массовая синхронная параллельная библиотека для многоядерного программирования от А. Н. Изельмана и Роба Х. Бисселинга в параллелизме и вычислениях: практика и опыт 24 (5), стр. 533-553 (2012), DOI: 10.1002 / cpe.1843 .

Внешние ссылки [ править ]

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

[CACM_Valiant-1] Лесли Г. Валиант, Модель моста для параллельных вычислений, Сообщения ACM, том 33, выпуск 8, август 1990 г. [1]

[JCSS_Valiant-2] Valiant, LG (2011). Модель моста для многоядерных вычислений. Журнал компьютерных и системных наук, 77 (1), 154-166 [2]

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

[Alpert-4] Перейти ↑ Alpert, R., & Philbin, J. (1997). cBSP: синхронизация с нулевой стоимостью в модифицированной модели BSP. Исследовательский институт NEC, улица Независимости, 4, Принстон, штат Нью-Джерси, 8540, [3] .

[hama-5] а б Апач Хама

[6] BSPlib

[7] Прегель

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

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

[10] Wijnand J. Suijlen: BSPonMPI , 2006.

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

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

[1]