Работа и глубина: два числа вместо одного

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

Как думаешь, сколько минут

Сборка проекта состоит из восьми задач. Если делать их по очереди на одной машине, уйдёт 44 минуты. Под сборку выделили сто машин - машин хватит на все задачи с избытком. Сколько займёт сборка теперь?

Ответь себе до чтения. «44 / 100, меньше минуты» - самый частый ответ, и он неверен: в проекте есть задачи, которые нельзя начать, пока не закончены другие. Ответ - 22 минуты, и вторая сотня машин его не изменит. Почему именно 22, а не 8 и не 40, - тема урока.

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

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

А если повар один, обед займёт сумму всех дел. Две эти величины - «сумма всего» и «самая длинная цепочка» - и описывают любую параллельную работу.

Механизм: граф зависимостей

Вычисление рисуют графом зависимостей: вершины - операции или задачи с их длительностью, стрелка из A в B значит «B нельзя начать, пока не закончена A». Циклов в таком графе нет: иначе задача ждала бы сама себя.

По графу считают две величины:

• работа T₁ - сумма длительностей всех вершин; столько займёт исполнение одним процессором;
• глубина T∞ - самая длинная по сумме длительностей цепочка стрелок, критический путь; столько займёт исполнение, если процессоров сколько угодно и каждая задача стартует в момент, когда готово всё, от чего она зависит. В англоязычных книгах глубину называют span.

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

Почему время на p процессорах зажато этими числами. За одну минуту p процессоров делают не больше p минут работы - значит, всю работу не сделать быстрее T₁ / p. И цепочку критического пути никакие процессоры не ускорят: её звенья идут строго по очереди - значит, не быстрее T∞.

Правило

Работа T₁ - сумма всех операций, глубина T∞ - самая длинная цепочка зависимостей. На p процессорах время Tₚ ≥ T₁ / p (закон работы) и Tₚ ≥ T∞ (закон глубины). Параллелизм T₁ / T∞ - во сколько раз задачу в принципе можно ускорить; процессоров сверх этого числа ей нечем занять.

Разбор: критический путь сборки

Задачи перечислены так, что каждая стоит после всех, от которых зависит. Тогда момент окончания считается одним проходом: задача стартует, когда закончилась последняя из её зависимостей, и заканчивается через свою длительность. Заодно запоминаем, какая зависимость задержала старт, - по этим ссылкам потом восстанавливается сам путь.

# задачи сборки: имя, длительность в минутах, от чего зависит
zadachi = [
    ["скачать", 4, []],
    ["ядро", 9, ["скачать"]],
    ["драйверы", 6, ["скачать"]],
    ["утилиты", 3, ["скачать"]],
    ["модули", 7, ["ядро"]],
    ["тесты ядра", 5, ["ядро", "драйверы"]],
    ["документация", 8, []],
    ["образ", 2, ["модули", "тесты ядра", "утилиты"]],
]
konec = {}
otkuda = {}
rabota = 0
for imya, dlit, zavisit in zadachi:
    start = 0
    for z in zavisit:
        if konec[z] > start:
            start = konec[z]
            otkuda[imya] = z
    konec[imya] = start + dlit
    rabota = rabota + dlit
glubina = 0
posl = ""
for imya in konec:
    if konec[imya] > glubina:
        glubina = konec[imya]
        posl = imya
put = [posl]
while put[-1] in otkuda:
    put.append(otkuda[put[-1]])
put.reverse()
print("работа", rabota, "глубина", glubina)
print("критический путь:", " -> ".join(put))
print("параллелизм", round(rabota / glubina, 2))

работа 44 глубина 22
критический путь: скачать -> ядро -> модули -> образ
параллелизм 2.0

Вот ответ на вопрос из начала: сколько бы машин ни было, быстрее 22 минут сборка не пройдёт, а машин хватит уже трёх (это покажет следующий урок). Параллелизм 2,0 говорит, что больше двух-трёх машин этой сборке почти не нужны: одновременно в ней идут самое большее четыре задачи, и на сотне машин 96 простаивают всё время.

