Закон Амдала

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

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

Закон можно сформулировать так:

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

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

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

Определение

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

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

где

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

Более того,

{\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 ]}

Вывод

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

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

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

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

T=(1-p)T+pT.

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

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

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

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

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

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. Закон Амдала гласит, что общее ускорение применения улучшения будет:

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 . Используя закон Амдала, общее ускорение составит

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.

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

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

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

Например, с последовательной программой, состоящей из двух частей B , для которых TA _и = 3 с и TB _A = 1 с ,

если часть B заставить работать в 5 раз быстрее, то есть s = 5 и p = T _B /( T _A + T _B ) = 0,25 , тогда $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 , то $S_{\text{latency}}={\frac {1}{1-0.75+{\frac {0.75}{2}}}}=1.60.$

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

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

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

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

Если нераспараллеливаемая часть оптимизирована в раз $O$ , затем

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

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

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}}}}.

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

Когда $s=\infty$ ,

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.

Если $1-p=0.4$ , $O=2$ и $s=5$ , затем:

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.

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

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

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

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

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 ]}

См. также

Ссылки

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

[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. дои : 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 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

v т и Параллельные вычисления
General	Distributed computing Parallel computing Massively parallel Cloud computing High-performance computing Multiprocessing Manycore processor GPGPU Computer network Systolic array
Levels	Bit Instruction Thread Task Data Memory Loop Pipeline
Multithreading	Temporal Simultaneous (SMT) Simultaneous and heterogenous Speculative (SpMT) Preemptive Cooperative Clustered multi-thread (CMT) Hardware scout
Theory	PRAM model PEM model Analysis of parallel algorithms Amdahl's law Gustafson's law Cost efficiency Karp–Flatt metric Slowdown Speedup
Elements	Process Thread Fiber Instruction window Array
Coordination	Multiprocessing Memory coherence Cache coherence Cache invalidation Barrier Synchronization Application checkpointing
Programming	Stream processing Dataflow programming Models Implicit parallelism Explicit parallelism Concurrency Non-blocking algorithm
Hardware	Flynn's taxonomy SISD SIMD Array processing (SIMT) Pipelined processing Associative processing MISD MIMD Dataflow architecture Pipelined processor Superscalar processor Vector processor Multiprocessor symmetric asymmetric Memory shared distributed distributed shared UMA NUMA COMA Massively parallel computer Computer cluster Beowulf cluster Grid computer Hardware acceleration
APIs	Ateji PX Boost Chapel HPX Charm++ Cilk Coarray Fortran CUDA Dryad C++ AMP Global Arrays GPUOpen MPI OpenMP OpenCL OpenHMPP OpenACC Parallel Extensions PVM pthreads RaftLib ROCm UPC TBB ZPL
Problems	Automatic parallelization Deadlock Deterministic algorithm Embarrassingly parallel Parallel slowdown Race condition Software lockout Scalability Starvation
Category: Parallel computing