Все-всем (параллельная схема)

В вычислениях операция параллельных «все ко всем» (также известная как индексная операция или полный обмен ) — это коллективная операция , при которой каждый процессор отправляет индивидуальное сообщение каждому другому процессору.

Первоначально каждый процессор содержит p сообщений размером m каждое, и цель состоит в том, чтобы обменять i-е сообщение процессора j на j-е сообщение процессора i.

Количество раундов связи и общий объем связи являются мерами оценки качества алгоритма «все со всеми». В этой статье мы рассматриваем однопортовую полнодуплексную машину. На такой машине алгоритм «все ко всем» требует как минимум $\lceil \log _{2}n\rceil$ коммуникационные раунды. Далее минимум $\left\lceil m(n-1)\right\rceil$ передаются единицы данных. Оптимум по обеим этим мерам не может быть достигнут одновременно. ^[1]

В зависимости от топологии сети (полносвязная, гиперкуб , кольцо ) требуются разные алгоритмы «все-все».

Алгоритмы «все-всем», основанные на топологии

Мы рассматриваем однопортовую машину. Способ маршрутизации данных по сети зависит от ее базовой топологии. Мы рассмотрим алгоритмы «все-все» для распространенных сетевых топологий.

Гиперкуб

Гиперкуб — это топология сети, в которой два процессора имеют общую ссылку, если расстояние Хэмминга их индексов равно единице. Идея алгоритма «все-всем» заключается в объединении сообщений, принадлежащих одному субкубу, а затем их распределении.

Кольцо

Алгоритм «все ко всем» в кольцевой топологии очень интуитивно понятен. Первоначально процессор отправляет сообщение размера m(p-1) одному из своих соседей. Связь осуществляется в одном направлении на всех процессорах. Когда процессор получает сообщение, он извлекает принадлежащую ему часть и пересылает оставшуюся часть сообщения следующему соседу. После (p-1) раундов связи каждое сообщение доставляется по назначению.

Время, затрачиваемое этим алгоритмом, равно $(t_{s}+{\frac {1}{2}}t_{w}mp)(p-1)$ . ^[2] Здесь $t_{s}$ - начальная стоимость связи, и $t_{w}$ — стоимость передачи единицы данных. Этот срок можно дополнительно улучшить, когда половина сообщений отправляется в одну, а другая половина — в другую сторону. Таким образом, сообщения доходят до места назначения раньше.

сетка

Для сетки мы смотрим на ${\sqrt {p}}\times {\sqrt {p}}$ сетка. Этот алгоритм легко адаптируется для любой сетки. Алгоритм «все-всем» в сетке состоит из двух фаз связи. Сначала каждый процессор группирует сообщения в ${\sqrt {p}}$ группы, каждая из которых содержит ${\sqrt {p}}$ сообщения. Сообщения попадают в одну группу, если их процессоры назначения используют одну и ту же строку. Затем выполняется операция «все ко всем» среди строк. Теперь каждый процессор содержит всю необходимую информацию о процессорах в своем столбце. Опять же, сообщения необходимо переставить. После еще одной операции «все-всем», на этот раз в отношении столбцов, каждый процессор получает свои сообщения.

Общее время связи для этого алгоритма составляет $(2t_{s}+t_{w}mp)({\sqrt {p}}-1)$ . Кроме того, время локальной перестановки сообщений увеличивает общее время работы алгоритма.

1-факторный алгоритм

Опять же, мы рассматриваем однопортовую машину. Тривиальный алгоритм заключается в отправке (p-1) асинхронных сообщений в сеть для каждого процессора. Производительность этого алгоритма низкая, что связано с перегрузкой, возникающей из-за ширины сети пополам. ^[3] Более сложные алгоритмы объединяют сообщения, чтобы уменьшить количество операций отправки и попытаться контролировать перегрузку.

Для больших сообщений стоимость запуска невелика по сравнению со стоимостью передачи полезной нагрузки. Быстрее отправлять сообщения непосредственно по назначению. В следующем алгоритме алгоритм «все ко всем» выполняется с использованием (p-1) маршрутизации «один к одному».

// p odd:
// pe index  $j\in \{0,\dots ,p-1\}$ 
for i := 0 to p-1 do
    Exchange data with PE  $(i-j)\,\mod \,p$

// p even:
// pe index  $j\in \{0,\dots ,p-1\}$ 
for i := 0 to p-2 do
    idle :=  ${\frac {p}{2}}i\,\mod \,(p-1)$ 
    if j = p-1 then
        exchange data with PE idle
    else
        if j = idle then
            exchange data with pe p-1
        else
            exchange data with PE  $(i-j)mod(p-1)$

Алгоритм ведет себя по-разному независимо от того, является ли p нечетным или четным. Если p нечетно, на каждой итерации один процессор простаивает. При четном p этот простаивающий процессор связывается с процессором с индексом p-1. Общее время, затраченное на $(p-1)(t_{s}+t_{w}m)$ для четного p, и $p(t_{s}+t_{w}m)$ для нечетного p соответственно.

Вместо объединения процессора j с процессором $(i-j){\bmod {p}}$ на итерации i мы также можем использовать исключающее ИЛИ j и i для определения отображения. Этот подход требует, чтобы p было степенью двойки. В зависимости от базовой топологии сети один подход может быть лучше другого. Подход «исключающее или» предпочтительнее при выполнении попарных маршрутизаций «один к одному» в гиперкубе или толстом дереве. ^[4]

Ссылки

^ Брук, Иегошуа; Хо, Цзин-Тянь; Кипнис, Шломо; Уэзерсби, Деррик (1997). «Эффективные алгоритмы комплексной связи в многопортовых системах передачи сообщений» (PDF) . Транзакции IEEE в параллельных и распределенных системах . 8 (11): 1143–1156. дои : 10.1109/71.642949 .
^ Грама, Анант (2003). Введение в параллельные вычисления .
^ Хамбруш, Сюзанна Э .; Хамид, Фарук; Хохар, Ашфак А. (май 1995 г.). «Коммуникационные операции на крупнозернистых сетчатых архитектурах» . Параллельные вычисления . 21 (5): 731–751. дои : 10.1016/0167-8191(94)00110-В .
^ Тхакур, Раджив; Чоудхари, Алок (26–29 апреля 1994 г.). Общение «все со всеми» в сетках с маршрутизацией «червоточины» . Материалы 8-го Международного симпозиума по параллельной обработке. Канкун, Мексика.

[1] Брук, Иегошуа; Хо, Цзин-Тянь; Кипнис, Шломо; Уэзерсби, Деррик (1997). «Эффективные алгоритмы комплексной связи в многопортовых системах передачи сообщений» (PDF) . Транзакции IEEE в параллельных и распределенных системах . 8 (11): 1143–1156. дои : 10.1109/71.642949 .

[2] Грама, Анант (2003). Введение в параллельные вычисления .

[3] Хамбруш, Сюзанна Э .; Хамид, Фарук; Хохар, Ашфак А. (май 1995 г.). «Коммуникационные операции на крупнозернистых сетчатых архитектурах» . Параллельные вычисления . 21 (5): 731–751. дои : 10.1016/0167-8191(94)00110-В .

[4] Тхакур, Раджив; Чоудхари, Алок (26–29 апреля 1994 г.). Общение «все со всеми» в сетках с маршрутизацией «червоточины» . Материалы 8-го Международного симпозиума по параллельной обработке. Канкун, Мексика.

[1]

[2]

[3]

[4]