Массовая синхронная параллель - Bulk synchronous parallel

В объемная синхронная параллель (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 рассматривает все коммуникационные действия супершага как одно целое и предполагает, что все отдельные сообщения, отправленные как часть этого модуля, имеют фиксированный размер.

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

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

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

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

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

Барьеры

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

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

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

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

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

Стоимость алгоритма BSP

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

${displaystyle max_ {i = 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 = сумма _ {s = 1} ^ {S} w_ {s} + gsum _ {s = 1} ^ {S} h_ {s} + Sl}$ где ${displaystyle S}$ количество супершагов.

${displaystyle W}$ , ${displaystyle H}$ , и ${displaystyle S}$ обычно моделируются как функции, которые зависят от размера проблемы. Эти три характеристики алгоритма BSP обычно описываются в терминах асимптотическая запись, например ${displaystyle Hin 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.

Смотрите также

внешняя ссылка

Д. Скилликорн, Джонатан Хилл, У. Ф. Макколл, Вопросы и ответы о BSP^{[постоянная мертвая ссылка ]} (1996)
BSP в мире
Документы, связанные с BSP
(На французском) Массовый синхронный параллельный ML ((по-английски) Официальный веб-сайт )
Apache Hama
Apache Giraph
Библиотека BSP Падерборнского университета
BSPonMPI
MulticoreBSP

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

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

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

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

[hama-5] а ^б Apache Hama

[6] BSPlib

[7] Pregel

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]