Коллективная операция

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

Реализация коллективных операций обеспечивается интерфейсом передачи сообщений. ^[1] (МПИ).

Определения

Во всех асимптотических функциях времени выполнения мы обозначаем задержку $\alpha$ (или время запуска каждого сообщения, независимо от размера сообщения), стоимость связи за слово $\beta$ , количество процессоров $p$ и размер ввода на узел $n$ . В тех случаях, когда у нас есть начальные сообщения на более чем одном узле, мы предполагаем, что все локальные сообщения имеют одинаковый размер. Для обращения к отдельным процессорам мы используем $p_{i}\in \{p_{0},p_{1},\dots ,p_{p-1}\}$ .

Если у нас нет равного распределения, т.е. узла $p_{i}$ имеет сообщение размера $n_{i}$ , мы получаем верхнюю границу времени выполнения, установив $n=\max(n_{0},n_{1},\dots ,n_{p-1})$ .

модель распределенной памяти Предполагается . Концепции аналогичны модели общей памяти . Однако системы с общей памятью могут обеспечивать аппаратную поддержку некоторых операций, таких как, широковещательная рассылка ( § Broadcast ), что обеспечивает удобное одновременное чтение. например, ^[2] Таким образом, могут стать доступны новые алгоритмические возможности.

Транслировать

Схема трансляции ^[3] используется для распределения данных от одного процессора ко всем процессорам, что часто необходимо в параллельных программах SPMD для распределения входных или глобальных значений. Трансляцию можно интерпретировать как обратную версию шаблона сокращения ( § Сокращение ). Изначально только root $r$ с $id$ $0$ сохраняет сообщение $m$ . Во время трансляции $m$ отправляется на остальные процессоры, так что в конечном итоге $m$ доступен для всех процессоров.

Поскольку реализация посредством последовательного цикла for с $p-1$ итерации становятся узким местом, подход «разделяй и властвуй» широко распространен . Одна из возможностей — использовать биномиальную древовидную структуру с требованием, чтобы $p$ должна быть степенью двойки. Когда блок обработки отвечает за отправку $m$ в обрабатывающие подразделения $i..j$ , он отправляет $m$ в блок обработки $\left\lceil (i+j)/2\right\rceil$ и делегирует ответственность за блоки обработки $\left\lceil (i+j)/2\right\rceil ..j$ перед ним, в то время как его собственная ответственность сводится к $i..\left\lceil (i+j)/2\right\rceil -1$ .

Биномиальные деревья имеют проблемы с длинными сообщениями. $m$ . Приемный блок $m$ может распространять сообщение другим устройствам только после получения всего сообщения. При этом сеть связи не используется. конвейерная обработка бинарных деревьев , где Поэтому используется $m$ разбивается на массив $k$ пакеты размером $\left\lceil n/k\right\rceil$ . Затем пакеты передаются один за другим, что обеспечивает быстрое распространение данных в сети связи.

Конвейерная трансляция по сбалансированному двоичному дереву возможна в ${\mathcal {O}}(\alpha \log p+\beta n)$ , тогда как для неконвейерного случая требуется ${\mathcal {O}}((\alpha +\beta n)\log p)$ расходы.

Уменьшать

Есть три квадрата, выровненных вертикально слева, и три квадрата, выровненных вертикально справа. Между двумя столбцами помещается круг с буквой f внутри. Три сплошные линии соединяют круг с тремя левыми квадратами. Одна сплошная линия соединяет круг и верхний правый квадрат. Буквы а, б и в написаны в левых квадратах от большей к младшей. Буква альфа написана в правом верхнем квадрате. — Информационный поток операции сокращения выполняется на трех узлах. f — ассоциативный оператор, а α — результат приведения.

Шаблон сокращения ^[4] используется для сбора данных или частичных результатов от разных блоков обработки и объединения их в глобальный результат выбранным оператором. Данный $p$ процессоры, сообщения $m_{i}$ находится на процессоре $p_{i}$ изначально. Все $m_{i}$ агрегируются по $\otimes$ и результат в конечном итоге сохраняется на $p_{0}$ . Оператор сокращения $\otimes$ должен быть как минимум ассоциативным. Некоторые алгоритмы требуют коммутативного оператора с нейтральным элементом. Операторы любят $sum$ , $min$ , $max$ являются общими.

Соображения по реализации аналогичны широковещанию ( § Broadcast ). Для конвейерной обработки двоичных деревьев сообщение должно быть представлено как вектор меньшего объекта для покомпонентного сокращения.

Конвейерное сокращение сбалансированного двоичного дерева возможно в ${\mathcal {O}}(\alpha \log p+\beta n)$ .

