Анализ параллельных алгоритмов: work и span

Урок про две фундаментальные характеристики, по которым оценивают параллельный алгоритм.

Work (T₁) — общее число операций (время на одном процессоре). Span (T∞) — длина критического пути, время при бесконечном числе процессоров. Параллелизм = work / span.

Две меры вместо одной

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

Параллелизм = work / span

Отношение T₁/T∞ показывает максимальное ускорение, которого алгоритм способен достичь — сколько процессоров он может полезно занять. Если параллелизм равен 1000, то и тысяча процессоров не простаивает; если он равен 4, то больше четырёх ядер бесполезны. Это более глубокая характеристика, чем закон Амдала: она встроена в саму структуру алгоритма.

import math

# дерево редукции n элементов: work = n-1, span = log2(n)
for n in [8, 64, 1024, 1_000_000]:
    work = n - 1
    span = math.ceil(math.log2(n))
    parallelism = work / span
    print(f"n={n:>8}: work={work:>8}, span={span:>3}, параллелизм={parallelism:>10.1f}")

Вывод:

n=       8: work=       7, span=  3, параллелизм=       2.3
n=      64: work=      63, span=  6, параллелизм=      10.5
n=    1024: work=    1023, span= 10, параллелизм=     102.3
n= 1000000: work=  999999, span= 20, параллелизм=   49999.9

Видно главное: с ростом n параллелизм редукции стремительно растёт (для миллиона элементов — около 50000), потому что work растёт линейно, а span — лишь логарифмически. Такой алгоритм отлично загрузит хоть тысячи ядер.

Закон Брента

На p процессорах время выполнения ограничено: T(p) ≤ T₁/p + T∞. Первый член — идеальное деление работы, второй — неустранимый критический путь. Пока p меньше параллелизма (T₁/T∞), доминирует первый член и ускорение почти линейно. Когда p превышает параллелизм, второй член (span) становится потолком — добавлять процессоры бессмысленно. Это и есть структурная причина потолка из закона Амдала.

Алгоритм	Work	Span	Параллелизм
Редукция (сумма)	O(n)	O(log n)	O(n/log n)
Scan Blelloch	O(n)	O(log n)	O(n/log n)
Умножение матриц	O(n³)	O(log n)	O(n³/log n)
Merge sort (parallel)	O(n log n)	O(log²n)	высокий

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

Work и span вычисляют по графу зависимостей задач (DAG). Work — число всех узлов графа, span — длина самого длинного пути от входа к выходу. Планировщик вроде work stealing достигает времени, близкого к T₁/p + T∞ — то есть почти оптимального, предсказанного законом Брента. Поэтому, проектируя параллельный алгоритм, инженер целенаправленно уменьшает span: заменяет последовательные цепочки деревьями, разворачивает рекурсию в сбалансированную.

Анализ через work и span ценен тем, что он машинно-независим: он говорит о структуре самого алгоритма, а не о конкретном железе. Закон Амдала требует знать долю распараллеливаемой работы — величину расплывчатую и зависящую от реализации. Work и span же выводятся прямо из графа зависимостей и дают чистую характеристику: на сколько процессоров алгоритм в принципе способен масштабироваться, прежде чем упрётся в критический путь. Поэтому в теории параллельных вычислений именно эти две меры — основной язык. Научившись прикидывать work и span для своих алгоритмов, вы получаете способность предсказать их параллельный потолок ещё до того, как написана первая строка кода.

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

Оценивать алгоритм только по work, игнорируя span — большой span скрыто ограничивает ускорение.
Думать, что низкая work всегда лучше — алгоритм с меньшей работой, но большим span может проиграть на многих ядрах.
Ждать ускорения сверх параллелизма (work/span) — за ним добавление процессоров бесполезно.

Итоги

Work (T₁) — всего операций; span (T∞) — критический путь, время при ∞ процессоров.
Параллелизм = work/span — сколько процессоров алгоритм способен полезно занять.
Закон Брента: T(p) ≤ T₁/p + T∞; за пределом параллелизма правит span.
Хороший параллельный алгоритм минимизирует span (заменяет цепочки деревьями).