Амдалов закон

Забрзувањето на програма со користење на повеќе обработувачи во паралелното извршување е ограничено со серискиот дел од програмата. Пример, ако 95% од програмата може да биде паралелизирана, теоретски може да добиеме максимално забрзување од 20 пати.

Амдалов закон, исто така познат како Амдалов аргумент, се користи за да се најде максималното подобрување на севкупниот систем кога само дел од системот е подобрен . Често се користи во паралелното сметање за да се предвиди теоретскиот максимум и забрзување со користење на повеќе обработувачи. Законот е именуван по компјутерски архитект Gene Amdahl, и беше претставен на AFIPS пролетната заедничка компјутерска конференција во 1967 година.

Забрзувањето на една програма со помош на повеќе обработувачи во паралелните компјутери е ограничен со времето потребно за секвенциалниот дел на работното време. На пример, ако на некоја програма и треба 20 часа користење на едно-јадрен процесор, а одреден дел од програмата која трае еден час да се изврши не може да се паралелизира, додека останатите 19 часа (95%) на времето за исполнување може да се парализирани, тогаш без оглед колку обработувачи се посветени на паралелно извршување на оваа програма, минималното време на извршувањето не може да биде помала од онаа критична еден час. Оттука, теоретски и забрзувањето е ограничено на најмногу 20×.

Дефиниција

Дадено:

• $n\in \mathbb {N}$, број на нитки за извршување,
• $B\in [0,1]$, дел од алгоритмот кој е строго сериски,

Времето $T\left(n\right)$ алгоритам кој се нитка за да се заврши $n$ задача(и) на извршување кои одговараат на :

$T(n)=T(1)\left(B+{\frac {1}{n}}\left(1-B\right)\right)$

Затоа, теоретското забрзување $S(n)$ кое може да извршува даден алгоритам на систем којшто е способен да извршува $n$ нитки за извршување е :

$S(n)={\frac {T\left(1\right)}{T\left(n\right)}}={\frac {T\left(1\right)}{T\left(1\right)\left(B+{\frac {1}{n}}\left(1-B\right)\right)}}={\frac {1}{B+{\frac {1}{n}}\left(1-B\right)}}$

Опис

Амдаловиот закон е модел за очекуваното забрзување и односот помеѓу паралелизираната имплементација на алгоритмот и неговата секвенцна имплементација, под претпоставка дека големината на проблемот останува иста кога се паралелизира. На пример, ако за дадена големина на проблем паралелизираната имплементација на алгоритмот може да работи 12% од операциите на алгоритмот произволно брзо (додека останатите 88% од активностите не можат да се паралелизират), Амдаловиот закон се држи на тоа дека максималното забрзување на паралелизираната верзија е 1/(1 – 0.12) = 1.136 пати побрза од не-паралелизираната имплементација.

Технички , законот е конкретизиран со остварувањето на забрзувањето од подобрување до пресметки кои влијаат на процентот P од таа пресметка каде подобрувањето има забрзување S. ((На пример, ако 30% од пресметките може да биде предмет на забрзување, P ќе биде 0.3; ако подобрувањето зазема место кое влијае двапати побрзоS ќе биде 2.) Амдаловиот закон конкретизира дека целокупното забрзување ќе биде:

${\frac {1}{(1-P)+{\frac {P}{S}}}}={\frac {1}{(1-0.3)+{\frac {0.3}{2}}}}=1.1765$

За да видиме како оваа формула е изведена, времето на извршување на старата пресметка беше 1,за некоја единица време. Времето на извршување на нова пресметка ќе биде должината на времето за која неподобрениот дел зазема дел ( која е 1 − P), плус должината на времето за подобрениот дел. Конечното забрзување е пресметано како делење на старото со новото време, за кое и формулата важи. Пример:

Дадена ни е секвенцна задача која е поделена на 4 дела: P1,P2,P3 и P4 со процент на времетрање соодветно 11%,18%,23% и 48%. Тогаш кажано ни е дека P1 не е забрзан, па S1=1, додека забрзувањето за P2 e 5 пати, за P3 e 20 пати, и за P4 забрзувањето е 1,6 пати. Со користење на формулата P1/S1 + P2/S2 + P3/S3 + P4/S4 го наоѓаме новото време на извршиување:

${\frac {0.11}{1}}+{\frac {0.18}{5}}+{\frac {0.23}{20}}+{\frac {0.48}{1.6}}=0.4575.$

или малку помалку од  ¹⁄₂ од оригиналното време на извршување. Користејки ја оваа формула (P1/S1 + P2/S2 + P3/S3 + P4/S4)⁻¹}},целокупното забрзување е 1 / 0.4575 = 2.186, или малку повеќе од двојното оригинално забрзување. Да забележиме дека забрзувањето од 20 и 5 пати нема голем ефект на целокупното забрзување кога P1(11%) не е забрзан, и P4(48%) e забрзан само 1.6 пати.