Все-Уменьшить

Шаблон полного сокращения ^[5] (также называемый allreduce) используется, если результат операции сокращения ( § Сокращение ) должен быть распространен на все процессоры. Данный $p$ процессоры, сообщения $m_{i}$ находится на процессоре $p_{i}$ изначально. Все $m_{i}$ агрегируются оператором $\otimes$ и результат в конечном итоге сохраняется на всех $p_{i}$ . Аналог операции сокращения, оператор $\otimes$ должно быть как минимум ассоциативным.

All-reduce можно интерпретировать как операцию сокращения с последующей трансляцией ( § Broadcast ). Для длинных сообщений подойдет соответствующая реализация, тогда как для коротких сообщений задержку можно уменьшить, используя топологию гиперкуба ( Hypercube (pattern communication) § All-Gather/All-Reduce ), если $p$ это степень двойки. All-reduce также можно реализовать с помощью алгоритма «бабочка» и добиться оптимальной задержки и пропускной способности. ^[6]

Полное сокращение возможно в ${\mathcal {O}}(\alpha \log p+\beta n)$ , поскольку сокращение и трансляция возможны в ${\mathcal {O}}(\alpha \log p+\beta n)$ с конвейеризацией на сбалансированных двоичных деревьях . All-reduce, реализованный с помощью алгоритма-бабочки, обеспечивает такое же асимптотическое время выполнения.

Префикс-Сумма/Сканирование

Префикс-сумма или операция сканирования ^[7] используется для сбора данных или частичных результатов из различных блоков обработки и для вычисления оператором промежуточных результатов, которые сохраняются в этих блоках обработки. Ее можно рассматривать как обобщение операции сокращения ( § Редукция ). Данный $p$ процессоры, сообщения $m_{i}$ находится на процессоре $p_{i}$ . Оператор $\otimes$ должен быть как минимум ассоциативным, тогда как некоторые алгоритмы требуют также коммутативного оператора и нейтрального элемента. Общие операторы: $sum$ , $min$ и $max$ . В конечном итоге блок обработки $p_{i}$ сохраняет сумму префикса $\otimes _{i'<=i}$ $m_{i'}$ . В случае так называемой суммы эксклюзивного префикса блок обработки $p_{i}$ сохраняет сумму префикса $\otimes _{i'<i}$ $m_{i'}$ . Некоторые алгоритмы требуют хранения общей суммы в каждом процессоре в дополнение к суммам префиксов.

Для коротких сообщений этого можно достичь с помощью топологии гиперкуба, если $p$ это степень двойки. Для длинных сообщений топология гиперкуба ( Гиперкуб (шаблон связи) § Сумма префиксов , Сумма префиксов § Распределенная память: алгоритм гиперкуба ) не подходит, поскольку все процессоры активны на каждом этапе и поэтому конвейерную обработку использовать нельзя. Топология двоичного дерева лучше подходит для произвольных $p$ и длинные сообщения ( сумма префиксов § Большие размеры сообщений: конвейерное двоичное дерево ).

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

Конвейерная сумма префиксов в двоичном дереве возможна в ${\mathcal {O}}(\alpha \log p+\beta n)$ .

Барьер

Барьер ^[8] как коллективная операция является обобщением концепции барьера , которую можно использовать в распределенных вычислениях. Когда процессор вызывает барьер, он ждет, пока все остальные процессоры также не вызовут барьер. Таким образом, барьер используется для достижения глобальной синхронизации в распределенных вычислениях.

Один из способов реализации барьера — вызвать all-reduce ( § All-Reduce ) с пустым/фиктивным операндом. Мы знаем, что время выполнения All-reduce ${\mathcal {O}}(\alpha \log p+\beta n)$ . Использование фиктивного операнда уменьшает размер. $n$ к постоянному коэффициенту и приводит к времени выполнения ${\mathcal {O}}(\alpha \log p)$ .

Собирать

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

Схема сбора информации ^[9] используется для хранения данных всех процессоров в одном процессоре. Данный $p$ процессоры, сообщения $m_{i}$ на процессорном блоке $p_{i}$ . Для фиксированного процессора $p_{j}$ , мы хотим сохранить сообщение $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ на $p_{j}$ . Сбор можно рассматривать как операцию сокращения ( § Редукция ), в которой используется оператор конкатенации. Это работает благодаря тому, что конкатенация ассоциативна. Используя тот же алгоритм сокращения биномиального дерева, мы получаем время выполнения ${\mathcal {O}}(\alpha \log p+\beta pn)$ . Мы видим, что асимптотическое время выполнения аналогично асимптотическому времени выполнения сокращения ${\mathcal {O}}(\alpha \log p+\beta n)$ , но с добавлением к слагаемому множителя p $\beta n$ . Этот дополнительный фактор обусловлен тем, что размер сообщения увеличивается на каждом этапе по мере объединения сообщений. Сравните это, чтобы уменьшить размер сообщения, который является константой для таких операторов, как $min$ .

