Автор: Цзиньхуэй Юань; Перевод Цзяли Шен, Юшань Чжан

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

В этой статье мы раскроем математическое свойство коллективных коммуникационных операций, проанализировав случай all-reduce, распространенный в параллелизме данных.

1 Что такое all-reduce

Как показано на рис. 1, имеется четыре устройства, каждое с одной матрицей (для простоты каждая строка в этих матрицах содержит только один элемент). А all-reduce — это операция, которая суммирует входное значение одной и той же строки на разных устройствах и возвращает результирующее значение в соответствующую строку.

Как показано на рис. 2, операцию all-reduce можно также выполнить с помощью еще двух основных операций коллективной связи: reduce-scatter и all-gather. Кроме того, кольцевая связь может эффективно реализовывать операции уменьшения рассеяния и сбора всех данных, как показано на диаграмме ниже.

2 Реализация операции уменьшения разброса и ее свойство

Как видно на рис. 2, операция уменьшения разброса — это операция, которая уменьшает входные значения между устройствами, при этом каждое устройство получает только часть результата. Перед дальнейшим обсуждением нам необходимо определить несколько символов.

Предположим, что имеется p устройств (p=4 в приведенном выше примере), а размер матрицы равен V. Тогда после операции уменьшения разброса каждое устройство получит порцию данных размером V/p.

Если связь между устройствами является дуплексной, а ее пропускная способность равна β, то пропускная способность ввода/вывода каждого устройства может как достигать β, так и сумма пропускной способности ввода/вывода всех устройств также будет равна p×β.

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

Всего имеется p устройств, и данные на каждом устройстве разделены на p частей, поэтому кольцевая операция уменьшения рассеяния должна выполнять p-1 шагов.

Шаг 1: Каждое устройство берет на себя управление одним фрагментом данных размером V/p и отправляет этот фрагмент данных устройству слева от него. Как показано на рисунке 3, устройство 1 берет на себя управление блоком данных 2 и отправляет его на устройство 0 (то есть устройство 4), устройство 2 берет на себя управление блоком данных 3 и отправляет его на устройство 1, а остальные устройства выполняют то же самое.

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

Шаг 2: Устройство 1 отправляет совокупный фрагмент данных 3 на устройство 0 (то есть устройство 4), устройство 2 отправляет совокупный фрагмент данных 4 на устройство 1, а остальные устройства работают одинаково.

Каждое устройство получает данные от устройства справа и интегрирует данные в свой исходный соответствующий фрагмент данных (тогда цвет фрагмента данных становится темнее, чем на шаге 1).

Шаг 3: устройство 1 отправляет совокупный фрагмент данных 4 на устройство 0 (то есть устройство 4), устройство 2 отправляет совокупный фрагмент данных 1 на устройство 1, а остальные устройства делают то же самое.

Каждое устройство получает данные от устройства справа от него и интегрирует вновь полученные данные в свой ранее соответствующий фрагмент данных (и цвет фрагмента данных становится темнее, чем на шаге 2).

После шагов p-1 каждому устройству принадлежит часть данных, которая сокращается в соответствующей позиции всех устройств. В течение всего процесса объем данных, отправляемых и получаемых каждым устройством, равен (p-1)V/p, а выходная или входная полоса пропускания равна β, поэтому время, необходимое для процесса, составляет (p-1) В/рβ. Если p достаточно велико, время завершения будет близко к V/β. Что удивительно, так это то, что время завершения не имеет отношения к количеству устройств p. Конечно, количество данных, передаваемых между всеми устройствами, составляет (p-1)V, что пропорционально p, количеству устройств.

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

3 Реализация all-gather и его свойства

После выполнения сокращения-разброса, все-уменьшения может быть реализовано через процесс все-сбора, а все-сбор также может быть реализовано с помощью алгоритма кольцевой связи.

На рис. 4 показан процесс реализации кольцевой сборки. Стоит отметить, что время его связи и трафик точно такие же, как и в reduce-scatter: время, необходимое для процесса, равно (p-1)V/pβ. Если p достаточно велико, время завершения близко к V/β, что не имеет отношения к p, количеству устройств. Конечно, объем данных, передаваемых между всеми устройствами, равен (p-1)V, что пропорционально p, количеству устройств p.

