Параллельные алгоритмы

2008 год. Intel выпускает Core i7 с 4 ядрами. Алгоритмы, написанные для одного ядра, не становятся быстрее. Нужно переписывать. Но как? Параллельные алгоритмы - это не просто 'запустить в нескольких потоках', это принципиально другой способ мышления о вычислениях.

• PostgreSQL parallel query: parallel sort и hash join на 32-ядерных серверах ускоряют аналитические запросы на 10-40x
• CUDA parallel sort в GPU базах данных (DuckDB GPU mode, cuDF от NVIDIA) - 100GB датасет сортируется за секунды
• Python scikit-learn GridSearchCV с n_jobs=-1 использует fork-join для параллельного перебора гиперпараметров - стандартная практика ML

Параллельная сортировка

Merge sort параллелизуется естественно: разделить массив на N/P кусков (P - число ядер), отсортировать каждый параллельно, затем смержить. Проблема: merge фаза - узкое место. Parallel merge sort на 8 ядрах даёт 5-6x ускорение (закон Амдала: sequential merge ~15%).

GPU radix sort (CUDA CUB библиотека) - 10-20x быстрее CPU sort на больших массивах. Используется в базах данных: PostgreSQL 16 добавил parallel sort для hash joins, что ускорило аналитические запросы на 40-60% на серверах с 32+ ядрами.

Parallel Prefix (Scan): строительный блок параллельных алгоритмов

Prefix sum (scan): для массива [a0, a1, ..., an] вычислить [a0, a0+a1, a0+a1+a2, ...]. Наивно - O(n) последовательно. Параллельно - O(log n) шагов, O(n) работы. Это примитив для 10+ алгоритмов: параллельный filter, histogram, radix sort, sparse matrix операции.

Thrust (CUDA C++ библиотека) и CUB предоставляют готовые parallel scan. В CPU мире: Intel TBB parallel_scan, std::inclusive_scan с execution::par (C++17). Spark использует prefix scan для distributed aggregations - shuffle phase.

Work Stealing: динамическая балансировка нагрузки

Work stealing решает проблему неравномерной нагрузки при fork-join параллелизме. Каждый поток имеет свою deque задач. Когда поток заканчивает задачи - крадёт с хвоста чужой deque. Воровство с хвоста (не головы) минимизирует конкуренцию: владелец работает с головы, воры - с хвоста.

Go runtime scheduler использует work stealing для горутин. Intel TBB, Cilk Plus, Java ForkJoinPool - все реализуют work stealing. Ключевой инсайт: воровать с хвоста означает кражу больших подзадач (которые ещё не разбились), что амортизирует overhead кражи.

Fork-Join: модель разделяй и властвуй

Fork-join - паттерн: fork (разделить задачу), execute parallel, join (собрать результаты). Рекурсивное разделение до threshold, затем sequential leaf. Ключевой вопрос: threshold. Слишком маленький - overhead fork > benefit. Слишком большой - плохая балансировка.

Python multiprocessing.Pool и concurrent.futures.ProcessPoolExecutor реализуют fork-join для CPU-intensive задач обходя GIL. NumPy операции (dot, sort) используют OpenMP fork-join внутри C кода. scikit-learn Parallel с n_jobs=-1 запускает fork-join на все CPU.

Ключевые идеи

• Parallel sort: разделить на P кусков, отсортировать параллельно, merge - узкое место (закон Амдала).
• Parallel prefix (scan): O(log n) шагов, примитив для 10+ алгоритмов - filter, histogram, radix sort.
• Work stealing: динамическая балансировка через кражу крупных задач с хвоста чужой deque.

Связанные темы

Параллельные алгоритмы строятся на базовых концепциях параллелизма:

• CUDA и GPU параллелизм — Parallel prefix и radix sort - ключевые примитивы GPU алгоритмов, реализованные в CUB/Thrust
• CSP и каналы (Go) — Fan-out/fan-in в Go - практическая реализация fork-join паттерна для I/O задач

Вопросы для размышления

• Как определить оптимальный threshold для рекурсивного fork-join: где грань между overhead разбиения и пользой параллелизма?
• Почему parallel prefix sum имеет O(n) работы при O(log n) шагах, и как это влияет на energy efficiency?
• В каких сценариях sequential алгоритм быстрее параллельного на том же железе?

Связанные уроки

• alg-01-big-o
• alg-05-merge-sort