Закон Амдала

Линейное ускорение считается теоретическим пределом эффективности вычислений на мультипроцессоре. Обоснованием этого свойства параллельной обработки служит закон Амдала. Ключевым моментом закона Амдала является доля последовательной обработкиотносительно полноговремени выполнения параллельной программы, когда в параллельной программе используется единственный процессор. Эта долянезависима от числа процессоров. Пусть f – доля таких вычислений в общем объеме, 0 < f < 1. Максимальное ускорение S, достижимое на вычислительной системе из p процессоров, можно оценить при помощи следующей формулы:

.

Вопрос: может ли существовать ускорение, большее, чем число процессоров (суперлинейное) S_p > p и E_p > 1?

Ответ: Нет. Каждый параллельный алгоритм, решая задачу за время T_p с p процессорами, может в принципе моделироваться последовательным алгоритмом за время T₁ = pT_p на единственном процессоре.

Тем не менее, суперлинейное ускорение обнаружено экспериментально при решении нескольких классов задач. Распространено мнение, что суперлинейное ускорение – это результат некорректной методики измерений времен T₁ и T_p. Считается, что одной из возможных причин служит эффект различия в алгоритмах кэширования вследствие различий оборудования и операционных систем.

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

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

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

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

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