Параллельный scan: префиксные суммы (Hillis-Steele)

Урок показывает, как «безнадёжно последовательную» префиксную сумму распараллелить за log n шагов.

Scan (префиксная сумма) — для массива a выдаёт массив, где каждый элемент равен сумме всех предыдущих (включая себя для inclusive-варианта). Фундаментальный приём, лежащий в основе многих параллельных алгоритмов.

Почему scan кажется последовательным

Inclusive scan массива [3,1,7,0] даёт [3,4,11,11]: каждый элемент зависит от предыдущего результата. Очевидный алгоритм — бежать слева направо, накапливая сумму, за O(n) последовательных шагов. Кажется, тут нечего параллелить: чтобы узнать сумму до элемента i, нужна сумма до i-1. Но это иллюзия — существует параллельный алгоритм за O(log n) шагов.

Алгоритм Hillis-Steele

Идея: на шаге с расстоянием d каждый элемент прибавляет к себе элемент, стоящий на d позиций левее. Сначала d=1 (прибавили соседа), потом d=2, потом d=4 — расстояние удваивается. За log n шагов каждый элемент «дотянулся» до всех предыдущих. Внутри одного шага все прибавления независимы и идут одновременно.

def hillis_steele(a):
    a = a[:]
    n = len(a)
    d = 1
    step = 0
    while d < n:
        step += 1
        b = a[:]                       # читаем из старого, пишем в новый
        for i in range(n):
            if i >= d:
                b[i] = a[i] + a[i-d]   # прибавляем элемент на d левее
        print(f"d={d}: {b}")
        a = b
        d *= 2
    return a

data = [3, 1, 7, 0, 4, 1, 6, 3]
print("вход:          ", data)
print("inclusive scan:", hillis_steele(data))

Вывод:

вход:           [3, 1, 7, 0, 4, 1, 6, 3]
d=1: [3, 4, 8, 7, 4, 5, 7, 9]
d=2: [3, 4, 11, 11, 12, 12, 11, 14]
d=4: [3, 4, 11, 11, 15, 16, 22, 25]
inclusive scan: [3, 4, 11, 11, 15, 16, 22, 25]

Три шага (log₂8) — и готов полный набор префиксных сумм. Обратите внимание: на каждом шаге читаем из «старой» копии, пишем в «новую» — иначе элемент успел бы измениться до того, как его прочитал сосед (классическая гонка).

Scan заслуживает особого внимания, потому что он опровергает интуицию. На первый взгляд префиксная сумма — образец последовательности: чтобы узнать сумму до пятого элемента, кажется, обязательно нужна сумма до четвёртого. Эта ложная очевидность годами мешала людям параллелить целые классы задач, которые «выглядели» последовательными. Урок Hillis-Steele шире самого scan: если задача кажется неразрывно последовательной из-за накапливаемого состояния, не спешите сдаваться — возможно, существует способ перестроить зависимости в дерево. Многие прорывы в параллельных алгоритмах были именно таким переосмыслением «очевидно последовательных» вычислений.

Зачем scan вообще нужен

Scan — это швейцарский нож параллельных алгоритмов. С его помощью параллельно делают: компактификацию массива (выбросить элементы по условию, узнав их новые позиции через scan флагов), распределение работы (префиксная сумма размеров даёт смещения), сортировку поразрядную (radix), построение гистограмм. Если задача «кажется» последовательной из-за накапливаемого состояния — часто её спасает scan.

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

Hillis-Steele делает log n шагов, но на каждом шаге — почти n сложений, итого work ≈ n·log n. Это больше, чем последовательные n операций. То есть алгоритм быстр по глубине, но расточителен по работе. Для GPU, где потоков много и они всё равно простаивали бы, это терпимо. Но существует более экономный work-efficient scan Blelloch — о нём следующий урок.

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

• Писать результат на месте, в тот же массив: сосед прочитает уже изменённое значение — гонка и неверный ответ. Нужны двойные буферы.
• Считать, что scan нельзя распараллелить из-за зависимости от предыдущего — можно, за log n.
• Игнорировать, что Hillis-Steele делает n·log n работы — для огромных массивов это расточительно.

Итоги

• Scan (префиксная сумма) распараллеливается за O(log n) шагов алгоритмом Hillis-Steele.
• На шаге d каждый элемент прибавляет элемент на d позиций левее; d удваивается.
• Нужны двойные буферы (читать старое, писать новое), иначе гонка.
• Hillis-Steele быстр по глубине, но делает n·log n работы.