Закон Амдала
Зако́н Амдала (англ. Amdahl's law, иногда также Закон Амдаля-Уэра) — иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей. Джин Амдал сформулировал закон в 1967 году, обнаружив простое по существу, но непреодолимое по содержанию ограничение на рост производительности при распараллеливании вычислений: «В случае, когда задача разделяется на несколько частей, суммарное время её выполнения на параллельной системе не может быть меньше времени выполнения самого длинного фрагмента».[1] Согласно этому закону, ускорение выполнения программы за счёт распараллеливания её инструкций на множестве вычислителей ограничено временем, необходимым для выполнения её последовательных инструкций.
Содержание
Математическое выражение
Пусть необходимо решить некоторую вычислительную задачу. Предположим, что её алгоритм таков, что доля <math>\alpha</math> от общего объёма вычислений может быть получена только последовательными расчётами, а, соответственно, доля <math>1 - \alpha</math> может быть распараллелена идеально (то есть время вычисления будет обратно пропорционально числу задействованных узлов <math>p</math>). Тогда ускорение, которое может быть получено на вычислительной системе из <math>p</math> процессоров, по сравнению с однопроцессорным решением не будет превышать величины
<math>S_p = \cfrac{1}{\alpha + \cfrac{1 - \alpha}{p}}</math>
Иллюстрация
Таблица показывает, во сколько раз быстрее выполнится программа с долей последовательных вычислений <math>\alpha</math> при использовании <math>p</math> процессоров.
| <math>\alpha</math> \ <math>p</math> | 10 | 100 | 1000 |
|---|---|---|---|
| 0 | 10 | 100 | 1000 |
| 10% | 5.263 | 9.174 | 9.910 |
| 25% | 3.077 | 3.883 | 3.988 |
| 40% | 2.174 | 2.463 | 2.496 |
Из таблицы видно, что только алгоритм, вовсе не содержащий последовательных вычислений (<math>\alpha = 0</math>), позволяет получить линейный прирост производительности с ростом количества вычислителей в системе. Если доля последовательных вычислений в алгоритме равна 25 %, то увеличение числа процессоров до 10 дает ускорение в 3,077 раза, а увеличение числа процессоров до 1000 даст ускорение в 3,988 раза.
Отсюда же очевидно, что при доле последовательных вычислений <math>\alpha</math> общий прирост производительности не может превысить <math>1 / \alpha</math>. Так, если половина кода — последовательная, то общий прирост никогда не превысит двух.
Идейное значение
Закон Амдала показывает, что прирост эффективности вычислений зависит от алгоритма задачи и ограничен сверху для любой задачи с <math>\alpha \ne 0</math>. Не для всякой задачи имеет смысл наращивание числа процессоров в вычислительной системе.
Более того, если учесть время, необходимое для передачи данных между узлами вычислительной системы, то зависимость времени вычислений от числа узлов будет иметь максимум. Это накладывает ограничение на масштабируемость вычислительной системы, то есть означает, что с определенного момента добавление новых узлов в систему будет увеличивать время расчёта задачи.
См. также
Напишите отзыв о статье "Закон Амдала"
Литература
- Антонов А. [old.computerra.ru/2002/430/15838/ Под законом Амдала] (рус.) // Компьютерра. — 11.02.2002. — № 430.
- [www.intuit.ru/department/calculate/paralltp/2/5.html Оценка максимально достижимого параллелизма]. Лекция из курса «Теория и практика параллельных вычислений» на сайте Института дистанционного обучения ИНТУИТ
- [www.researchgate.net/publication/228569958_Calculation_of_the_acceleration_of_parallel_programs_as_a_function_of_the_number_of_threads Calculation of the acceleration of parallel programs as a function of the number of threads by George Popov, Valeri Mladenov and Nikos Mastorakis]
Примечания
- ↑ При условии одинаковой скорости всех вычислителей.
| ||||||||||||||||||||||||||||||||||||||||||
Отрывок, характеризующий Закон Амдала
«По причине болезненных ваших припадков, извольте, ваше высокопревосходительство, с получения сего, отправиться в Калугу, где и ожидайте дальнейшего повеления и назначения от его императорского величества».Но вслед за отсылкой Бенигсена к армии приехал великий князь Константин Павлович, делавший начало кампании и удаленный из армии Кутузовым. Теперь великий князь, приехав к армии, сообщил Кутузову о неудовольствии государя императора за слабые успехи наших войск и за медленность движения. Государь император сам на днях намеревался прибыть к армии.
Старый человек, столь же опытный в придворном деле, как и в военном, тот Кутузов, который в августе того же года был выбран главнокомандующим против воли государя, тот, который удалил наследника и великого князя из армии, тот, который своей властью, в противность воле государя, предписал оставление Москвы, этот Кутузов теперь тотчас же понял, что время его кончено, что роль его сыграна и что этой мнимой власти у него уже нет больше. И не по одним придворным отношениям он понял это. С одной стороны, он видел, что военное дело, то, в котором он играл свою роль, – кончено, и чувствовал, что его призвание исполнено. С другой стороны, он в то же самое время стал чувствовать физическую усталость в своем старом теле и необходимость физического отдыха.
29 ноября Кутузов въехал в Вильно – в свою добрую Вильну, как он говорил. Два раза в свою службу Кутузов был в Вильне губернатором. В богатой уцелевшей Вильне, кроме удобств жизни, которых так давно уже он был лишен, Кутузов нашел старых друзей и воспоминания. И он, вдруг отвернувшись от всех военных и государственных забот, погрузился в ровную, привычную жизнь настолько, насколько ему давали покоя страсти, кипевшие вокруг него, как будто все, что совершалось теперь и имело совершиться в историческом мире, нисколько его не касалось.
Чичагов, один из самых страстных отрезывателей и опрокидывателей, Чичагов, который хотел сначала сделать диверсию в Грецию, а потом в Варшаву, но никак не хотел идти туда, куда ему было велено, Чичагов, известный своею смелостью речи с государем, Чичагов, считавший Кутузова собою облагодетельствованным, потому что, когда он был послан в 11 м году для заключения мира с Турцией помимо Кутузова, он, убедившись, что мир уже заключен, признал перед государем, что заслуга заключения мира принадлежит Кутузову; этот то Чичагов первый встретил Кутузова в Вильне у замка, в котором должен был остановиться Кутузов. Чичагов в флотском вицмундире, с кортиком, держа фуражку под мышкой, подал Кутузову строевой рапорт и ключи от города. То презрительно почтительное отношение молодежи к выжившему из ума старику выражалось в высшей степени во всем обращении Чичагова, знавшего уже обвинения, взводимые на Кутузова.
Разговаривая с Чичаговым, Кутузов, между прочим, сказал ему, что отбитые у него в Борисове экипажи с посудою целы и будут возвращены ему.
– C'est pour me dire que je n'ai pas sur quoi manger… Je puis au contraire vous fournir de tout dans le cas meme ou vous voudriez donner des diners, [Вы хотите мне сказать, что мне не на чем есть. Напротив, могу вам служить всем, даже если бы вы захотели давать обеды.] – вспыхнув, проговорил Чичагов, каждым словом своим желавший доказать свою правоту и потому предполагавший, что и Кутузов был озабочен этим самым. Кутузов улыбнулся своей тонкой, проницательной улыбкой и, пожав плечами, отвечал: – Ce n'est que pour vous dire ce que je vous dis. [Я хочу сказать только то, что говорю.]
В Вильне Кутузов, в противность воле государя, остановил большую часть войск. Кутузов, как говорили его приближенные, необыкновенно опустился и физически ослабел в это свое пребывание в Вильне. Он неохотно занимался делами по армии, предоставляя все своим генералам и, ожидая государя, предавался рассеянной жизни.
Выехав с своей свитой – графом Толстым, князем Волконским, Аракчеевым и другими, 7 го декабря из Петербурга, государь 11 го декабря приехал в Вильну и в дорожных санях прямо подъехал к замку. У замка, несмотря на сильный мороз, стояло человек сто генералов и штабных офицеров в полной парадной форме и почетный караул Семеновского полка.
Курьер, подскакавший к замку на потной тройке, впереди государя, прокричал: «Едет!» Коновницын бросился в сени доложить Кутузову, дожидавшемуся в маленькой швейцарской комнатке.
