Гиперкуб (шаблон связи)

$d$ Трехмерный гиперкуб — это сетевая топология для параллельных компьютеров с $2^{d}$ элементы обработки. Топология позволяет эффективно реализовать некоторые базовые коммуникационные примитивы, такие как Broadcast , All- Ruce и Prefix sum . ^[1] Элементы обработки пронумерованы. $0$ через $2^{d}-1$ . Каждый обрабатывающий элемент соседствует с обрабатывающими элементами, номера которых отличаются одним и только одним битом. Алгоритмы, описанные на этой странице, эффективно используют эту структуру.

Схема алгоритма

Большинство коммуникационных примитивов, представленных в этой статье, имеют общий шаблон. ^[2] Первоначально каждый обрабатывающий элемент имеет одно сообщение, которое должно достичь всех остальных обрабатывающих элементов в ходе работы алгоритма. Следующий псевдокод описывает необходимые шаги связи. Таким образом, Initialization , Operation и Output являются заполнителями, которые зависят от данного коммуникационного примитива (см. следующий раздел).

Input: message  $m$ .
Output: depends on Initialization, Operation and Output.
Initialization
 $s:=m$ 
for  $0\leq k<d$  do
     $y:=i{\text{ XOR }}2^{k}$ 
    Send  $s$  to  $y$ 
    Receive  $m$  from  $y$ 
    Operation $(s,m)$ 
endfor
Output

Каждый обрабатывающий элемент перебирает своих соседей (выражение $i{\text{ XOR }}2^{k}$ отрицает $k$ -й бит $i$ двоичное представление, таким образом получая номера его соседей). На каждой итерации каждый обрабатывающий элемент обменивается сообщением с соседом и впоследствии обрабатывает полученное сообщение. Операция обработки зависит от примитива связи.

Примитивы связи

Префиксная сумма

В начале операции суммирования префиксов каждый обрабатывающий элемент $i$ владеет сообщением $m_{i}$ . Цель — вычислить $\bigoplus _{0\leq j\leq i}m_{j}$ , где $\oplus$ является ассоциативной операцией. Следующий псевдокод описывает алгоритм.

Input: message  $m_{i}$  of processor  $i$ .
Output: prefix sum  $\bigoplus _{0\leq j\leq i}m_{j}$  of processor  $i$ .
 $x:=m_{i}$  
 $\sigma :=m_{i}$ 
for  $0\leq k\leq d-1$  do
     $y:=i{\text{ XOR }}2^{k}$ 
    Send  $\sigma$  to  $y$ 
    Receive  $m$  from  $y$ 
     $\sigma :=\sigma \oplus m$ 
    if bit  $k$  in  $i$  is set then  $x:=x\oplus m$ 
endfor

Алгоритм работает следующим образом. Заметим, что гиперкубы размерности $d$ можно разбить на два гиперкуба размерности $d-1$ . Назовите субкуб, содержащий узлы с ведущим 0, как 0-субкуб, а субкуб, состоящий из узлов с ведущей 1, как 1-субкуб. После того, как оба субкуба вычислили сумму префикса, сумма по всем элементам в кубе с 0 субкубами должна быть добавлена к каждому элементу в кубе с 1 субкубом, поскольку каждый обрабатывающий элемент в кубе с 0 субкубами имеет более низкий ранг. чем обрабатывающие элементы в 1-субкубе. Псевдокод сохраняет сумму префикса в переменной $x$ и сумма по всем узлам субкуба в переменной $\sigma$ . Это позволяет всем узлам в кубе с 1 суб-юнитом получать сумму по кубу с 0-ю субтитровами на каждом этапе.

Это приводит к коэффициенту $\log p$ для $T_{\text{start}}$ и фактор $n\log p$ для $T_{\text{byte}}$ : $T(n,p)=(T_{\text{start}}+nT_{\text{byte}})\log p$ .

Все собрать/все уменьшить

Операции по сбору всех данных начинаются с того, что каждый элемент обработки имеет сообщение. $m_{i}$ . Цель операции состоит в том, чтобы каждый обрабатывающий элемент знал сообщения всех других обрабатывающих элементов, т.е. $x:=m_{0}\cdot m_{1}\dots m_{p}$ где $\cdot$ является конкатенация. Операцию можно реализовать по шаблону алгоритма.

Input: message  $x:=m_{i}$  at processing unit  $i$ .
Output: all messages  $m_{1}\cdot m_{2}\dots m_{p}$ .
 $x:=m_{i}$ 
for  $0\leq k<d$  do
     $y:=i{\text{ XOR }}2^{k}$ 
    Send  $x$  to  $y$ 
    Receive  $x'$  from  $y$ 
     $x:=x\cdot x'$ 
endfor

С каждой итерацией длина передаваемого сообщения удваивается. Это приводит к тому, что время выполнения $T(n,p)\approx \sum _{j=0}^{d-1}(T_{\text{start}}+n\cdot 2^{j}T_{\text{byte}})=\log(p)T_{\text{start}}+(p-1)nT_{\text{byte}}$ .

Тот же принцип можно применить к операциям All-Reduce , но вместо объединения сообщений выполняется операция сокращения двух сообщений. Итак, это операция сокращения , результат которой известен всем процессорам. По сравнению с обычной операцией сокращения, за которой следует широковещательная рассылка, All-Reduce в гиперкубах уменьшает количество шагов связи.

