Work-efficient scan: алгоритм Blelloch

Урок про work-efficient scan, который тратит лишь O(n) работы, сохраняя малую глубину.

Scan Blelloch — алгоритм exclusive-scan из двух проходов по дереву: up-sweep (вверх, считаем частичные суммы) и down-sweep (вниз, раздаём префиксы). Работа — O(n), глубина — O(log n).

Проблема, которую он решает

Hillis-Steele элегантен, но делает n·log n работы — для миллиарда элементов это в 30 раз больше операций, чем у последовательного scan. Алгоритм Blelloch (1990) делает всего O(n) работы, как последовательный, но при этом параллелен. Он немного сложнее и состоит из двух фаз.

Up-sweep: считаем суммы поддеревьев

Первая фаза — как дерево редукции снизу вверх. Складываем пары, потом пары пар, и так далее. После up-sweep в правом конце массива оказывается полная сумма, а в промежуточных позициях — суммы поддеревьев. Это нам пригодится в обратном проходе.

Down-sweep: раздаём префиксы

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

def blelloch(a):
    a = a[:]
    n = len(a)
    # up-sweep: частичные суммы
    d = 1
    while d < n:
        for i in range(0, n, 2*d):
            a[i + 2*d - 1] += a[i + d - 1]
        d *= 2
    print("после up-sweep:", a, "(правый конец = полная сумма)")
    total = a[-1]
    a[-1] = 0                          # очищаем корень
    # down-sweep: раздаём префиксы
    d = n // 2
    while d >= 1:
        for i in range(0, n, 2*d):
            t = a[i + d - 1]
            a[i + d - 1] = a[i + 2*d - 1]
            a[i + 2*d - 1] += t
        d //= 2
    return a, total

data = [3, 1, 7, 0, 4, 1, 6, 3]
res, total = blelloch(data)
print("exclusive scan:", res)
print("полная сумма:  ", total)

Вывод:

после up-sweep: [3, 4, 7, 11, 4, 5, 6, 25] (правый конец = полная сумма)
exclusive scan: [0, 3, 4, 11, 11, 15, 16, 22]
полная сумма:   25

Результат — exclusive scan: элемент i равен сумме всех элементов до i. Проверьте: третий элемент 11 = 3+1+7 (сумма первых трёх), как и должно быть. Чтобы получить inclusive scan, достаточно прибавить к каждому элементу исходный массив поэлементно или сдвинуть.

Inclusive против exclusive

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

Up-sweep и down-sweep вместе делают примерно 2·(n-1) операций — линейно по n, как последовательный scan, но обе фазы имеют глубину log n. Поэтому Blelloch называют work-efficient: он не тратит лишнюю работу ради параллелизма. На GPU именно этот алгоритм лежит в основе библиотечных primitives вроде CUB и Thrust scan. Цена — чуть более хитрая индексация и две фазы вместо одной.

Сравнение Hillis-Steele и Blelloch — хороший пример того, что у параллельного алгоритма есть не одна «правильная» форма, а спектр компромиссов. Hillis-Steele проще в реализации и имеет меньше шагов синхронизации, но тратит в log n раз больше работы. Blelloch экономен по работе, но сложнее и делает два прохода. Какой выбрать, зависит от железа: на маленьких массивах, где потоки всё равно простаивали бы, лишняя работа Hillis-Steele бесплатна, и его берут за простоту. На огромных массивах, где работа реально стоит времени и энергии, побеждает Blelloch. Зрелый инженер держит в голове оба и выбирает по ситуации, а не заучивает один «лучший» алгоритм.

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

• Перепутать inclusive и exclusive — у них разный сдвиг, и алгоритмы поверх scan дадут смещённый результат.
• Забыть обнулить корень перед down-sweep — получите мусор.
• Применять Blelloch к массиву не степени двойки без дополнения (padding) — индексация сломается.

Итоги

• Blelloch — work-efficient scan: O(n) работы и O(log n) глубины, две фазы up-sweep/down-sweep.
• Up-sweep считает суммы поддеревьев, down-sweep раздаёт префиксы сверху вниз.
• Даёт exclusive scan; лежит в основе GPU-библиотек (Thrust, CUB).