Все ко всем (параллельный шаблон) - Википедия - All-to-all (parallel pattern)

Визуализация для всеобщего взаимодействия с четырьмя процессорами и m = 1.

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

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

Количество раундов обмена данными и общий объем обмена данными являются показателями для оценки качества универсального алгоритма. В этой статье мы рассматриваем однопортовый полнодуплексный компьютер. На такой машине для полного алгоритма требуется как минимум раунды общения. Далее минимум единиц данных передается. Оптимального для обоих этих мер нельзя достичь одновременно.[1]

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

Универсальные алгоритмы на основе топологии

Визуализация комплексного алгоритма в кольцевой топологии.
Визуализация комплексного алгоритма в сеточной топологии.

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

Гиперкуб

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

Звенеть

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

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

Сетка

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

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

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

Визуализация однофакторного алгоритма.

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

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

  // p odd: // индекс pe   для i: = от 0 до p-1 обмениваться данными с PE 
  // четное p: // индекс pe   для i: = от 0 до p-2 на холостом ходу: =   если j = p-1, то обмениваться данными с PE в режиме ожидания, иначе если j = в режиме ожидания, то обмениваться данными с pe p-1, иначе обмениваться данными с PE 

Алгоритм ведет себя по-разному, независимо от того, четно или нечетно p. Если p нечетное, на каждой итерации один процессор простаивает. При четном p этот неработающий процессор связывается с процессором с индексом p-1. Общее затраченное время составляет для четного p, и для нечетного p соответственно.

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

Рекомендации

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