Гонки в параллельных алгоритмах и когда НЕ стоит параллелить

Завершающий урок: про корректность параллельных алгоритмов и про честное «не надо».

Гонка данных (data race) — ситуация, когда два потока обращаются к одной памяти без упорядочивания и хотя бы один пишет; результат становится непредсказуемым.

Гонки: краткое напоминание

Детально гонки и синхронизация разбираются в курсе «Конкурентность и многопоточность» — здесь лишь связь с параллельными алгоритмами. Даже если алгоритм спроектирован из независимых кусков, на стыках (сборка результатов, общие счётчики, граничные ячейки stencil) возникает разделяемое состояние. Классический пример — параллельная редукция, написанная наивно: все потоки прибавляют к общей переменной sum += local, и инкременты теряются.

Поток A читает sum=10, поток B читает sum=10
Поток A пишет sum=15 (10+5), поток B пишет sum=13 (10+3)
Одно из прибавлений потеряно! Должно быть 18, а вышло 13.

Правильный параллельный алгоритм избегает таких гонок по дизайну: использует reduction (локальные аккумуляторы + дерево), а не общую переменную; пишет результат каждого куска в свою ячейку; обменивается граничными данными явно. Лучшая защита от гонок — структура без разделяемой записи, а не россыпь блокировок.

# правильно: каждый поток пишет в СВОЮ ячейку, гонки нет
data = [3, 1, 7, 0, 4, 1, 6, 3]
threads = 4
chunk = len(data) // threads

partial = [0] * threads          # своя ячейка на поток - нет общей записи
for t in range(threads):
    partial[t] = sum(data[t*chunk:(t+1)*chunk])
print("частичные (без гонки):", partial)
print("итог (редукция):", sum(partial))

Вывод:

частичные (без гонки): [4, 7, 5, 9]
итог (редукция): 25

Когда НЕ стоит параллелить

Параллелизм — инструмент, а не самоцель. Есть классы задач, где он не окупается или даже вредит.

Маленькая задача. Если работа выполняется за микросекунды, накладные расходы на создание потоков и координацию превысят саму работу. Сложить сто чисел параллельно медленнее, чем последовательно.

Большая последовательная доля. По закону Амдала, если 80% задачи неустранимо последовательны, потолок ускорения — всего 1.25×. Усилия не стоят результата.

Сильные зависимости. Алгоритмы, где каждый шаг зависит от предыдущего (некоторые рекуррентные вычисления, обход связного списка, глубокий DFS), имеют большой span и малый параллелизм — делить почти нечего.

Память-ограниченные задачи. Если задача упирается в пропускную способность памяти, а не в счёт (простой проход по огромному массиву с малой работой на элемент), добавление ядер не поможет — они все ждут память. Параллелизм ускоряет счёт, а не доступ к памяти.

Дороже отладка. Параллельный код сложнее писать, тестировать и сопровождать (гонки воспроизводятся не всегда). Если ускорение скромное, простой последовательный код может быть выгоднее в сумме.

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

Грамотный подход — сначала измерить, потом параллелить. Профилировщик показывает, где программа реально проводит время. Если 90% времени — в одной счётной функции с большим параллелизмом, её и распараллеливают. Если время размазано или упирается в память/ввод-вывод, параллелизм не поможет, и лучше оптимизировать алгоритм или память. Часто переписать последовательный алгоритм на более эффективный даёт больший выигрыш, чем распараллелить плохой.

Завершить курс стоит на трезвой ноте: параллелизм — не цель, а средство, и зрелость инженера видна именно в умении не применять его без нужды. Начинающий, узнав про потоки, бросается распараллеливать всё подряд и часто получает код медленнее, сложнее и багованнее исходного. Опытный сперва спрашивает: а нужна ли тут вообще скорость? Если да — где именно тратится время? И достаточно ли там параллелизма, чтобы окупить сложность? Нередко ответ — «нет», и лучшее решение состоит в том, чтобы оставить код последовательным и понятным. Всё, что вы изучили в этом курсе, — законы, примитивы, паттерны, анализ — нужно не для того, чтобы параллелить любой ценой, а для того, чтобы осознанно решать, когда это оправдано, и делать это правильно, когда решились.

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

• Параллелить всё подряд без замеров — тратите усилия там, где выигрыша нет.
• Защищать редукцию общей переменной с блокировкой вместо локальных аккумуляторов — медленно и хрупко.
• Игнорировать, что параллельный код дороже в отладке — скромное ускорение может не окупить сложность.

Итоги

• Гонки возникают на стыках (сборка, общие счётчики); правильный алгоритм избегает разделяемой записи по дизайну.
• Не стоит параллелить крошечные, сильно последовательные, память-ограниченные задачи.
• Сначала профилируйте, потом параллельте; иногда лучший последовательный алгоритм выгоднее.
• Параллелизм — инструмент с ценой; применяйте его осознанно, а не по привычке.