Закон Амдала

Теоретическое ускорение задержки (через сокращение задержки, т.е. задержка в качестве метрики истекает время между входом и выводом в системе) выполнения программы как функция числа процессоров, выполняющих ее, в соответствии с Закон Амдала. Ускорение ограничено последовательной частью программы. Например, если 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 _{задержка} - это теоретическое ускорение выполнения всей задачи;
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 , и 4 -я часть ускоряется в 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 раза).

Например, с серийной программой в двух частях A и B, для которых t _a = 3 s и t _b = 1 s ,

Если часть 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).

Улучшение части A в 2 раза увеличит общую скорость программы в 1,60, что делает ее на 37,5% быстрее, чем исходное вычисление.
Тем не менее, улучшение части B в 5 в 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 Computer Architecture News . 13 (3). Нью -Йорк, Нью -Йорк, США: ACM : 225–231 [с. 226]. doi : 10.1145/327070.327215 . ISBN 0-8186-0634-7 Полем ISSN 0163-5964 . S2CID 7083878 .
^ Редди, Мартин (2011). API -дизайн для C ++ . Берлингтон, Массачусетс : издатели Морган Кауфманн . п. 210. doi : 10.1016/c2010-0-65832-9 . ISBN 978-0-12-385003-4 Полем LCCN 2010039601 . OCLC 666246330 .
^ Брайант, Рэндал Э .; Дэвид, О'Халларон (2016), Компьютерные системы: перспектива программиста (3 изд.), Pearson Education, p. 58, ISBN 978-1-488-67207-1
^ МакКул, Майкл; Реиндерс, Джеймс; Робисон, Арч (2013). Структурное параллельное программирование: шаблоны для эффективных вычислений . Elsevier. п. 61. ISBN 978-0-12-415993-8 .
^ Хилл, Марк Д.; Марти, Майкл Р. (2008). «Закон Амдала в многокрасную эпоху». Компьютер 41 (7): 33–38. Citeseerx 10.1.1.221.8635 . doi : 10.1109/mc.2008.209 .
^ Рафиев, Ашур; Аль-Хаянни, Мухаммед Ан; Ся, Фэй; Шафик, Ришад; Романовский, Александр; Яковлев, Алекс (2018-07-01). «Модели ускорения и масштабирования мощности для гетерогенных много ядерных систем» . IEEE транзакции на многомасштабных вычислительных системах . 4 (3): 436–449. doi : 10.1109/tmscs.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) . АФИПС ТУЩЕСТВО (30): 483–485. doi : 10.1145/1465482.1465560 . S2CID 195607370 .

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

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

[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] Редди, Мартин (2011). API -дизайн для C ++ . Берлингтон, Массачусетс : издатели Морган Кауфманн . п. 210. doi : 10.1016/c2010-0-65832-9 . ISBN 978-0-12-385003-4 Полем LCCN 2010039601 . OCLC 666246330 .

[3] Брайант, Рэндал Э .; Дэвид, О'Халларон (2016), Компьютерные системы: перспектива программиста (3 изд.), Pearson Education, p. 58, ISBN 978-1-488-67207-1

[4] МакКул, Майкл; Реиндерс, Джеймс; Робисон, Арч (2013). Структурное параллельное программирование: шаблоны для эффективных вычислений . Elsevier. п. 61. ISBN 978-0-12-415993-8 .

[5] Хилл, Марк Д.; Марти, Майкл Р. (2008). «Закон Амдала в многокрасную эпоху». Компьютер 41 (7): 33–38. Citeseerx 10.1.1.221.8635 . doi : 10.1109/mc.2008.209 .

[6] Рафиев, Ашур; Аль-Хаянни, Мухаммед Ан; Ся, Фэй; Шафик, Ришад; Романовский, Александр; Яковлев, Алекс (2018-07-01). «Модели ускорения и масштабирования мощности для гетерогенных много ядерных систем» . IEEE транзакции на многомасштабных вычислительных системах . 4 (3): 436–449. doi : 10.1109/tmscs.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