Закон Амдала: почему последовательная часть всё ограничивает

Урок выводит и считает закон Амдала — самый важный закон в параллельных вычислениях.

Закон Амдала: если доля p работы распараллеливается, а доля (1-p) обязана идти последовательно, то ускорение на N процессорах равно S(N) = 1 / ((1-p) + p/N).

Интуиция

Представьте задачу, где 95% времени можно распараллелить, а 5% — нет (чтение файла, финальная запись результата). Даже с бесконечным числом процессоров эти 5% никуда не денутся. Параллельная часть схлопнется почти в ноль, а последовательная останется. Значит, общее время не может стать меньше 5% исходного, то есть ускорение не превысит 1/0.05 = 20. Сколько бы ядер вы ни добавили — потолок 20×. Это и есть жестокое сердце закона Амдала: не распараллеленная доля задаёт предел.

Формула и предел

S(N) = 1 / ((1-p) + p/N). При N → ∞ член p/N стремится к нулю, и остаётся S(∞) = 1/(1-p). Несколько значений потолка:

Считаем сами

Посчитаем ускорение для p = 0.95 при разном числе процессоров и убедимся, что оно подползает к 20 и упирается в потолок.

def amdahl(p, n):
    # p — параллельная доля, n — число процессоров
    return 1.0 / ((1 - p) + p / n)

p = 0.95
print(f"параллельная доля p = {p}, потолок = {1/(1-p):.0f}x")
print(f"{'N':>8} {'speedup':>8}")
for n in [1, 2, 4, 8, 16, 1_000_000]:
    print(f"{n:>8} {amdahl(p, n):>8.3f}")

Вывод:

параллельная доля p = 0.95, потолок = 20x
       N  speedup
       1    1.000
       2    1.905
       4    3.478
       8    5.926
      16    9.143
 1000000   20.000

Миллион процессоров дал ровно 20× — ни на йоту больше потолка. А переход с 8 на 16 ядер поднял ускорение лишь с 5.9 до 9.1: отдача от каждого нового ядра стремительно падает.

Этот эффект убывающей отдачи — главная причина, по которой нельзя «купить» производительность ядрами. Удвоив ядра с 8 до 16, мы заплатили вдвое больше, а ускорение выросло лишь в полтора раза. Удвоив с 16 до 32, получим ещё меньше прироста. В какой-то момент каждое новое ядро стоит как предыдущее, но почти ничего не добавляет. Закон Амдала позволяет посчитать эту точку заранее и не тратить деньги за её пределом. Именно поэтому опытные инженеры сначала измеряют последовательную долю своей задачи, а уже потом решают, сколько ядер имеет смысл задействовать.

Практический вывод

Прежде чем закупать кластер, оцените свою последовательную долю. Если в задаче 30% работы неустранимо последовательны (p = 0.7), потолок — всего 3.3×, и тысяча ядер бесполезна. Часто выгоднее не добавлять ядра, а уменьшать последовательную часть: переписать ввод-вывод, убрать глобальную блокировку, распараллелить инициализацию. Каждый отвоёванный у последовательности процент сдвигает потолок вверх непропорционально сильно.

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

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

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

• Игнорировать последовательную долю и удивляться, что ускорение «застряло».
• Думать, что закон Амдала запрещает любую пользу от ядер — он лишь задаёт потолок, до которого ещё надо дойти.
• Забывать, что при росте размера задачи последовательная доля может уменьшаться (об этом — закон Густафсона).

Итоги

• S(N) = 1/((1-p) + p/N); при N → ∞ потолок равен 1/(1-p).
• Даже малая непараллелимая доля жёстко ограничивает ускорение.
• Уменьшать последовательную часть часто выгоднее, чем добавлять ядра.