Закон Амдаля

Формула в архитектуре компьютера

Теоретическое ускорение задержки (через уменьшение задержки, т.е. задержка как метрика — это прошедшее время между входом и выходом в системе) выполнения программы как функции количества процессоров, выполняющих ее, согласно закону Амдаля. Ускорение ограничено последовательной частью программы. Например, если 95% программы можно распараллелить, то теоретически максимальное ускорение с использованием параллельных вычислений составит 20 раз.

В компьютерной архитектуре закон Амдаля (или аргумент Амдаля ^[1] ) представляет собой формулу, которая дает теоретическое ускорение задержки выполнения задачи при фиксированной рабочей нагрузке , которое можно ожидать от системы, ресурсы которой улучшены .

Закон можно сформулировать следующим образом:

«Общее улучшение производительности, достигаемое за счет оптимизации одной части системы, ограничивается долей времени, в течение которого улучшенная часть фактически используется». ^[2]

Он назван в честь ученого-компьютерщика Джина Амдаля и был представлен на Весенней совместной компьютерной конференции Американской федерации обществ обработки информации (AFIPS) в 1967 году.

Закон Амдаля часто используется в параллельных вычислениях для прогнозирования теоретического ускорения при использовании нескольких процессоров. Например, если программе требуется 20 часов для завершения с использованием одного потока, и часть программы продолжительностью один час не может быть распараллелена, то только оставшиеся 19 часов ( p = 0,95 ) времени выполнения могут быть распараллелены. Поэтому, независимо от того, сколько потоков выделено на параллельное выполнение этой программы, минимальное время выполнения всегда больше 1 часа. Следовательно, теоретическое ускорение составляет максимум 20-кратную производительность одного потока, . ${\displaystyle \left({\dfrac {1}{1-p}}=20\right)}$

Универсальный закон масштабируемости (USL), разработанный Нилом Дж. Гюнтером , расширяет закон Амдаля и учитывает дополнительные накладные расходы из-за межпроцессного взаимодействия. USL количественно определяет масштабируемость на основе таких параметров, как конкуренция и согласованность. ^[3]

Определение

Закон Амдаля можно сформулировать следующим образом: ^[4]

${\displaystyle S_{\text{latency}}(s)={\frac {1}{(1-p)+{\frac {p}{s}}}}}$

где

• S- _{латентность} — теоретическое ускорение выполнения всей задачи;
• s — ускорение той части задачи, которая выигрывает от улучшения системных ресурсов;
• p — доля времени выполнения, которую первоначально занимала часть, получающая выгоду от улучшенных ресурсов.

Более того,

${\displaystyle {\begin{cases}S_{\text{latency}}(s)\leq {\dfrac {1}{1-p}}\\[8pt]\lim \limits _{s\to \infty }S_{\text{latency}}(s)={\dfrac {1}{1-p}}.\end{cases}}}$

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

Закон Амдаля применим только к случаям, когда размер проблемы фиксирован. На практике, по мере того, как становится доступно больше вычислительных ресурсов, они, как правило, используются для более крупных задач (больших наборов данных), и время, затрачиваемое на параллелизуемую часть, часто растет гораздо быстрее, чем на изначально последовательную работу. В этом случае закон Густафсона дает менее пессимистичную и более реалистичную оценку параллельной производительности. ^[5]

Вывод

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

• часть, которая не получает выгоды от улучшения ресурсов системы;
• часть, которая получает выгоду от улучшения ресурсов системы.

Примером может служить компьютерная программа, обрабатывающая файлы. Часть этой программы может сканировать каталог диска и создавать список файлов внутри памяти. После этого другая часть программы передает каждый файл в отдельный поток для обработки. Часть, которая сканирует каталог и создает список файлов, не может быть ускорена на параллельном компьютере, но часть, которая обрабатывает файлы, может.

