Конспект: коллективные операции и распределённая память

Понятия

Распределённая память - у каждого узла своя память, обмен - сообщениями. Сообщение длины n стоит α + β · n: α - задержка, β - время на байт. Узел за раунд отправляет одно и принимает одно.

Коллективные операции: рассылка (одно → все), reduce (все → один со сложением), all-reduce (сумма у всех), reduce-scatter (каждому - сумма своего куска), all-gather (каждому - все куски), all-to-all (каждый каждому - свою порцию).

Кража работы - у каждого рабочего дек; владелец берёт с конца, вор - с начала у случайной жертвы.

Что унести

ЦЕНА СООБЩЕНИЙ
порог n* = α / β: короче - задержка, длиннее - передача
α = 20 мкс, 10 ГБ/с: n* = 200 КБ
1 МБ одним сообщением - 120 мкс, тысячей по 1 КБ - 20 100 мкс
сбор с p узлов: по очереди (p − 1)(α + βn), деревом ⌈log₂ p⌉(α + βn)

РАССЫЛКА                   нижние границы: α log₂ p и β n
биномиальное дерево: раунд k - узлы i < 2ᵏ шлют узлам i + 2ᵏ
    ⌈log₂ p⌉(α + βn), p − 1 сообщение; 1000 узлов - 10 раундов
конвейер: k кусков по цепочке, (p − 2 + k)(α + βn/k) → βn
64 узла: 1 КБ - дерево 121 мкс; 100 МБ - цепочка 18,6 мс
от корня r: виртуальный номер v = (i − r) mod p

ALL-REDUCE              время                   хорош для
дерево + рассылка       2 log₂ p (α + βn)       -
гиперкуб (удвоение)     log₂ p (α + βn)         коротких
кольцо                  2(p − 1)(α + βn/p)      длинных
кольцо = reduce-scatter (p − 1 шагов) + all-gather (p − 1)
передача кольца с узла 2n(p − 1)/p - почти нижняя граница
64 узла: 1 КБ - гиперкуб 121 мкс, кольцо 2520
         100 МБ - гиперкуб 60 мс, кольцо 22 мс
all-to-all: p(α + βn) напрямую или log₂ p (α + βpn) гиперкубом

БАЛАНСИРОВКА
известные размеры: задача i → рабочему ⌊Sᵢ · p / W⌋, перекос < max tᵢ
    тяжёлый хвост: поровну по числу +43%, по префиксам +4,5%
общая очередь: просто, но мастер - узкое место
кража работы (Блюмофе, Лейзерсон): T₁/p + O(T∞), краж O(p · T∞)
    8 разных корней: без кражи 1101, с кражей 383 (граница 368)

Ловушки джокера

Цикл мелких запросов. Тысяча запросов по строке - тысяча задержек; одна пачка - одна.

Координатор, принимающий от всех. Сбор по одному сообщению линеен по p; делают деревом.

Оценка по пропускной способности. Для коротких сообщений решает задержка, а не гигабиты.

Дерево для больших данных. Каждый раунд гонит весь объём; нужен конвейер или кольцо.

Кольцо для скаляра. 2(p − 1) задержек там, где гиперкубу хватает log₂ p.

Отправитель без данных. В расписании отправлять может только получивший к началу раунда.

Деление по числу задач при тяжёлом хвосте. Время - по самому загруженному.

Вор, крадущий свежее. Мелкие задачи - много краж и толкотня с владельцем на одном конце дека.

Понятия

Что унести

Ловушки джокера

Комментарии

Оставить комментарий