Информатика / Алгоритмы и анализ данных

Закон Амдала: предел ускорения параллельной программы

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

Опубликовано: 18 октября 2026 г.Обновлено: 18 октября 2026 г.

Формула

S(N)=\frac{1}{(1-p)+p/N}

График Ускорение при параллельной доле 0,8

Четыре исполнителя дают 2,5 раза; верхний предел равен 5.

Обозначения

$S(N)$: отношение исходного времени к параллельному времени, безразмерная величина
$N$: число одинаковых параллельных исполнителей, безразмерная величина
$p$: доля исходного времени, доступная идеальному распараллеливанию, безразмерная величина

Условия применения

Объём задачи фиксирован, N≥1, 0≤p≤1. Доля p измеряется по времени последовательного выполнения той же задачи. Параллельная работа делится равномерно, производительность исполнителей одинакова, затраты на обмен, запуск потоков и синхронизацию в этой идеальной оценке отсутствуют.

Ограничения

Реальное ускорение может быть ниже из-за обмена, диска, памяти и дисбаланса. При изменении размера задачи или поведения кэша сравнение требует уточнения. Число ядер само по себе не определяет p. Закон описывает отношение времён конкретной задачи, а не универсальную характеристику компьютера.

Подробное объяснение

Примем исходное время за единицу. Последовательный участок занимает 1−p и не сокращается при добавлении исполнителей. Параллельный участок в идеале делится на N равных частей и занимает p/N. Сумма этих времён стоит в знаменателе ускорения.

Ускорение определяется как исходное время, делённое на новое. Поэтому при N=1 знаменатель равен единице и S=1, а не нулю. При p=1 все время можно разделить между исполнителями и получается идеальное линейное ускорение S=N.

Если p<1, при росте N параллельная часть стремится к нулю, но последовательная остаётся. Предел ускорения равен 1/(1−p). Даже очень большое число ядер не устраняет участок, который выполняется по очереди. Это ограничение касается выбранного разбиения задачи.

Доля p относится к исходному запуску. После ускорения соотношение этапов меняется: последовательный участок занимает большую долю нового времени. Нельзя повторно подставлять эту новую долю как исходную без переопределения сравниваемых запусков.

Практический расчёт начинают с профилирования, а не с подсчёта строк кода. Короткий участок может занимать почти всё время, а длинный — выполняться мгновенно. Если работа упирается в общий диск, идеальное деление p/N не выполнится даже при формально независимых задачах.

Как пользоваться формулой

Измерьте последовательное время одной фиксированной задачи и определите долю времени распараллеливаемого участка.
Выберите число одинаковых исполнителей N и оцените, допустимо ли пренебречь обменом и дисбалансом нагрузки.
Сложите неизменную долю 1−p с уменьшенной долей p/N, затем возьмите обратную величину этой суммы.
Переведите ускорение обратно во время и сравните с пределом 1/(1−p), если последовательная доля ненулевая.

Историческая справка

Джин Амдал сформулировал аргумент о роли последовательной части вычисления в работе 1967 года о достижении высокой вычислительной производительности. Современная дробь с p и N является привычной математической записью этого ограничения. Позднее обсуждение параллельных систем показало важность различать ускорение одной неизменной задачи и увеличение размера задачи при доступном времени. В 2008 году Марк Хилл и Майкл Марти применили рассуждения Амдала к многоядерным процессорам, подчёркивая влияние архитектуры и ресурсов ядер. На этой странице используется базовая идеализированная модель одинаковых исполнителей. Она полезна для первой оценки, но не заменяет измерение реального приложения и не утверждает бесполезность параллельных вычислений вообще.

Историческая линия формулы

Закон носит имя Джина Амдала и связан с его аргументом 1967 года о последовательной доле вычислений. Используемая запись — модель фиксированной работы; последующие варианты для многоядерных архитектур и масштабируемых задач вводят дополнительные предпосылки.

Пример

Последовательный расчёт длится 100 секунд, из которых 80 секунд можно идеально разделить между четырьмя исполнителями. Тогда p=0,8, N=4. Новое время равно 20+80/4=40 секунд. По формуле S=1/(0,2+0,8/4)=1/0,4=2,5. Ответ: ускорение в 2,5 раза, а не в четыре. Проверка через измерение времени: 100/40=2,5. При неограниченном числе исполнителей в модели остаются 20 секунд, поэтому предельное ускорение равно пяти. Практический запуск может занять больше 40 секунд из-за передачи данных или ожидания медленного участника; эти затраты не были включены в исходные предпосылки.

Частая ошибка

Не считайте долю параллельных строк кода вместо доли времени. Не умножайте p на N: время участка делится на число исполнителей. Не называйте предел 1/(1−p) достижимым на любом конечном N. Не сравнивайте запуски с разными объёмами данных как одну фиксированную задачу без отдельного пояснения.

Практика

Задачи с решением

Девяносто процентов

Условие. Параллельная доля 0,9, исполнителей 10. Найдите идеальное ускорение.

Решение. Знаменатель 0,1+0,9/10=0,19. S=1/0,19=100/19≈5,26316.

Ответ. Около 5,26 раза

Половина времени

Условие. Параллельная доля 0,5. Сравните четыре исполнителя и предел при бесконечном N.

Решение. Для четырёх S=1/(0,5+0,5/4)=1/0,625=1,6. Предел равен 1/0,5=2.

Ответ. 1,6 раза; предел 2 раза

Дополнительные источники

https://cvw.cac.cornell.edu/parallel/efficiency/amdahls-law
https://www.cs.cmu.edu/~18742/papers/Hill2008.pdf

Связанные формулы

Информатика

Двоичный поиск: максимальное число сравнений ключа

$C_{\max}(n)=\lfloor\log_2 n\rfloor+1,\quad n\ge1$

Двоичный поиск в отсортированном массиве отбрасывает половину диапазона после каждого трехстороннего сравнения. В худшем случае для n≥1 требуется не более ⌊log₂ n⌋+1 итераций.

Информатика

Время передачи файла по скорости канала

$t=\frac{I}{v}$

Время передачи файла по скорости канала: формула t=\frac{I}{v} помогает величины t, I, v заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.

Информатика

Размер растрового изображения по пикселям и глубине цвета

$I=W\cdot H\cdot b$

Размер растрового изображения по пикселям и глубине цвета: формула I=W\cdot H\cdot b помогает величины I, W, H, b заданы для одной и той же ситуации, периода или объекта. В тексте есть условия, пример, ошибки и проверка результата.