Время выполнения всей задачи до улучшения ресурсов системы обозначается как . Оно включает время выполнения той части, которая не получит выгоду от улучшения ресурсов, и время выполнения той, которая получит выгоду от этого. Доля времени выполнения задачи, которая получит выгоду от улучшения ресурсов, обозначается как . Та, которая касается части, которая не получит выгоду от этого, поэтому равна . Тогда: ${\displaystyle T}$ ${\displaystyle p}$ ${\displaystyle 1-p}$

${\displaystyle T=(1-p)T+pT.}$

Именно выполнение той части, которая выигрывает от улучшения ресурсов, ускоряется фактором после улучшения ресурсов. Следовательно, время выполнения той части, которая не выигрывает от этого, остается прежним, в то время как часть, которая выигрывает от этого, становится: ${\displaystyle s}$

${\displaystyle {\frac {p}{s}}T.}$

Теоретическое время выполнения всей задачи после улучшения ресурсов составит: ${\displaystyle T(s)}$

${\displaystyle T(s)=(1-p)T+{\frac {p}{s}}T.}$

Закон Амдаля дает теоретическое ускорение задержки выполнения всей задачи при фиксированной рабочей нагрузке ${\displaystyle W}$ , что дает

${\displaystyle S_{\text{latency}}(s)={\frac {TW}{T(s)W}}={\frac {T}{T(s)}}={\frac {1}{1-p+{\frac {p}{s}}}}.}$

Параллельные программы

Если 30% времени выполнения может быть предметом ускорения, p будет равно 0,3; если улучшение делает затронутую часть в два раза быстрее, s будет равно 2. Закон Амдаля гласит, что общее ускорение от применения улучшения составит:

${\displaystyle S_{\text{latency}}={\frac {1}{1-p+{\frac {p}{s}}}}={\frac {1}{1-0.3+{\frac {0.3}{2}}}}=1.18.}$

Например, предположим, что нам дана последовательная задача, которая разделена на четыре последовательные части, проценты времени выполнения которых составляют p 1 = 0,11 , p 2 = 0,18 , p 3 = 0,23 и p 4 = 0,48 соответственно. Затем нам говорят, что 1-я часть не ускорена, поэтому s 1 = 1 , в то время как 2-я часть ускорена в 5 раз, поэтому s 2 = 5 , 3-я часть ускорена в 20 раз, поэтому s 3 = 20 , а 4-я часть ускорена в 1,6 раза, поэтому s 4 = 1,6 . Используя закон Амдаля, общее ускорение равно

${\displaystyle S_{\text{latency}}={\frac {1}{{\frac {p1}{s1}}+{\frac {p2}{s2}}+{\frac {p3}{s3}}+{\frac {p4}{s4}}}}={\frac {1}{{\frac {0.11}{1}}+{\frac {0.18}{5}}+{\frac {0.23}{20}}+{\frac {0.48}{1.6}}}}=2.19.}$

Обратите внимание, что ускорение 2-й и 3-й частей в 5 и 20 раз соответственно не оказывает большого влияния на общее ускорение, тогда как 4-я часть (48% времени выполнения) ускоряется всего в 1,6 раза.

Серийные программы

Предположим, что задача состоит из двух независимых частей, A и B. Часть B занимает примерно 25% времени всего вычисления. Работая очень усердно, можно сделать эту часть в 5 раз быстрее, но это сократит время всего вычисления лишь немного. Напротив, может потребоваться выполнить меньше работы, чтобы часть A выполнялась в два раза быстрее. Это сделает вычисления намного быстрее, чем при оптимизации части B , даже несмотря на то, что ускорение части B больше с точки зрения соотношения (в 5 раз против 2 раз).

Например, с последовательной программой из двух частей A и B, для которой T _A = 3 с и T _B = 1 с ,

