Рассылка: биномиальное дерево для коротких сообщений и конвейер для длинных

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

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

Узел 0 знает новость, и её надо разослать на 1000 узлов. За один раунд каждый узел может отправить одно сообщение одному другому узлу. Сколько раундов понадобится?

Ответь себе до чтения. «999 - корень пишет каждому» - если рассылает только корень. Но узел, получивший новость, тоже может её передавать. Тогда после первого раунда знают двое, после второго - четверо: ответ 10.

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

Слух в деревне. Узнавший сразу рассказывает соседу, и теперь рассказывают оба. Через день знают двое, через два - четверо, через десять - тысяча. Число знающих удваивается, пока не кончатся слушатели.

Но если «новость» - это телега кирпичей, удвоение не спасает: в каждом раунде кто-то везёт телегу целиком, и десять раундов - это десять полных рейсов. Выгоднее выстроить цепочку и передавать кирпичи по одному: пока второй кирпич едет к первому соседу, первый уже едет дальше.

Механизм: дерево и конвейер

Биномиальная рассылка. В раунде k (считая с нуля) каждый узел i < 2ᵏ, у которого уже есть данные, отправляет их узлу i + 2ᵏ. Число получивших удваивается: 1, 2, 4, …. Раундов ⌈log₂ p⌉, сообщений p − 1 - каждый узел получает ровно одно. Время ⌈log₂ p⌉ · (α + β · n).

Конвейерная цепочка. Узлы стоят цепочкой 0 → 1 → … → p − 1, сообщение разрезано на k кусков. Первый кусок проходит p − 1 переходов, каждый следующий отстаёт на один шаг: всего p − 2 + k шагов по α + β · n / k. Больше кусков - меньше β-часть, но больше задержек; оптимум - примерно k ≈ √((p − 2) · β · n / α): там, где растущее с k слагаемое k · α сравнивается с падающим (p − 2) · β · n / k, и при большом n время близко к β · n. Сандерс разбирает конвейер по двоичному дереву (расписание длиннее, здесь только результат) - он получает O(β · n + α · log p), то есть обе нижние границы с точностью до множителей.

Правило

Рассылка на p узлов не быстрее α · log₂ p и не быстрее β · n. Биномиальное дерево (раунд k: узлы i < 2ᵏ шлют узлам i + 2ᵏ) даёт ⌈log₂ p⌉ (α + β · n) - оптимально для коротких сообщений. Для длинных сообщение режут на куски и гонят конвейером: время приближается к β · n.

Разбор: расписание биномиальной рассылки

Программа строит раунды и проверяет главное: все узлы получили данные, каждый узел в раунде отправляет не больше одного сообщения, раундов ⌈log₂ p⌉.

def binom_rassylka(p):
    # раунд k: каждый узел i < 2^k, у которого уже есть данные,
    # отправляет их узлу i + 2^k, если такой есть
    est = [False] * p
    est[0] = True
    raundy = []
    shag = 1
    while shag < p:
        raund = []
        for i in range(shag):
            if est[i] and i + shag < p:
                raund.append([i, i + shag])
        for otkuda, kuda in raund:
            est[kuda] = True
        raundy.append(raund)
        shag = shag * 2
    return [raundy, est.count(True)]

r = binom_rassylka(8)
for k in range(len(r[0])):
    print("раунд", k + 1, r[0][k])
for p in [8, 100, 1000]:
    r = binom_rassylka(p)
    soobshchenij = 0
    for raund in r[0]:
        soobshchenij = soobshchenij + len(raund)
    print(p, "узлов: раундов", len(r[0]), "сообщений", soobshchenij,
          "получили все:", r[1] == p)

раунд 1 [[0, 1]]
раунд 2 [[0, 2], [1, 3]]
раунд 3 [[0, 4], [1, 5], [2, 6], [3, 7]]
8 узлов: раундов 3 сообщений 7 получили все: True
100 узлов: раундов 7 сообщений 99 получили все: True
1000 узлов: раундов 10 сообщений 999 получили все: True

На восьми узлах - три раунда: 1, 2 и 4 сообщения. На 1000 - десять раундов и 999 сообщений: каждый узел, кроме корня, получает ровно одно. Узлы, у которых данных ещё нет, в раунде не отправляют - условие est[i] это и проверяет; на p = 100 последний раунд неполный: узлов i + 64 < 100 всего 36.

Разбор: дерево или конвейер

Теперь время. 64 узла, задержка 20 мкс, 10 ГБ/с. Для цепочки перебираем число кусков k = 1, 2, 4, … и берём лучшее.

import math

alfa = 20.0
beta = 0.0001
p = 64

def binom(n):
    return math.ceil(math.log2(p)) * (alfa + beta * n)

def cepochka(n):
    # k кусков идут по цепочке 0 -> 1 -> ... -> p-1:
    # первый кусок идёт p - 1 переходов, остальные k - 1 - вслед за ним
    luchshee = -1
    k = 1
    while k <= n:
        t = (p - 2 + k) * (alfa + beta * n / k)
        if luchshee < 0 or t < luchshee:
            luchshee = t
        k = k * 2
    return luchshee

print("байт       дерево     цепочка   нижняя граница")
for n in [1000, 10 ** 6, 10 ** 8]:
    niz = max(math.ceil(math.log2(p)) * alfa, beta * n)
    print(n, round(binom(n)), round(cepochka(n)), round(niz))

байт       дерево     цепочка   нижняя граница
1000 121 1266 120
1000000 720 2048 120
100000000 60120 18644 10000

Килобайт: дерево - 121 мкс, почти ровно нижняя граница 6 · α = 120. Цепочка - 1266: 63 перехода, каждый с задержкой, на пути от начала до конца цепочки. Мегабайт: дерево всё ещё лучше, 720 против 2048. Сто мегабайт: дерево - 60 миллисекунд, потому что шесть раундов гонят по сто мегабайт; цепочка - 18,6 при нижней границе 10. Порог, где они меняются местами, - около шести мегабайт при этих α и β. Поэтому библиотеки держат оба алгоритма и выбирают по размеру.

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

Рассылка корнем. Корень пишет всем по очереди: p − 1 раундов. На тысяче узлов это 999 раундов там, где хватило бы десяти.

Дерево для больших данных. Модель нейросети на гигабайт рассылают биномиальным деревом на 512 узлов: девять раундов по гигабайту. Конвейер или разбиение на куски делают это почти за одну передачу.

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

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

MPI_Bcast в реализациях MPICH и Open MPI переключается между биномиальным деревом, конвейером и двухфазной схемой (разрезать и раздать куски, потом собрать их у всех) по размеру сообщения и числу узлов. Раздача обновления по тысячам серверов - BitTorrent внутри дата-центра (так, например, Twitter раздавал сборки утилитой Murder) - тот же конвейер: файл режется на куски, и каждый узел передаёт их дальше, как только получил.

Теперь сам

1. Сколько раундов и сообщений нужно биномиальной рассылке на 5000 узлов?
2. В каком раунде узел 13 получит данные при биномиальной рассылке от узла 0?
3. Почему конвейер с k = 1 хуже простой цепочки нет - а с огромным k снова плохо?