Всесобрать

Есть три квадрата, выровненных по вертикали слева, и три прямоугольника, выровненных по вертикали справа. Три пунктирные линии соединяют верхний левый квадрат с верхним правым прямоугольником, средний левый квадрат со средним правым прямоугольником и нижний левый квадрат с нижним правым прямоугольником. Две сплошные линии соединяют средний и нижний левый квадраты с верхним правым прямоугольником. Две сплошные линии соединяют верхний и нижний левый квадрат со средним правым прямоугольником. Две сплошные линии соединяют верхний и средний левый квадраты с нижним правым прямоугольником. Буквы а, б и в написаны в левых квадратах от большей к младшей. Буквы а, б и в написаны во всех правых прямоугольниках подряд. — Информационный поток операции All-Gather выполняется на трёх узлах.

Схема всеобщего общения ^[9] используется для сбора данных со всех блоков обработки и хранения собранных данных на всех блоках обработки. Данный $p$ блоки обработки $p_{i}$ , сообщение $m_{i}$ изначально хранится на $p_{i}$ , мы хотим сохранить сообщение $m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ на каждом $p_{j}$ .

Это можно рассматривать по-разному. Первый представляет собой операцию полного сокращения ( § All-Reduce ) с конкатенацией в качестве оператора, точно так же, как сбор может быть представлен с помощью сокращения. Второй представляет собой операцию сбора, за которой следует широковещательная рассылка нового сообщения размером $pn$ . При этом мы видим, что все собирается ${\mathcal {O}}(\alpha \log p+\beta pn)$ возможно.

Разброс

Есть три прямоугольника, выровненных по вертикали слева, и три квадрата, выровненных по вертикали справа. Пунктирная линия соединяет верхний левый прямоугольник с верхним правым квадратом. Две сплошные линии соединяют верхний левый прямоугольник со средним и нижним правым квадратами. Буквы c, b и a написаны в верхнем левом прямоугольнике подряд. Буквы а, б и в написаны в правых квадратах от большей к младшей. — Информационный поток операции Scatter выполняется на трёх узлах.

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

Данный $p$ блоки обработки $p_{i}$ , фиксированный процессор $p_{j}$ который содержит сообщение $m=m_{1}\cdot m_{2}\cdot \ldots \cdot m_{p}$ . Мы хотим передать сообщение $m_{i}$ на $p_{i}$ . Применяются те же проблемы реализации, что и для сбора ( § Gather ). Это приводит к оптимальному времени работы в ${\mathcal {O}}(\alpha \log p+\beta pn)$ .

Все на все

Все на все ^[11] является наиболее общей моделью общения. Для $0\leq i,j<p$ , сообщение $m_{i,j}$ это сообщение, которое изначально хранится на узле $i$ и должен быть доставлен на узел $j$ . Мы можем выражать все примитивы связи, не использующие операторы, через все-всем. Например, трансляция сообщения $m$ из узла $p_{k}$ эмулируется установкой $m_{i,j}=m$ для $i=k$ и настройка $m_{l,j}$ пусто для $l\neq k$ .

Предполагая, что у нас есть полностью подключенная сеть, наилучшее время работы для всех-всех находится в ${\mathcal {O}}(p(\alpha +\beta n))$ . Это достигается за счет $p$ раунды прямого обмена сообщениями. Для $p$ степень 2, в раунде связи $k$ , узел $p_{i}$ обменивается сообщениями с узлом $p_{j},j=i\oplus k$ .

Если размер сообщения невелик и при передаче данных преобладает задержка, для распределения сообщений во времени можно использовать алгоритм гиперкуба. ${\mathcal {O}}(\log p(\alpha +\beta pn))$ .

Есть три прямоугольника, выровненных по вертикали слева, и три прямоугольника, выровненных по вертикали справа. Прямоугольники в три раза выше ширины. Члены a1, a2 и a3 написаны в верхнем левом прямоугольнике один под другим. Термины b1, b2 и b3 написаны в левом среднем прямоугольнике один под другим. Термины c1, c2 и c3 написаны в нижнем левом прямоугольнике один под другим. Члены a1, b1 и c1 написаны в правом верхнем прямоугольнике друг под другом. Члены a2, b2 и c2 написаны в среднем правом прямоугольнике один под другим. Члены a3, b3 и c3 написаны в правом нижнем прямоугольнике друг под другом. Пунктирная линия соединяет a1 из верхнего левого прямоугольника и a1 из верхнего правого прямоугольника. Пунктирная линия соединяет b2 из среднего левого прямоугольника и b2 из среднего правого прямоугольника. Пунктирная линия соединяет c3 из нижнего левого прямоугольника и c3 из нижнего правого прямоугольника. Сплошные линии соединяют другие соответствующие члены между левым и правым прямоугольниками. — Информационный поток операции «Все-всем» выполняется на трех узлах. Буквы обозначают узлы, а цифры обозначают элементы информации.

