Распределённая память: цена сообщения α + β · n

Если ты знаешь модель α + β·n, порог, где задержка сравнивается с передачей, и почему сбор с p узлов делают деревом, листай до «Теперь сам».

Как думаешь, во сколько раз

Нужно переслать мегабайт с узла на узел. Вариант первый - одним сообщением. Вариант второй - тысячей сообщений по килобайту. Сеть - 10 гигабайт в секунду, задержка - 20 микросекунд на сообщение. Во сколько раз второй вариант медленнее?

Ответь себе до чтения. «Данных столько же - время то же» - частая ошибка. Байты передаются за одно и то же время, но у второго варианта тысяча задержек. Ответ - примерно в 170 раз.

На что это похоже

Грузоперевозки. Каждый рейс грузовика стоит фиксированно - водитель, топливо, погрузка - плюс немного за каждый ящик. Сто ящиков одним рейсом - дёшево. Сто рейсов по ящику - разорение, хотя ящиков столько же. А если груз огромный, то уже неважно, сколько рейсов: стоимость определяется числом ящиков, и выгадать можно, только не возя ящики туда-обратно.

Механизм: модель и её следствия

Модель распределённой памяти: p узлов, у каждого своя память, между ними сеть. Сообщение длиной n идёт от узла к узлу за α + β · n. Узел одновременно может отправлять одно сообщение и принимать одно (полный дуплекс, один порт). Сандерс и соавторы строят на этой модели всю главу о коллективных операциях.

Следствия:

• порог n* = α / β: сообщения короче него стоят в основном задержку, длиннее - в основном передачу;
• мелкие сообщения склеивают в пакеты - на каждом сэкономленном сообщении экономится α;
• свести сумму векторов длины n (или другую сводку того же размера) с p узлов на один: по очереди - (p − 1)(α + β · n), деревом - ⌈log₂ p⌉ (α + β · n); в дереве узлы попарно складывают свои части, как сумма деревом из первой главы раздела, только теперь каждый уровень - раунд сообщений. Время самих сложений здесь не считаем: обычно оно меньше передачи.

Близкая модель BSP (Валиант, 1990) делит вычисление на супершаги: все считают локально, потом обмениваются сообщениями, потом барьер. Цена супершага - локальная работа плюс g · h за обмен (h - наибольшее число машинных слов, которое узел отправляет или принимает за супершаг) плюс L за барьер; L играет роль α, g - роль β, только L платится раз за супершаг, а не за каждое сообщение.

Правило

Сообщение длиной n стоит α + β · n; узел за раз отправляет одно и принимает одно. Сообщения короче α / β стоят в основном задержку - их склеивают; данные длиннее - стоят передачу, и их нельзя гонять лишний раз. Свести данные с p узлов на один можно за ⌈log₂ p⌉ раундов деревом вместо p − 1 по очереди.

Разбор: мегабайт одним и миллионом сообщений

Задержка 20 микросекунд - типичная цифра для TCP внутри дата-центра; в специальных сетях вроде InfiniBand она в десятки раз меньше. Пропускная способность - 10 гигабайт в секунду, то есть β = 0,0001 микросекунды на байт. Для своей сети α и β меряют «пинг-понгом»: время пересылки туда и обратно для сообщений разной длины ложится на прямую 2α + 2β · n: половина её наклона - β, половина начального значения - α.

# сообщение длины n байт стоит alfa + beta * n
alfa = 20.0      # микросекунд на сообщение: задержка сети и стека
beta = 0.0001    # микросекунд на байт: 10 ГБ/с
vsego = 10 ** 6  # отправить мегабайт
print("сообщений  размер  время, мкс  доля задержки")
for kuskov in [1, 10, 1000, 100000, 1000000]:
    razmer = vsego // kuskov
    t = kuskov * (alfa + beta * razmer)
    dolya = kuskov * alfa / t
    print(kuskov, razmer, round(t, 1), round(dolya, 3))
