Лишняя работа и зернистость: когда быстрый на бумаге алгоритм проигрывает

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

Как думаешь, какой быстрее

Два алгоритма поиска максимума среди 4096 чисел. Первый работает за два шага, но на первом шаге ему нужны 16 миллионов процессоров. Второй - дерево сравнений из первого урока: 12 шагов. Машина - восемь ядер. Какой алгоритм закончит раньше и во сколько раз?

Ответь себе до чтения. Два шага против двенадцати выглядят однозначно. Но восемь ядер не исполнят шаг на 16 миллионов процессоров за единицу времени - им придётся сделать эту работу по очереди. Ответ: дерево быстрее примерно в четыре тысячи раз.

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

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

И наоборот: одна заявка на годовой запас бумаги заставит всех ждать, пока её привезут целиком. Хороший размер заявки - где-то посередине, и он зависит от цены одной заявки.

Механизм: работа решает, когда процессоров мало

По оценке Брента время на p процессорах около T₁ / p + T∞. Когда p маленькое, а так почти всегда и бывает, первое слагаемое главное. Отсюда два правила.

Работоэффективность. Алгоритм с глубиной 1, но работой n² на восьми ядрах идёт как n² / 8 - хуже обычного последовательного цикла за n. Хороший параллельный алгоритм сначала держит работу на уровне последовательного, а уже потом снижает глубину.

Зернистость. Порождение задачи, синхронизация, передача данных - это тоже работа, просто не полезная. Если каждая задача стоит s операций накладных расходов, рекурсия до кусков размера 1 добавляет к работе s · 2n. Порог g: куски размером не больше g считаются обычным циклом, задач становится 2n / g, и накладные расходы падают в g раз. Платим за это глубиной: самый длинный путь теперь включает последовательный кусок длины g.

Правило

Параллельный алгоритм работоэффективен, если его работа O(T_посл) - того же порядка, что у лучшего последовательного. При малом числе процессоров время определяет работа, поэтому сначала сохраняют её, а потом снижают глубину. Накладные расходы на задачу - тоже работа: рекурсию останавливают порогом g, ниже которого считают последовательно, и выбирают g так, чтобы задач было много больше, чем процессоров, но каждая была заметно дороже своих накладных расходов.

Разбор: максимум за два шага на CRCW

Алгоритм с n² процессорами: процессор (i, j) сравнивает x[i] и x[j] и, если x[i] меньше, пишет единицу в ячейку proigral[i]. Все пишут одно и то же значение 1, так что правило common соблюдено. На втором шаге элемент без отметки - максимум; если таких несколько, все они равны максимуму и пишут ответ одним и тем же значением - правило common снова соблюдено. Программа исполняет оба шага и затем сравнивает время с деревом на восьми ядрах по оценке Брента.

import math

def max_vse_pary(x):
    # CRCW common: процессор (i, j) пишет 1, если x[i] < x[j]
    n = len(x)
    proigral = [0] * n
    zapisej = 0
    for i in range(n):
        for j in range(n):
            if x[i] < x[j]:
                proigral[i] = 1
                zapisej = zapisej + 1
    for i in range(n):
        if proigral[i] == 0:
            return [x[i], zapisej]

print(max_vse_pary([7, 3, 9, 1, 9, 4, 2, 8]))
p = 8
print("n  все пары: работа, оценка на 8  дерево: работа, оценка на 8")
for n in [64, 1024, 4096]:
    lg = math.ceil(math.log2(n))
    para_rab = n * n
    para_t = para_rab / p + 2
    der_rab = n - 1
    der_t = der_rab / p + lg
    print(n, para_rab, round(para_t), der_rab, round(der_t))

[9, 27]
n  все пары: работа, оценка на 8  дерево: работа, оценка на 8
64 4096 514 63 14
1024 1048576 131074 1023 138
4096 16777216 2097154 4095 524