Обзор среды выполнения

Эта таблица ^[12] дает обзор наиболее известных асимптотических сред выполнения, предполагая, что у нас есть свободный выбор топологии сети.

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

На практике нам приходится приспосабливаться к доступным физическим топологиям, например, «стрекоза», «толстое дерево» , грид-сеть (ссылается и на другие топологии).

Дополнительная информация в разделе Топология сети .

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

Сложности, указанные в таблице, зависят от задержки $\alpha$ и стоимость связи за слово $\beta$ помимо количества процессоров $p$ и размер входного сообщения на узел $n$ . Столбцы # отправителей и # получателей представляют количество отправителей и получателей, участвующих в операции соответственно. В столбце # сообщений указано количество входных сообщений и поле «Вычисления?». Столбец указывает, выполняются ли какие-либо вычисления над сообщениями или сообщения просто доставляются без обработки. Сложность дает асимптотическую сложность оптимальной реализации во время выполнения при свободном выборе топологии.


Имя	# отправителей	# получателей	# сообщения	Расчеты?	Сложность
Транслировать	$1$	$p$	$1$	нет	${\mathcal {O}}(\alpha \log p+\beta n)$
Уменьшать	$p$	$1$	$p$	да	${\mathcal {O}}(\alpha \log p+\beta n)$
Все-уменьшить	$p$	$p$	$p$	да	${\mathcal {O}}(\alpha \log p+\beta n)$
Префиксная сумма	$p$	$p$	$p$	да	${\mathcal {O}}(\alpha \log p+\beta n)$
Барьер	$p$	$p$	$0$	нет	${\mathcal {O}}(\alpha \log p)$
Собирать	$p$	$1$	$p$	нет	${\mathcal {O}}(\alpha \log p+\beta pn)$
Всесобрать	$p$	$p$	$p$	нет	${\mathcal {O}}(\alpha \log p+\beta pn)$
Разброс	$1$	$p$	$p$	нет	${\mathcal {O}}(\alpha \log p+\beta pn)$
Все-Всем	$p$	$p$	$p^{2}$	нет	${\mathcal {O}}(\log p(\alpha +\beta pn))$ или ${\mathcal {O}}(p(\alpha +\beta n))$

Примечания

^ Коллективные операции интеркоммуникатора . Стандарт интерфейса передачи сообщений (MPI), глава 7.3.1. Отдел математики и информатики Аргоннской национальной лаборатории .
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, с. 395
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 396-401.
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 402-403.
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 403-404.
^ Юань, Синь (февраль 2009 г.). «Алгоритмы полного сокращения оптимальной пропускной способности для кластеров рабочих станций» (PDF) . Журнал параллельных и распределенных вычислений . 69 (2).
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 404-406.
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, с. 408
^ Перейти обратно: ^а ^б Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 412-413.
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, с. 413
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 413-418.
^ Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, с. 394

Ссылки

Сандерс, Питер ; Мельхорн, Курт ; Дитцфельбингер, Мартин; Дементьев, Роман (2019). Последовательные и параллельные алгоритмы и структуры данных — базовый набор инструментов . Springer Nature Switzerland AG. ISBN 978-3-030-25208-3 .

[1] Коллективные операции интеркоммуникатора . Стандарт интерфейса передачи сообщений (MPI), глава 7.3.1. Отдел математики и информатики Аргоннской национальной лаборатории .

[:1-2] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, с. 395

[:2-3] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 396-401.

[:3-4] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 402-403.

[:4-5] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 403-404.

[6] Юань, Синь (февраль 2009 г.). «Алгоритмы полного сокращения оптимальной пропускной способности для кластеров рабочих станций» (PDF) . Журнал параллельных и распределенных вычислений . 69 (2).

[:5-7] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 404-406.

[:6-8] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, с. 408

[:7-9] Перейти обратно: ^а ^б Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 412-413.

[:8-10] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, с. 413

[:9-11] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, стр. 413-418.

[:10-12] Сандерс, Мельхорн, Дитцфельбингер, Дементьев 2019, с. 394

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]