Накладные расходы: почему 2 ядра не дают ровно 2x

Урок про «налоги» параллелизма, из-за которых реальное ускорение всегда меньше идеального.

Накладные расходы (overhead) — работа, которой не было в последовательной версии и которая появляется только из-за распараллеливания: координация, обмен данными, ожидание.

Откуда берётся потеря

Идеальная картина — N ядер делают по 1/N работы и ускоряют ровно в N раз — нарушается всегда. Причины складываются.

Создание и завершение потоков. Запустить поток или процесс стоит времени. Если работа крошечная, это создание превышает саму пользу.

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

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

Дисбаланс нагрузки. Если работа поделена неровно, самое загруженное ядро определяет общее время, а остальные простаивают в конце.

Модель с накладными расходами

Реалистичнее писать T(N) = T_seq + T_par/N + T_overhead(N), где overhead обычно растёт с N (больше ядер — больше координации). Покажем на расчёте, как фиксированный overhead на каждое ядро убивает выигрыш при мелкой задаче.

# work_per_core — полезная работа, overhead — налог на ядро (в условных единицах)
work_total = 1000.0
overhead_per_core = 30.0

print(f"{'N':>3} {'идеал':>7} {'реально':>8} {'эффект.':>8}")
for n in [1, 2, 4, 8, 16, 32]:
    ideal = work_total / n
    real = work_total / n + overhead_per_core * n  # overhead растёт с N
    speedup = work_total / real
    eff = speedup / n
    print(f"{n:>3} {ideal:>7.1f} {real:>8.1f} {eff:>8.2f}")

Вывод:

  N   идеал  реально  эффект.
  1  1000.0   1030.0     0.97
  2   500.0    560.0     0.89
  4   250.0    370.0     0.68
  8   125.0    365.0     0.34
 16    62.5    542.5     0.12
 32    31.2    991.2     0.03

Поразительно: на 32 ядрах реальное время (991) почти такое же, как на одном ядре (1030) — весь выигрыш от деления работы съеден накладными расходами! Overhead, растущий с N, в какой-то момент перевешивает пользу. Существует оптимальное число ядер — здесь около 4-8, после которого время лишь растёт.

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

Самый коварный overhead — синхронизация кэшей в разделяемой памяти. Когда два ядра пишут в близкие адреса, аппаратура вынуждена гонять строки кэша между ядрами (об этом — урок про false sharing). Этот «тихий» налог не виден в коде, но способен свести ускорение к нулю. В кластере же доминирует сеть: алгоритм с частым обменом мелкими сообщениями проиграет алгоритму, который шлёт редкие крупные пакеты.

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

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

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

Итоги

• Реальное время = последовательная часть + параллельная/N + накладные расходы(N).
• Overhead (потоки, коммуникация, синхронизация, дисбаланс) растёт с числом ядер.
• Существует оптимальное число ядер; за ним добавление ядер замедляет программу.