На восьми числах алгоритм нашёл 9 и сделал 27 одновременных записей - при двух девятках обе остались без отметки, и ответ всё равно верный: значение у них одно. На 4096 числах оценка Брента для восьми ядер - около двух миллионов единиц времени, для дерева - 524 (если честно разложить уровни дерева по восьми ядрам, выходит 514). Разница в 4000 раз, и вся она - лишняя работа: n² против n − 1. Глубина 2 против 12 нигде не видна.

Где такой алгоритм всё-таки полезен: внутри видеокарты, где процессоров тысячи, а n - десятки. При n = 32 работа 1024 - мелочь, и два шага вместо пяти дают выигрыш - если одновременные записи в одну ячейку на этом железе дёшевы.

Разбор: порог для суммы миллиона чисел

Сумма 2²⁰ чисел рекурсией «пополам», восемь ядер, порождение задачи стоит 50 операций. Порог g: задача размером не больше g складывает числа обычным циклом. Считаем работу, глубину и оценку времени по Бренту для разных порогов.

import math
n = 2 ** 20
p = 8
s = 50
print("порог  задач  работа  глубина  оценка на 8")
for g in [1, 16, 256, 4096, 65536, n]:
    listev = n // g
    rabota = n + s * (2 * listev - 1)
    # путь от корня к листу: log2(listev) порождений и сам лист
    glubina = g + s * (round(math.log2(listev)) + 1)
    vremya = rabota / p + glubina
    print(g, 2 * listev - 1, rabota, glubina, round(vremya))
print("идеал", n // p)

порог  задач  работа  глубина  оценка на 8
1 2097151 105906126 1051 13239317
16 131071 7602126 866 951132
256 8191 1458126 906 183172
4096 511 1074126 4546 138812
65536 31 1050126 65786 197052
1048576 1 1048626 1048626 1179704
идеал 131072

При пороге 1 работа выросла в сто раз: два миллиона задач по 50 операций накладных расходов на миллион полезных сложений. При пороге во весь массив задача одна и параллельности нет; оценка Брента здесь даже завышена - одну задачу на ядра не разделить, и настоящее время равно работе, 1 048 626. При пороге 4096 задач 511 - по 64 на ядро, накладные расходы - 2% работы, и оценка времени всего на 6% хуже идеала n / p. Заметь, что и порог 256, и 65536 дают результат в 1,3-1,4 раза хуже лучшего, а не в сто: дно широкое.

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

Параллельность ради параллельности. Цикл по тысяче элементов переписали на задачи, по одной на элемент, и он стал медленнее в десять раз. Порождение задачи в пуле стоит сотни наносекунд, сложение - доли наносекунды.

Порог «на глаз» без замера. Порог подобрали на рабочей машине, а на сервере с 64 ядрами задач стало меньше, чем ядер: 31 задача на 64 ядра - половина машины простаивает. Правило «задач в разы больше, чем ядер» привязывает порог к машине.

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

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

ForkJoinPool в Java документирует ровно этот совет: задача должна выполнять заметную работу, иначе накладные расходы съедят выигрыш, и порог подбирают замером. Rayon в Rust делит работу адаптивно и сам перестаёт дробить, когда куски становятся мелкими. В numpy и библиотеках линейной алгебры параллельный цикл включается только для массивов больше некоторого размера - это и есть порог.

Работоэффективность - то, что отличает алгоритм для статьи от алгоритма для библиотеки. Параллельная сортировка в стандартной библиотеке C++ (std::sort с std::execution::par) делает работу того же порядка, что последовательная, - иначе она проигрывала бы ей на двух ядрах.

Теперь сам

1. Алгоритм A: работа n log₂ n, глубина log₂ n. Алгоритм B: работа n, глубина n / 1000. Какой быстрее на 4 ядрах при n = 10⁶, а какой на 10⁶ ядрах?
2. Порог 64, сумма 2²⁰ чисел, накладные расходы 50 на задачу. Сколько задач и какая доля работы уходит на накладные расходы?
3. Почему при пороге 1 глубина в таблице (1051) больше, чем при пороге 16 (866), хотя последовательный кусок короче? Не ошибка ли это?