Закон Густафсона: масштабирование задачи

Урок показывает, почему на практике большие задачи масштабируются лучше, чем предсказывает Амдал.

Закон Густафсона: если с ростом числа процессоров мы решаем пропорционально большую задачу, масштабированное ускорение равно S(N) = (1-p) + N·p, где p — параллельная доля работы при размере на N процессоров.

Спор двух законов

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

Формула и расчёт

В густафсоновской постановке ускорение S(N) = (1-p) + N·p. Здесь нет потолка: чем больше N, тем больше ускорение. Посчитаем для той же параллельной доли p = 0.95.

def gustafson(p, n):
    return (1 - p) + n * p

p = 0.95
print(f"параллельная доля p = {p}")
print(f"{'N':>4} {'масштаб. ускорение':>20}")
for n in [1, 2, 4, 8, 16]:
    print(f"{n:>4} {gustafson(p, n):>20.2f}")

Вывод:

параллельная доля p = 0.95
   N   масштаб. ускорение
   1                 1.00
   2                 1.95
   4                 3.85
   8                 7.65
  16                15.25

Сравните: Амдал на 16 ядрах дал лишь 9.1×, а Густафсон — 15.25×. Разница не в математике, а в постановке вопроса. Амдал спрашивает «во сколько раз быстрее решим ту же задачу?», Густафсон — «насколько большую задачу решим за то же время?».

Эта смена вопроса объясняет, почему суперкомпьютеры вообще имеют смысл. Если бы действовал только Амдал, наращивать тысячи ядер было бы бессмысленно — потолок упёрся бы в несколько десятков. Но учёные используют большие машины не для того, чтобы решить вчерашнюю задачу за миллисекунды, а чтобы решить задачу, которая вчера была неподъёмной: смоделировать климат планеты с разрешением в километр вместо ста, обучить модель на терабайтах вместо гигабайтов. С каждым добавленным ядром растёт не скорость старой задачи, а масштаб новой — и в этом режиме тысячи ядер работают полезно.

Когда какой закон применим

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

Оба закона описывают одну реальность, просто с разных сторон. Если зафиксировать размер — увидите потолок Амдала. Если позволить размеру расти — увидите масштабирование Густафсона. Большинство задач «больших данных» и научных симуляций живут в режиме Густафсона: ценность не в том, чтобы фиксированную задачу решить мгновенно, а в том, чтобы за разумное время решать всё более крупные.

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

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

Итоги

• Густафсон: S(N) = (1-p) + N·p — без потолка, ускорение растёт с N.
• Применим, когда задача масштабируется вместе с числом процессоров (слабое масштабирование).
• Амдал и Густафсон — два взгляда на одну реальность: фиксированная задача против растущей.