Параллельный поиск, BFS и связные компоненты

Урок про параллелизм в поиске и обходах графов: где он естественен, а где упирается в зависимости.

Параллельный BFS обрабатывает граф уровнями (фронтами): все вершины текущего фронта раскрываются одновременно, порождая следующий фронт.

Параллельный поиск в массиве

Найти, есть ли значение в неотсортированном массиве, легко параллелится: режем массив на куски, каждое ядро ищет в своём, и если кто-то нашёл — сигналим всем остановиться. Это map + reduce (логическое ИЛИ результатов). Минимум из массива, максимум, количество совпадений — всё это редукции. А вот бинарный поиск в отсортированном массиве параллелится плохо: он и так O(log n), делить нечего, каждый шаг зависит от предыдущего.

# параллельный поиск минимума как редукция (эмуляция по кускам)
data = [9, 3, 7, 1, 8, 2, 6, 4]
workers = 2
chunk = len(data) // workers
local_min = []
for w in range(workers):
    part = data[w*chunk:(w+1)*chunk]
    local_min.append(min(part))       # каждое ядро -> локальный минимум
    print(f"ядро {w}: {part} -> min {local_min[-1]}")
print("глобальный минимум:", min(local_min))   # редукция минимумов

Вывод:

ядро 0: [9, 3, 7, 1] -> min 1
ядро 1: [8, 2, 6, 4] -> min 2
глобальный минимум: 1

BFS по уровням

Обход в ширину естественно ложится на параллелизм: вершины одного уровня (фронта) не зависят друг от друга, их можно раскрывать одновременно. Алгоритм идёт волнами: фронт уровня 0 — стартовая вершина; параллельно раскрываем всех её соседей — это фронт уровня 1; параллельно раскрываем их соседей — фронт уровня 2; и так далее. Параллелизм есть внутри уровня, но уровни идут строго по порядку (нужен барьер между ними).

from collections import deque

graph = {0: [1, 2], 1: [3], 2: [3, 4], 3: [5], 4: [5], 5: []}

def bfs_levels(g, start):
    visited = {start}
    frontier = [start]
    level = 0
    while frontier:
        print(f"уровень {level}: {frontier}")   # весь фронт раскрываем параллельно
        nxt = []
        for u in frontier:
            for v in g[u]:
                if v not in visited:
                    visited.add(v)
                    nxt.append(v)
        frontier = nxt
        level += 1

bfs_levels(graph, 0)

Вывод:

уровень 0: [0]
уровень 1: [1, 2]
уровень 2: [3, 4]
уровень 3: [5]

Проблемы параллельного BFS

Идея проста, но дьявол в деталях. Когда несколько вершин фронта одновременно открывают одного и того же соседа, нужно атомарно решить, кто его «застолбит» — иначе вершину добавят в следующий фронт дважды (гонка). Кроме того, размеры фронтов сильно скачут: в социальном графе один уровень может содержать миллионы вершин, а соседний — десятки, что рушит баланс нагрузки. Поэтому реальные параллельные BFS используют хитрые приёмы (direction-optimizing BFS, который переключается между «сверху-вниз» и «снизу-вверх» в зависимости от размера фронта).

Связные компоненты

Найти связные компоненты параллельно сложнее обычного DFS (DFS принципиально последователен — глубокая рекурсия). Параллельные подходы используют итеративный «label propagation»: каждой вершине дают метку (свой номер), затем многократно параллельно обновляют метку до минимальной среди соседей; за несколько раундов метки сходятся, и одинаковая метка = одна компонента. Это снова shared-память + редукция, повторяемая до стабилизации.

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

BFS на GPU хранит фронт как массив вершин; на каждом уровне тысячи потоков параллельно перебирают рёбра фронта и атомарными операциями помечают новые вершины. Барьер между уровнями обязателен. DFS на GPU почти не используют — его глубокая последовательная природа плохо ложится на массовый параллелизм.

Графовые алгоритмы — отрезвляющий контрпример к оптимизму параллелизма. Сложить массив легко: данные регулярны, доступ предсказуем, нагрузка ровная. Граф же нерегулярен: у одной вершины два соседа, у другой миллион; фронт BFS то взрывается, то схлопывается; обращения к памяти прыгают по всему графу, убивая кэш. Поэтому реальное ускорение параллельного BFS часто скромно, несмотря на обилие формальной независимости. Этот разрыв между «теоретически параллельно» и «практически быстро» — важный урок: наличие независимых задач необходимо, но не достаточно; нужны ещё регулярность доступа к памяти и сбалансированность нагрузки.

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

Параллелить DFS «в лоб» — его рекурсивная глубина последовательна, выигрыша почти нет.
Забыть атомарность при пометке вершин в BFS — одна вершина попадёт в фронт несколько раз.
Игнорировать скачки размера фронта — дисбаланс нагрузки убьёт ускорение.

Итоги

Поиск минимума/максимума/наличия в массиве — это редукция, отлично параллелится.
BFS параллелится по уровням: фронт раскрывается одновременно, между уровнями — барьер.
Главные трудности BFS — атомарная пометка вершин и скачки размера фронта; DFS плохо параллелится.