Закон Амдала

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

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

В компьютерной архитектуре закон Амдала (или аргумент Амдала ^[1] ) представляет собой формулу, которая дает теоретическое ускорение задержки выполнения задачи при фиксированной рабочей нагрузке , которое можно ожидать от системы, ресурсы которой улучшены. В нем говорится, что « общее улучшение производительности, достигаемое за счет оптимизации одной части системы, ограничено долей времени, в течение которого улучшенная часть фактически используется ». ^[2] Он назван в честь ученого-компьютерщика Джина Амдала и был представлен на весенней совместной компьютерной конференции Американской федерации обществ обработки информации (AFIPS) в 1967 году.

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

Определение

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

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

где

• S _latency — теоретическое ускорение выполнения всей задачи;
• 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}}}$

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

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

Вывод

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

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

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

Время выполнения всей задачи до улучшения ресурсов системы обозначим . Оно включает в себя время выполнения той части, которая не выиграет от улучшения ресурсов, и время выполнения той части, которая от этого выиграет. Доля времени выполнения задачи, которая выиграет от улучшения ресурсов, обозначается . Следовательно, речь идет о той части, которая не получит от этого пользы . Затем: ${\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 , а четвертая часть ускоряется в 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 раз быстрее, но время всего вычисления при этом сокращается лишь незначительно. Напротив, чтобы часть А выполнялась вдвое быстрее, возможно, потребуется выполнить меньше работы . Это сделает вычисления намного быстрее, чем при оптимизации части B , даже несмотря на то, что ускорение части B в соотношении больше (в 5 раз против 2 раз).

Например, с последовательной программой, состоящей из двух частей _A и B , _для которых TA = 3 с и TB = 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).}$

• Улучшение части А в 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 ).

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

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

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

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

Рекомендации

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

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

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

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

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