Закон Амдала

Ускорение программы с помощью параллельных вычислений на нескольких процессорах ограничено размером последовательной части программы. Например, если можно распараллелить 95 % программы, то теоретически максимальное ускорение будет 20-кратным, невзирая на то, сколько процессоров используется.

Зако́н Амдала (англ. Amdahl's law, иногда также Закон Амдаля — Уэра) — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого медленного фрагмента». Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.

Математическое выражение

Пусть необходимо решить некоторую вычислительную задачу. Предположим, что её алгоритм таков, что доля $\alpha$ от общего объёма вычислений может быть получена только последовательными расчётами, а, соответственно, доля $1-\alpha$ может быть распараллелена идеально (то есть время вычисления будет обратно пропорционально числу задействованных узлов $p$). Тогда ускорение, которое может быть получено на вычислительной системе из $p$ процессоров, по сравнению с однопроцессорным решением не будет превышать величины

$S_{p}={\cfrac {1}{\alpha +{\cfrac {1-\alpha }{p}}}}$

Иллюстрация

Таблица показывает, во сколько раз быстрее выполнится программа с долей последовательных вычислений $\alpha$ при использовании $p$ процессоров.

$\alpha$ \ $p$	10	100	1 000
0	10	100	1 000
10 %	5,263	9,174	9,910
25 %	3,077	3,883	3,988
40 %	2,174	2,463	2,496

Из таблицы видно, что только алгоритм, вовсе не содержащий последовательных вычислений ($\alpha =0$), позволяет получить линейный прирост производительности с ростом количества вычислителей в системе. Если доля последовательных вычислений в алгоритме равна 25 %, то увеличение числа процессоров до 10 дает ускорение в 3.077 раз, а увеличение числа процессоров до 1000 даст ускорение в 3.988 раз.

Отсюда же очевидно, что при доле последовательных вычислений $\alpha$ общий прирост производительности не может превысить $1/\alpha$. Так, если половина кода — последовательная, то общий прирост никогда не превысит двух.

Идейное значение

Закон Амдала показывает, что прирост эффективности вычислений зависит от алгоритма задачи и ограничен сверху для любой задачи с $\alpha \neq 0$. Не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной системе.

Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь минимум. Это накладывает ограничение на масштабируемость вычислительной системы, то есть означает, что с определенного момента добавление новых узлов в систему будет увеличивать время расчёта задачи.

Формулировка для многоядерных вычислителей: производительность многоядерной системы ограничивается наиболее узким местом — доступом к общей памяти ядер микропроцессора.

См. также

• Закон Густафсона — Барсиса
• Закон Мура
• Кластер (группа компьютеров)
• Компьютеры пятого поколения

Литература

• Антонов А. Под законом Амдала // Компьютерра. — 11.02.2002. — № 430. (недоступная ссылка)
• Calculation of the acceleration of parallel programs as a function of the number of threads by George Popov, Valeri Mladenov and Nikos Mastorakis