• если часть B заставить работать в 5 раз быстрее, то есть s = 5 и p = T _B /( T _A + T _B ) = 0,25 , то $${\displaystyle S_{\text{latency}}={\frac {1}{1-0.25+{\frac {0.25}{5}}}}=1.25;}$$
• если часть A заставить работать в 2 раза быстрее, то есть s = 2 и p = T _A /( T _A + T _B ) = 0,75 , то $${\displaystyle S_{\text{latency}}={\frac {1}{1-0.75+{\frac {0.75}{2}}}}=1.60.}$$

Поэтому, заставить часть A работать в 2 раза быстрее лучше, чем заставить часть B работать в 5 раз быстрее. Процентное улучшение скорости можно рассчитать как

${\displaystyle {\text{percentage improvement}}=100\left(1-{\frac {1}{S_{\text{latency}}}}\right).}$

• Улучшение части A в 2 раза увеличит общую скорость программы в 1,60 раза, что сделает ее на 37,5% быстрее исходного вычисления.
• Однако улучшение части B в 5 раз, что, предположительно, потребует больше усилий, позволит достичь общего коэффициента ускорения всего лишь в 1,25 раза, что сделает ее на 20% быстрее.

Оптимизация последовательной части параллельных программ

Если непараллелизуемая часть оптимизирована в множитель , то ${\displaystyle O}$

${\displaystyle T(O,s)=(1-p){\frac {T}{O}}+{\frac {p}{s}}T.}$

Из закона Амдаля следует, что ускорение за счет параллелизма определяется выражением

${\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}.}$

Когда , то имеем , что означает, что ускорение измеряется относительно времени выполнения после оптимизации непараллелизуемой части. ${\displaystyle s=1}$ ${\displaystyle S_{\text{latency}}(O,s)=1}$

Когда , ${\displaystyle s=\infty }$

${\displaystyle S_{\text{latency}}(O,\infty )={\frac {T(O)}{T(O,s)}}={\frac {(1-p){\frac {1}{O}}+{p}}{{\frac {1-p}{O}}+{\frac {p}{s}}}}=1+{\frac {p}{1-p}}O.}$

Если , и , то: ${\displaystyle 1-p=0.4}$ ${\displaystyle O=2}$ ${\displaystyle s=5}$

${\displaystyle S_{\text{latency}}(O,s)={\frac {T(O)}{T(O,s)}}={\frac {{0.4}{\frac {1}{2}}+0.6}{{\frac {0.4}{2}}+{\frac {0.6}{5}}}}=2.5.}$

Преобразование последовательных частей параллельных программ в параллелизуемые

Далее рассмотрим случай, когда непараллелизуемая часть уменьшается в раз , а параллелизуемая часть соответственно увеличивается. Тогда ${\displaystyle O'}$

${\displaystyle T'(O',s)={\frac {1-p}{O'}}T+\left(1-{\frac {1-p}{O'}}\right){\frac {T}{s}}.}$

Из закона Амдаля следует, что ускорение за счет параллелизма определяется выражением

${\displaystyle S'_{\text{latency}}(O',s)={\frac {T'(O')}{T'(O',s)}}={\frac {1}{{\frac {1-p}{O'}}+\left(1-{\frac {1-p}{O'}}\right){\frac {1}{s}}}}.}$

Отношение к закону убывающей доходности

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

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

Этот анализ не учитывает другие потенциальные узкие места, такие как пропускная способность памяти и пропускная способность ввода-вывода. Если эти ресурсы не масштабируются с числом процессоров, то простое добавление процессоров обеспечивает еще меньшую отдачу.

Следствием закона Амдаля является то, что для ускорения реальных приложений, которые имеют как последовательные, так и параллельные части, требуются гетерогенные вычислительные методы. ^[6] Существуют новые модели ускорения и потребления энергии, основанные на более общем представлении гетерогенности, называемом гетерогенностью нормальной формы, которые поддерживают широкий спектр гетерогенных многоядерных архитектур. Эти методы моделирования направлены на прогнозирование энергоэффективности системы и диапазонов производительности, а также облегчают исследования и разработки на уровне аппаратного и системного программного обеспечения. ^{[7] [8]}