Отсюда и способ ускорить сборку: не докупать машины, а резать критический путь. Если «ядро» разбить на две независимые половины по 4,5 минуты, которые идут параллельно после «скачать», а «модули» и «тесты ядра» ждут обеих, глубина станет 4 + 4,5 + 7 + 2 = 17,5, хотя работа не изменится.

Разбор: рекурсия - ещё не параллелизм

Кажется, что «разделяй и властвуй» параллелится само: две половины независимы, считай их на разных процессорах. Посчитаем это честно для двух алгоритмов. Работа и глубина рекурсивной функции считаются той же рекурсией: работа половин складывается, а глубина берётся по максимуму, потому что половины идут одновременно.

def summa_derevom(n):
    # работа и глубина: половины параллельно, одно сложение сверху
    if n == 1:
        return [0, 0]
    l = summa_derevom(n // 2)
    p = summa_derevom(n - n // 2)
    return [l[0] + p[0] + 1, max(l[1], p[1]) + 1]

def sliyanie_posledovatelnoe(n):
    # половины сортируются параллельно, а слияние - один цикл на n шагов
    if n == 1:
        return [0, 0]
    l = sliyanie_posledovatelnoe(n // 2)
    p = sliyanie_posledovatelnoe(n - n // 2)
    return [l[0] + p[0] + n, max(l[1], p[1]) + n]

for n in [16, 256, 4096]:
    s = summa_derevom(n)
    m = sliyanie_posledovatelnoe(n)
    print(n, "сумма", s, round(s[0] / s[1], 1),
          "сортировка", m, round(m[0] / m[1], 1))

16 сумма [15, 4] 3.8 сортировка [64, 30] 2.1
256 сумма [255, 8] 31.9 сортировка [2048, 510] 4.0
4096 сумма [4095, 12] 341.2 сортировка [49152, 8190] 6.0

У суммы на 4096 числах параллелизм 341: работа 4095, глубина 12. У сортировки слиянием - всего 6. Причина в слиянии: на верхнем уровне оно одно и проходит все n элементов подряд, на следующем - два слияния по n / 2, которые идут одновременно и тоже занимают n / 2 шагов. Глубина складывается в n + n/2 + n/4 + … ≈ 2n, а работа - n · log₂ n. Параллелизм n · log₂ n / 2n = log₂ n / 2, то есть 6 при n = 4096 - сколько ни дай ядер, сортировка ускорится не больше чем вшестеро.

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

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

Сравнение с самим собой. Параллельную программу запускают на одном ядре, потом на восьми, и получают «ускорение в 7,5 раза». Но если программа на одном ядре вдвое медленнее обычного последовательного алгоритма из-за лишней работы, настоящее ускорение - 3,75. Сравнивать честно надо с лучшим последовательным решением, а не с параллельной версией на одном ядре.

Покупка ядер без подсчёта глубины. Задача с параллелизмом 2 на 64 ядрах работает почти так же, как на четырёх, а платят за все 64. Без числа T₁ / T∞ это выясняется только после покупки.

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

Пайплайн CI в GitLab или GitHub Actions - тот самый граф: задачи и needs: между ними. Когда сборка идёт сорок минут, полезный первый вопрос - какой у неё критический путь. Bazel печатает его прямо в отчёте о сборке, make -j 64 упирается в него же. Spark и Dask строят граф задач для каждого запроса, и длинная цепочка последовательных стадий там тоже видна сразу.

В алгоритмах эти два числа дают общий язык: «работа n · log n, глубина log² n» говорит о параллельной сортировке всё, что нужно для выбора, без привязки к конкретному числу ядер.

Теперь сам

1. Добавь к сборке задачу «упаковка» на 6 минут, зависящую от «документации» и «образа». Какими станут работа, глубина и параллелизм?
2. Обычный цикл s = s + x[i] по n числам. Чему равны работа и глубина и почему цикл нельзя ускорить ядрами без переписывания?
3. Рекурсивное число Фибоначчи fib(n) = fib(n − 1) + fib(n − 2), где два вызова идут параллельно. Глубина растёт как n или как fib(n)?