Разделяй-и-властвуй параллельно: fork-join

Урок про самую естественную модель параллелизма для рекурсивных алгоритмов.

Fork-join — модель, где задача рекурсивно разветвляется (fork) на подзадачи, выполняемые параллельно, а затем результаты собираются (join) при возврате из рекурсии.

Идея

Многие алгоритмы устроены как «разделяй и властвуй»: разбить задачу на части, решить части, объединить. Merge sort, быстрое преобразование Фурье, суммирование дерева, многие задачи на массивах. В fork-join подзадачи, на которые мы разбили, независимы — значит, их можно решать параллельно. Слово fork означает «разветвить»: породить параллельные подзадачи. Слово join — «дождаться их и объединить результаты».

parallel_sum(массив):
    если массив мал: вернуть обычную сумму
    иначе:
        L, R = разделить пополам
        fork:  left  = parallel_sum(L)   # параллельно
        fork:  right = parallel_sum(R)   # параллельно
        join                              # дождаться обоих
        вернуть left + right

Эмуляция рекурсивного деления

Покажем структуру fork-join на параллельном суммировании. В браузере реальных потоков нет — выполняем рекурсию последовательно, но печатаем, как задача разветвляется и собирается. На реальной машине ветви считались бы одновременно.

def parallel_sum(a, depth=0):
    indent = "  " * depth
    if len(a) <= 1:
        print(f"{indent}лист {a} -> {sum(a)}")
        return sum(a)
    mid = len(a) // 2
    print(f"{indent}fork {a} -> {a[:mid]} | {a[mid:]}")
    left = parallel_sum(a[:mid], depth + 1)   # ветвь 1 (параллельно)
    right = parallel_sum(a[mid:], depth + 1)  # ветвь 2 (параллельно)
    total = left + right                       # join: объединяем
    print(f"{indent}join -> {left} + {right} = {total}")
    return total

data = [3, 1, 7, 0]
print("сумма =", parallel_sum(data))

Вывод:

fork [3, 1, 7, 0] -> [3, 1] | [7, 0]
  fork [3, 1] -> [3] | [1]
    лист [3] -> 3
    лист [1] -> 1
  join -> 3 + 1 = 4
  fork [7, 0] -> [7] | [0]
    лист [7] -> 7
    лист [0] -> 0
  join -> 7 + 0 = 7
join -> 4 + 7 = 11
сумма = 11

Дерево рекурсии — это и есть структура параллелизма: ветви на одном уровне независимы и считаются одновременно, join ждёт обе и складывает. Глубина дерева log n задаёт минимальное число шагов, а число листьев — потенциальный параллелизм.

Порог гранулярности

Разветвлять до одиночных элементов расточительно — overhead на создание задачи превысит пользу. Поэтому в fork-join вводят порог (cutoff): когда подзадача стала достаточно мала (скажем, меньше 1000 элементов), её считают последовательно без дальнейшего ветвления. Это классический приём: параллелить крупные ветви, мелочь — последовательно.

Где это используется

Fork-join — основа целых систем: язык Cilk (cilk_spawn / cilk_sync), OpenMP tasks (#pragma omp task), Java ForkJoinPool и parallelStream, Threading Building Blocks (TBB). Все они дают программисту простой способ сказать «эти две ветви независимы, считай параллельно», а планировщик сам раскидывает задачи по ядрам.

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

Когда задача делает fork, она кладёт одну ветвь в очередь, а вторую начинает считать сама. Свободные ядра подхватывают задачи из очередей — об этом механизме (work stealing) следующий урок. Join реализуется как ожидание готовности результата ветви: если ветвь ещё не посчитана, ядро может пока поработать над другой задачей.

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

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

• Ветвить до одиночных элементов без порога — overhead задач съест выигрыш.
• Делать fork для зависимых подзадач — если ветви делят состояние, будут гонки.
• Забыть join перед использованием результата — прочитаете недосчитанное значение.

Итоги

• Fork-join: рекурсивно разветвить на независимые подзадачи (fork), посчитать параллельно, объединить (join).
• Дерево рекурсии = структура параллелизма; ветви одного уровня независимы.
• Порог гранулярности (cutoff) переключает мелкие подзадачи на последовательный счёт.
• Лежит в основе Cilk, OpenMP tasks, Java ForkJoinPool, TBB.