Все на все

Здесь каждый обрабатывающий элемент имеет уникальное сообщение для всех остальных обрабатывающих элементов.

Input: message  $m_{ij}$  at processing element  $i$  to processing element  $j$ .
for  $d>k\geq 0$  do
    Receive from processing element  $i{\text{ XOR }}2^{k}$ :
        all messages for my  $k$ -dimensional sub cube
    Send to processing element  $i{\text{ XOR }}2^{k}$ :
        all messages for its  $k$ -dimensional sub cube
endfor

С каждой итерацией сообщение приближается к месту назначения на одно измерение, если оно еще не пришло. Следовательно, все сообщения достигли цели не более чем через $d=\log {p}$ шаги. На каждом шагу, $p/2$ сообщения отправляются: в первой итерации половина сообщений не предназначена для собственного субкуба. На каждом последующем шаге субкуб становится вдвое меньше предыдущего, но на предыдущем шаге от другого обрабатывающего элемента поступило ровно такое же количество сообщений.

Это приводит к тому, что время выполнения $T(n,p)\approx \log {p}(T_{\text{start}}+{\frac {p}{2}}nT_{\text{byte}})$ .

ESBT-трансляция

Алгоритм ESBT-broadcast (Edge-disjoint Spanning Binomial Tree) ^[3] — это конвейерный алгоритм широковещательной передачи с оптимальным временем выполнения для кластеров с топологией сети гиперкуб. Алгоритм встраивает $d$ биномиальные деревья, не пересекающиеся по ребрам в гиперкубе, такие, что каждый сосед обрабатывающего элемента $0$ является корнем остовного биномиального дерева на $2^{d}-1$ узлы. Чтобы передать сообщение, исходный узел разбивает свое сообщение на $k$ куски одинакового размера и циклически отправляет их в корни биномиальных деревьев. Получив фрагмент, биномиальные деревья транслируют его.

Время выполнения

На каждом этапе исходный узел отправляет один из своих $k$ куски в биномиальное дерево. Трансляция фрагмента внутри биномиального дерева занимает $d$ шаги. Таким образом, требуется $k$ шаги по распределению всех кусков и дополнительно $d$ шагов до тех пор, пока не завершится последняя трансляция биномиального дерева, что приведет к $k+d$ шаги в целом. Таким образом, время выполнения сообщения длиной $n$ является $T(n,p,k)=\left({\frac {n}{k}}T_{\text{byte}}+T_{\text{start}}\right)(k+d)$ . С оптимальным размером куска $k^{*}={\sqrt {\frac {nd\cdot T_{\text{byte}}}{T_{\text{start}}}}}$ , оптимальное время работы алгоритма равно $T^{*}(n,p)=n\cdot T_{\text{byte}}+\log(p)\cdot T_{\text{start}}+{\sqrt {n\log(p)\cdot T_{\text{start}}\cdot T_{\text{byte}}}}$ .

Построение биномиальных деревьев

А $3$ -мерные гиперкубы со встроенными тремя ESBT.

В этом разделе описывается, как систематически строить биномиальные деревья. Сначала построим одно биномиальное остовное дерево von $2^{d}$ узлы следующим образом. Пронумеруйте узлы из $0$ к $2^{d}-1$ и рассмотрим их двоичное представление. Затем дочерние элементы каждого узла получаются путем отрицания одиночных ведущих нулей. В результате получается одно биномиальное остовное дерево. Чтобы получить $d$ копии дерева, не пересекающиеся по ребрам, переместите и поверните узлы: для $k$ -я копия дерева, примените операцию XOR с $2^{k}$ к каждому узлу. Затем поверните вправо все узлы на $k$ цифры. Полученные биномиальные деревья не пересекаются по ребрам и, следовательно, удовлетворяют требованиям алгоритма ESBT-вещания.

Ссылки

^ Грама, А. (2003). Введение в параллельные вычисления. Эддисон Уэсли; Ауфляж: 2-е изд. ISBN 978-0201648652 .
^ Фостер, И. (1995). Проектирование и создание параллельных программ: концепции и инструменты для параллельной разработки программного обеспечения. Эддисон Уэсли; ISBN 0201575949 .
^ Джонсон, СЛ; Хо, К.-Т. (1989). «Оптимальное вещание и персонализированное общение в гиперкубах». Транзакции IEEE на компьютерах . 38 (9): 1249–1268. дои : 10.1109/12.29465 . ISSN 0018-9340 .

[1] Грама, А. (2003). Введение в параллельные вычисления. Эддисон Уэсли; Ауфляж: 2-е изд. ISBN 978-0201648652 .

[2] Фостер, И. (1995). Проектирование и создание параллельных программ: концепции и инструменты для параллельной разработки программного обеспечения. Эддисон Уэсли; ISBN 0201575949 .

[3] Джонсон, СЛ; Хо, К.-Т. (1989). «Оптимальное вещание и персонализированное общение в гиперкубах». Транзакции IEEE на компьютерах . 38 (9): 1249–1268. дои : 10.1109/12.29465 . ISSN 0018-9340 .

[1]

[2]

[3]