Смотрите также

• Закон Густафсона
• Универсальный закон вычислительной масштабируемости
• Анализ параллельных алгоритмов
• Метод критического пути
• Закон Мура

Ссылки

1. Роджерс, Дэвид П. (июнь 1985 г.). «Улучшения в проектировании многопроцессорных систем». ACM SIGARCH Computer Architecture News . 13 (3). Нью-Йорк, Нью-Йорк, США: ACM : 225–231 [стр. 226]. doi : 10.1145/327070.327215. ISBN 0-8186-0634-7. ISSN  0163-5964. S2CID  7083878.
2. Reddy, Martin (2011). API Design for C++ . Берлингтон, Массачусетс : Morgan Kaufmann Publishers . стр. 210. doi :10.1016/C2010-0-65832-9. ISBN 978-0-12-385003-4. LCCN  2010039601. OCLC  666246330.
3. Гюнтер, Нил (2007). Партизанское планирование мощностей: тактический подход к планированию высокомасштабируемых приложений и сервисов . ISBN 978-3540261384.
4. Брайант, Рэндал Э.; Дэвид, О'Халларон (2016), Компьютерные системы: точка зрения программиста (3-е изд.), Pearson Education, стр. 58, ISBN 978-1-488-67207-1
5. МакКул, Майкл; Рейндерс, Джеймс; Робинсон, Арч (2013). Структурированное параллельное программирование: шаблоны для эффективных вычислений . Elsevier. стр. 61. ISBN 978-0-12-415993-8.
6. Хилл, Марк Д.; Марти, Майкл Р. (2008). «Закон Амдаля в эпоху многоядерных процессоров». Computer . 41 (7): 33–38. CiteSeerX 10.1.1.221.8635 . doi :10.1109/MC.2008.209. 
7. Рафиев, Ашур; Аль-Хаянни, Мохаммед АН; Ся, Фэй; Шафик, Ришад; Романовский, Александр; Яковлев, Алекс (2018-07-01). «Модели масштабирования ускорения и мощности для гетерогенных многоядерных систем». Труды IEEE по многомасштабным вычислительным системам . 4 (3): 436–449. doi :10.1109/TMSCS.2018.2791531. ISSN  2332-7766. S2CID  52287374.
8. Аль-Хаянни, Мохаммед А. Ноаман; Ся, Фэй; Рафиев, Ашур; Романовский, Александр; Шафик, Ришад; Яковлев, Алекс (июль 2020 г.). «Закон Амдаля в контексте гетерогенных многоядерных систем – обзор». IET Computers & Digital Techniques . 14 (4): 133–148. doi : 10.1049/iet-cdt.2018.5220 . ISSN  1751-8601. S2CID  214415079.

Дальнейшее чтение

• Амдаль, Джин М. (1967). «Обоснованность подхода с использованием одного процессора для достижения крупномасштабных вычислительных возможностей» (PDF) . Труды конференции AFIPS (30): 483–485. doi :10.1145/1465482.1465560. S2CID  195607370.

Внешние ссылки

• Джин М. Амдал (1989), Устное историческое интервью с Джином М. Амдалом , Институт Чарльза Бэббиджа , Университет Миннесоты, hdl :11299/104341. Амдаль обсуждает свою дипломную работу в Университете Висконсина и свой проект WISC . Обсуждает свою роль в разработке нескольких компьютеров для IBM, включая STRETCH , IBM 701 и IBM 704 . Он обсуждает свою работу с Натаниэлем Рочестером и управление процессом проектирования в IBM. Упоминает работу с Ramo-Wooldridge , Aeronutronic и Computer Sciences Corporation
• «Закон Амдаля» Джоэла Ф. Кляйна, Wolfram Demonstrations Project (2007)
• Закон Амдаля в эпоху многоядерности (июль 2008 г.)