Однако в алгоритме уменьшения разброса V относится к размеру данных всей матрицы, т. е. размеру данных входной матрицы при уменьшении разброса и объему данных выходной матрицы при полном сборе.

4 Взаимосвязь между коммуникационным трафиком и избыточной памятью

Выше анализируется только коммуникационный трафик, но не потребление памяти устройства. Возьмем в качестве примера рис. 3. Размер входной матрицы в каждом устройстве равен V, но после операции уменьшения разброса каждому устройству требуется только V/p пространства памяти, что означает (p-1)V/p пространства. является избыточным. Всего имеется p устройств, поэтому в каждом кластере можно сохранить (p-1)V памяти. Обратите внимание, что избыточная память в каждом устройстве такая же, как коммуникационный трафик в каждом устройстве, а избыточная память во всех устройствах такая же, как и общий коммуникационный трафик во всех устройствах.

Возьмите рисунок 4 в качестве примера. Размер входной матрицы на каждом устройстве равен V/p, но после операции полного сбора память, необходимая для каждого устройства, составляет V, а размер и значение матрицы на каждом устройстве идентичны. Другими словами, после операции all-gather разные устройства сохраняют одни и те же данные, что приводит к избыточности памяти. Точно так же объем избыточной памяти на каждом устройстве равен объему коммуникационного трафика на каждом устройстве, поэтому избыточная память на всех устройствах также равна общему коммуникационному трафику.

Конечно, эквивалентность резервирования и трафика связи не случайна. Именно связь вызывает избыточность данных между устройствами.

Таким образом, при сохранении V без изменений увеличьте p, количество устройств (назовем p параллельной шириной коллективной связи), и пропорционально возрастет коммуникационный трафик между всеми устройствами, а избыточная память во всех устройствах уменьшится. также увеличиваются пропорционально. Конечно, время, необходимое для завершения определенного коллективного сообщения, почти не имеет отношения к p, ширине параллелизма.

Таким образом, увеличение ширины параллели p — палка о двух концах. С одной стороны, это заставляет каждое устройство обрабатывать меньше данных, то есть V/p, тем самым сокращая время вычислений. Но, с другой стороны, это требует большей пропускной способности связи (p-1)V и большего объема памяти (p-1)V.

5 Оптимальность кольцевого алгоритма

Мы подняли вопрос выше: можете ли вы придумать реализацию коллективного алгоритма лучше, чем кольцевой алгоритм? Ответ заключается в том, что теоретически лучшего алгоритма не существует.

Мы проанализировали, что для завершения сокращения-разброса и сбора всех устройств каждое устройство должно как минимум отправлять (и одновременно получать) объем данных (p-1)V/p. Независимо от того, какой алгоритм используется, объем данных не может быть меньше.

Какое самое короткое время потребуется при таком объеме данных? Выходная полоса пропускания равна β, поэтому кратчайшее время, необходимое устройству для отправки данных, составляет (p-1)V/pβ, что также является временем, необходимым для кольцевого алгоритма.

Конечно, время связи здесь включает только пропускную способность передачи, но не задержку в каждой передаче. Когда объем данных V относительно велик, задержкой можно пренебречь, и приведенный выше анализ верен.

Но когда V чрезвычайно мало или количество устройств p чрезвычайно велико, полоса пропускания β становится менее важной, а задержка становится более важной. В этой ситуации нашим первым выбором будет древовидный алгоритм, а не кольцевой. Вот почему NVIDIA NCCL реализует алгоритмы как кольцевого, так и двойного дерева.

Статьи по теме:

  1. Как повысить эффективность вычислений для PReLU в CUDA — оптимизация производительности OneFlow
  2. Вышел OneFlow v0.7.0!

Добро пожаловать в OneFlow наGitHub и следите за нами в Twitter и LinkedIn.

Кроме того, приглашаем присоединиться к нашей группе Discord, чтобы обсуждать и задавать вопросы, связанные с OneFlow, а также общаться с участниками и пользователями OneFlow по всему миру.