print("порог, где задержка равна передаче:", round(alfa / beta), "байт")

сообщений  размер  время, мкс  доля задержки
1 1000000 120.0 0.167
10 100000 300.0 0.667
1000 1000 20100.0 0.995
100000 10 2000100.0 1.0
1000000 1 20000100.0 1.0
порог, где задержка равна передаче: 200000 байт

Одно сообщение - 120 микросекунд, и задержка в нём - шестая часть. Тысяча сообщений по килобайту - 20 100 микросекунд, в 167 раз дольше, и 99,5% времени - задержки. Порог 200 000 байт означает: всё, что меньше двухсот килобайт, в этой сети стоит в основном задержку. Поэтому базы данных и брокеры сообщений собирают мелкие записи в пачки (batching), а протоколы склеивают пакеты.

Разбор: собрать сумму с p узлов

У каждого из p узлов есть число или вектор, нужна сумма на узле 0. Линейно корень принимает сообщения по очереди - у него один порт. Деревом узлы сливаются попарно, и за раунд число держателей частичных сумм уменьшается вдвое.

import math

def lineino(p, n, alfa, beta):
    # корень по очереди принимает p - 1 сообщение
    return (p - 1) * (alfa + beta * n)

def derevom(p, n, alfa, beta):
    # пары сливаются, как сумма деревом: ceil(log2 p) раундов
    return math.ceil(math.log2(p)) * (alfa + beta * n)

alfa = 20.0
beta = 0.0001
print("узлов  8 байт: линейно, деревом   8 МБ: линейно, деревом")
for p in [8, 64, 1024]:
    malo = [lineino(p, 8, alfa, beta), derevom(p, 8, alfa, beta)]
    mnogo = [lineino(p, 8 * 10 ** 6, alfa, beta),
             derevom(p, 8 * 10 ** 6, alfa, beta)]
    print(p, round(malo[0]), round(malo[1]),
          round(mnogo[0]), round(mnogo[1]))

узлов  8 байт: линейно, деревом   8 МБ: линейно, деревом
8 140 60 5740 2460
64 1260 120 51660 4920
1024 20461 200 838860 8200

Маленькие сообщения: на 1024 узлах линейно - 20 миллисекунд, деревом - 200 микросекунд. Выигрыш - 1023 / 10, около ста раз: логарифм задержек против линейного числа. Большие сообщения: отношение то же, но дерево всё равно плохо - каждый из десяти раундов гонит все восемь мегабайт, и выходит 8,2 миллисекунды, тогда как одна передача β · n - 0,8 миллисекунды. Каждый некорневой узел должен получить или отдать данные хотя бы раз, поэтому β · n - нижняя граница. Как к ней подобраться, покажут следующие уроки: конвейер и разбиение данных на куски.

Что ломается без этого

Цикл из маленьких запросов. Сервис запрашивает у базы тысячу строк по одной: тысяча задержек туда и обратно. Тот же запрос одной пачкой - одна задержка. Это самая частая причина «база медленная» при быстрой базе.

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

Оценка по пропускной способности. «У нас 100 гигабит, значит, всё быстро» - для мелких сообщений пропускная способность ничего не решает, решает задержка.

Зачем это в работе

MPI на суперкомпьютерах, NCCL при обучении нейросетей на сотнях видеокарт, Spark и Ray в обработке данных - все реализуют одни и те же коллективные операции: рассылку, сборку, all-reduce, all-to-all. Выбор алгоритма внутри них делается ровно по модели α + β · n: для коротких сообщений - деревья с логарифмом задержек, для длинных - конвейеры и кольца, экономящие передачу.

Теперь сам

1. α = 5 мкс, β = 0,001 мкс/байт. Каков порог α / β, и что выгоднее: 100 сообщений по 1000 байт или одно на 100 000 байт?
2. Сколько раундов нужно дереву, чтобы свести данные с 3000 узлов?
3. Почему корень при линейной сборке не может принимать сообщения от нескольких узлов одновременно?