Параллельная редукция: дерево сложения за O(log n)

Урок подробно разбирает, почему параллельная редукция занимает всего log n шагов.

Дерево редукции — схема, где на каждом шаге пары соседних элементов складываются одновременно, вдвое сокращая массив, пока не останется одно значение.

Идея дерева

Последовательная сумма n чисел — это n-1 сложений строго по очереди. Но сложения независимы попарно! На первом шаге можно одновременно сложить (a0+a1), (a2+a3), (a4+a5), (a6+a7) — четыре сложения сразу, массив сократился вдвое. На втором шаге — два сложения, на третьем — одно. Для 8 элементов это 3 шага вместо 7. В общем случае — log₂(n) шагов. Это и есть параллельная редукция: глубина дерева равна логарифму.

шаг 0:  3   1   7   0   4   1   6   3
          \ /     \ /     \ /     \ /
шаг 1:    4       7       5       9
            \     /         \     /
шаг 2:      11             14
                \         /
шаг 3:           25

Пошаговая эмуляция

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

import math

def reduce_tree(a):
    a = a[:]
    step = 0
    while len(a) > 1:
        step += 1
        b = []
        for i in range(0, len(a), 2):
            if i + 1 < len(a):
                b.append(a[i] + a[i+1])   # пара складывается (параллельно на ядрах)
            else:
                b.append(a[i])            # нечётный хвост проходит дальше
        print(f"шаг {step}: {b}")
        a = b
    return a[0]

data = [3, 1, 7, 0, 4, 1, 6, 3]
print("массив:", data)
print("сумма =", reduce_tree(data))
print("шагов = log2(8) =", int(math.log2(len(data))))

Вывод:

массив: [3, 1, 7, 0, 4, 1, 6, 3]
шаг 1: [4, 7, 5, 9]
шаг 2: [11, 14]
шаг 3: [25]
сумма = 25
шагов = log2(8) = 3

Работа и глубина

Заметьте: общее число сложений всё равно n-1 (на 8 элементах — 7: четыре + два + одно). Это работа (work) — она не уменьшилась. Уменьшилась глубина (depth/span) — длина самой длинной цепочки зависимых операций: с n-1 до log n. Параллелизм возникает именно из малой глубины: за log n шагов мы заканчиваем, если есть достаточно ядер. Об анализе work и span — отдельный урок в конце курса.

Как работает под капотом

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

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

Частые ошибки

• Забыть про нечётный хвост: если элементов не степень двойки, последний непарный элемент нужно аккуратно протащить дальше.
• Думать, что дерево уменьшает число операций — оно уменьшает глубину, а работа та же n-1.
• Синхронизировать после каждого крошечного шага на GPU, не укрупнив работу на поток — лишний overhead.

Итоги

• Дерево редукции сворачивает n элементов за log n параллельных шагов вместо n-1.
• Работа остаётся n-1, уменьшается глубина (длина цепочки зависимостей).
• Параллелизм рождается из малой глубины; редукция — базовый приём на GPU.