В этой статье мы поговорим о законе Амдала (Amdahl’s law) и он том, в чём его суть.
Эта запись также доступна в нашем канале Telegram для разработчиков.
Сущность закона Амдала
Этот интересный закон был придуман Джином Амдалом несколько десятилетий назад, его время от времени упоминают в контексте информационных систем, так что знать его суть не помешает.
Вообще, смысл данного закона весьма простой: если мы “улучшаем” (ускоряем) часть некой системы, то общий эффект на быстродействие всей системы будет зависеть от того, насколько этот компонент был важен (то есть какой процент времени работа с ним занимает) и насколько мы его улучшили.
Звучит как пассаж от капитана Очевидность, но для оценки есть конкретная формула. Записывается она следующим образом:
S = 1 / ( (1 - a) + (a / k) )
S— это то, насколько быстрее система будет работать в общем целом (в полтора, два раза, и так далее).a— доля исходного времени выполнения задачи, которую занимает компонент, подлежащий ускорению (значение от 0.0 до 1.0).k— фактор “улучшения” компонента.
Пример
Ну, к примеру, если мы знаем, что в нашей системе определённый компонент затрачивает 60% всего времени, необходимого для выполнения задачи, и мы улучшаем (ускоряем) этот компонент аж в 3 раза, то по факту S будет равно 1.67. Иными словами, вся система ускорится чуть более, чем в полтора раза. Казалось бы, мы очень серьёзно улучшили немалую часть системы, но окончательная выгода оказалась не такой уж большой.
Применение закона
Вообще говоря, этот закон может применяться далеко не только в информационных системах. К примеру, водитель грузовика знает, что ему нужно проехать 2500 километров, а скорость будет составлять условные 100 км/ч. Значит, вся поездка займёт 25 часов без учёта остановок.
Тогда вопрос: если мы предположим, что на участке пути в 1500 километров можно ехать со скоростью в 150 км/ч, то насколько быстрее мы реально доедем? Ответить на этот вопрос несложно.
Участок в 1500 км из всей дороги в 2500 км — это 60%, то есть a = 0.6.
Если мы едем на этом участке 150 км/ч, то k = 1.5, то есть в полтора раза быстрее.
Следовательно, финальное S равно 1.25, иными словами, приедем мы на 5 часов раньше.
Заметьте, что мы можем использовать долю расстояния вместо доли времени только потому, что изначально грузовик двигался с одинаковой скоростью на всём маршруте. Если бы скорости на разных участках отличались, пришлось бы отдельно рассчитывать время для каждого из них.
Закон Амдала и многоядерные процессоры
Кстати, закон Амдала особенно интересен в контексте параллельных вычислений. Представьте, что мы написали программу, 80% времени выполнения которой можно распараллелить, а оставшиеся 20% приходится выполнять последовательно. Теперь допустим, что мы запускаем её на четырёх процессорных ядрах.
В идеальных условиях параллельную часть можно ускорить в четыре раза. Подставляем значения в нашу формулу:
S = 1 / ((1 - 0.8) + (0.8 / 4))
= 1 / (0.2 + 0.2)
= 2.5
Выходит, что даже с четырьмя ядрами программа ускорится всего в 2.5 раза, а не в четыре. И это мы ещё не учитываем накладные расходы на создание потоков, синхронизацию и обмен данными!
Более того, даже если мы каким-то чудом получим бесконечное количество ядер, максимальное ускорение составит 1 / 0.2 = 5. Всё потому, что оставшиеся 20% работы никуда не делись и по-прежнему выполняются последовательно.
Вот такая, понимаешь, загогулина: можно купить хоть тысячу процессоров, но если программа большую часть времени занимается последовательной работой, железо само по себе её не спасёт.
Частный случай
Любопытно, что будет, если одну из частей системы мы сделаем настолько быстрой, что она практически не затрачивает никакого времени (это время настолько мало, что им можно пренебречь).
То есть, другими словами, что будет, если k равно бесконечности? В этом случае часть a / k в формуле уходит, потому что значение будет стремиться к нулю. Тогда вся формула превращается в S = 1 / ( 1 - a ). Следовательно, даже если мы возьмём 60% всей системы и ускорим её так, что она будет выполнять необходимые операции мгновенно, всё равно общий рост производительности будет только 2.5 (или 1 / 0.4).