Паралелизација

Во овој случај на паралелизација, Амдаловиот закон вели дека ако P е процентот од програмата која може да биде паралелизирана (односно, има корист од паралелизацијата), и (1 − P) е процентот кој не може да биде паралелизиран (останува сериски), тогаш максималното забрзување кое може да се оствари со користење на N обработувачи е:

$S(N)={\frac {1}{(1-P)+{\frac {P}{N}}}}$.

Ограничено, како N настојува кој бесконечност, максималното забрзување настојува кој 1 / (1 − P). Во пракса, цената на соодносот на перформансите паѓа брзо откако N се зголеми тогаш е дури мал дел од (1 − P).

Како пример , ако P е 90%, тогаш (1 − P) е 10%, и проблемот може да биде забрзан од максимум фактор 10, без разлика колку голема вредност се користи за N . Поради оваа причина, паралелното пресметување е единствено корисно за мал број на обработувачи, или проблеми со многу големи вредност за P: исто така наречени иеmbarrassingly parallel проблеми. Голем дел од вештините на паралелното програмирање се состои од обидот да се намали компонентата (1 – P) на најмала можна вредност.

P може да се процени со користење на мерливо забрзување (SU)на определен број на обработувачи (NP) користејки

$P_{\text{estimated}}={\frac {{\frac {1}{SU}}-1}{{\frac {1}{NP}}-1}}$.

P проценувајки на овој начин може да биде искористен во Амдаловиот закон за да предвиди забрзување на различен број на обработувачи.

Однос на намалувањето како резултат кај законот

Амдаловиот закон често е поврзуван со т.н law of diminishing returns , само во посебни случаи на имплементација на Амдалов закон. Ако еден избор оптимално ( во случаи на остварено забрзување) кое се подобрува, тогаш ќе се види монотоно опаѓање на подобрувањето. Ако , во секој случај, еден избор на не-оптималност, после подобрувањето на под-оптималната компонента и поместувањето до зголемување на повеќе оптимални компоненти, тогаш ќе се види зголемувањето како резултат. Да забележиме дека често е рационално да се подобри системот кој е не-оптимален во оваа смисла, со оглед на тоа дека некои подобрувања потешко се прифаќаат во времето на развој за разлика од другите.

Поврзано

• Critical path method
• Karp–Flatt metric
• Moore's law

Наводи

• Rodgers, David P. (June 1985). „Improvements in multiprocessor system design“. ACM SIGARCH Computer Architecture News archive. New York, NY, USA: ACM. 13 (3): 225–231. doi:10.1145/327070.327215. ISBN 0-8186-0634-7. ISSN 0163-5964.

Further reading

• Amdahl, Gene M. (1967). „Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities“ (PDF). AFIPS Conference Proceedings (30): 483–485. doi:10.1145/1465482.1465560.

Надворешни врски

• Cases where Amdahl's law is inapplicable Архивирано на 14 април 2013 г.
• Oral history interview with Gene M. Amdahl Charles Babbage Institute, University of Minnesota. Amdahl discusses his graduate work at the University of Wisconsin and his design of WISC. Discusses his role in the design of several computers for IBM including the STRETCH, IBM 701, and IBM 704. He discusses his work with Nathaniel Rochester and IBM's management of the design process. Mentions work with Ramo-Wooldridge, Aeronutronic, and Computer Sciences Corporation
• A simple interactive Amdahl's Law calculator
• "Amdahl's Law" by Joel F. Klein, Wolfram Demonstrations Project, 2007.
• Amdahl's Law in the Multicore Era
• Blog Post: "What the $#@! is Parallelism, Anyhow?" Архивирано на 9 септември 2008 г.
• Amdahl's Law applied to OS system calls on multicore CPU Архивирано на 22 јуни 2010 г.
• Evaluation of the Intel Core i7 Turbo Boost feature Архивирано на 4 март 2016 г., by James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat and Alexandra Fedorova
• Calculation of the acceleration of parallel programs as a function of the number of threads, by George Popov, Valeri Mladenov and Nikos Mastorakis