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

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

• 1 История
• 2 Модель
• 3 Связь
• 4 Барьеры
• 5 Стоимость алгоритма BSP
• 6 Расширения и использование
• 7 См. Также
• 8 Ссылки
• 9 Внешние ссылки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$W\; +\; H\; g\; +\; S\; l\; знак\; равно\; \sum \; s\; =\; 1\; S\; ws\; +\; g\; \sum \; s\; =\; 1\; S\; hs\; +\; S\; l\; \{\backslash \; displaystyle\; W\; +\; Hg\; +\; Sl\; =\; \backslash \; sum\; \_\; \{s\; =\; 1\}\; ^\; \{S\}\; w\_\; \{s\}\; +\; g\; \backslash \; sum\; \_\; \{s\; =\; 1\}\; ^\; \{S\}\; h\_\; \{s\}\; +\; Sl\}$, где $S\; \{\backslash \; displaystyle\; S\}$- количество супершаги.

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

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

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

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

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

• БД Skillicorn, Jonathan Hill, WF McColl, Вопросы и ответы о BSP (1996)
• BSP Worldwide
• документы, связанные с BSP
• (на французском языке) Bulk Synchronous Parallel ML ((на английском языке) официальный сайт )
• Apache Hama
• Apache Giraph
• Библиотека BSP Университета Падерборна
• BSPonMPI
• MulticoreBSP