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

Амдалов закон, још познат као и Амдалов аргумент, се користи да се пронађе максимално очекивано побољшање свеукупног система, када се побољша само један део система. Често се користи у паралелној обради да би се предвидео теоретски максимално убрзање при коришћењу више процесора. Закон је добио име по рачунарском архитекти Џи̑ну Амдалу (Gene Amdahl). Закон је представљен у америчкој федерацији друштва за обрађивање података (енгл. American Federation of Information Processing Societies, AFIPS) на „Spring Joint“ рачунарској конференцији 1967.

Убрзање програма, који користи више процесора у паралелној обради, је ограничено секвенцијалним разломком програма. На пример, ако 95% програма може бити паралелизовано, теоретски максимално убрзање, коришћењем паралелне обраде, би било 20 пута веће него на дијаграму, без обзира на то колико се процесора користи.

Убрзање програма, који користи више процесора у паралелном окружењу, је ограничен временом које је потребно да се обради секвенцијални део програма. На пример, ако је програму потребно 20 сати коришћења једног језгра, и ако се одређени део програма (коме треба сат времена да се изврши) не може паралелизовати, док се осталих 95% (19 сати) може паралелизовати, онда, без обзира на то колико је процесора посвећено паралелном извршавању програма, минимално време извршавање не може бити мање од једног сата. Одатле је убрзање ограничено на највише 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)$

Дакле, теоретско убрзање које се може добити извршавањем алгоритма на систему који је способан да изврши $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) плус дужине дела колико треба побољшаном делу да се изврши. Време које је потребно да се изврши побољшани део једнак је претходној дужини времена извршавања овог дела, подељеног убрзањем. Тиме добијамо дужину времена побољшаног дела P/S. Коначно убрзање се рачуна дељењем старог времена извршавања, новим временом извршавања, које се израчунава формулом горе.

Још један пример овога: дат нам је секвенцијалан задатак који се дели на четири узастопна дела: P1, P2, P3 и P4 који се извршавају, процентуално, 11%, 18%, 23% и 48%, редом. Онда нам је речено да P1 не убрзава (тако да је S1 = 1) док P2 убрзава 5 пута, P3 убрзава 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%) убрзава само 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 (такозвани неометано паралелни проблеми). Велики део вештине паралелног програмирања се састоји од покушаја да се смањи компонента 1 – P на што мању вредност.

P се може проценити коришћењем измереног убрзања (SU) на одређеном броју процесора (NP) коришћењем:

$P_{\text{процењено}}={\frac {{\frac {1}{SU}}-1}{{\frac {1}{NP}}-1}}$.

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

Веза са законом опадајућих повратних вредности

Амдалов закон се често спаја са законом опадајућих повратних вредности, с обзиром само на специјалан случај када применом Амдаловог закона, демонстрирамо закон опадајућих повратних вредности. Ако се оптимално изабере шта жели да се побољша (у смислу остваривања убрзања), онда се могу видети монотона опадања неких побољшања док се нека друга још више побољшавају. Међутим, ако се избор изврши неоптимално, после побољшања мање оптималних компоненти и прелажења на побољшање више оптималних компоненти, могу се видети повећања побољшања. Често је рационално побољшати систем у редоследу који није оптималан зато што је нека побољшања теже достићи или зато што захтевају више времена.

Амдалов закон представља закон опадајућих повратних вредности ако се узима у обзир која сорта повратних вредности се добија додавањем више процесора некој машини ако се покреће рачунање фиксне величине које ће искористити све доступне процесоре до максимума. Сваки нови процесор који се дода систему ће додати мање снаге према граници $\scriptstyle 1/(1\,-\,P)$.

Ова анализа занемарује друге потенцијалне случајеве где се јављају уска грла (као што су пропусни опсег меморије и пропусни опсег улаза/излаза) ако се не скалира са бројем процесора. Међутим, узимајући у обрзир ове случајеве уских грла би тежило да, још детаљније, демонстрира, опадајуће повратне вредности додавањем само процесора.

Убрзање у секвенцијалном програму

Претпоставимо да задатак има 2 независна дела, делове А и B. B делу треба отприлике 25% времена целокупног рачунања. Радећи напорно, неко може учинити овај део 5 пута бржим, али би то само смањило време извршавања целог рачунања за мало. Супротно, тај неко може уложити мање напора и учинити А део дупло бржим. То ће учинити рачунање много бржим него оптимизовање B дела, чак иако је брзина B дела већа (5 пута у односу на 2 пута).

Максимално убрзање у побољшаном секвенцијалном програму, где је неки део убрзан $p$ пута је ограничено неједнакошћу:

${\text{максимално убрзање}}\leq {\frac {p}{1+f\cdot (p-1)}}$

где је $\scriptstyle f$ ($\scriptstyle 0\;<\;f\;<\;1$) део времена (пре побољшања) потрошено у делу које није побољшано. На пример (видети слику десно:)

• Ако учинимо део B пет пута бржим ($\scriptstyle p\;=\;5$), $\scriptstyle t_{A}\;=\;3$, $\scriptstyle t_{B}\;=\;1$, и $\scriptstyle f\;=\;t_{A}/(t_{A}\,+\,t_{B})\;=\;0,75$, онда

  ${\text{максимално убрзање}}\leq {\frac {5}{1+0,75\cdot (5-1)}}=1,25$

• Ако учинимо део А два пута бржим ($\scriptstyle p\;=\;2$), $\scriptstyle t_{B}\;=\;1$, $\scriptstyle t_{A}\;=\;3$, и $\scriptstyle f\;=\;t_{B}/(t_{A}\,+\,t_{B})\;=\;0,25$, онда

  ${\text{максимално убрзање}}\leq {\frac {2}{1+0,25\cdot (2-1)}}=1,60$

Стога, дупло бржи А део је бољи случај него пет пута бржи B део. Проценат побољшања у брзини се рачуна:

${\text{проценат побољшања}}=\left(1-{\frac {1}{\text{фактор убрзања}}}\right)\cdot 100$

• Побољшањем дела А дупло, добија се повећање укупне брзине програма за 1,6 пута, што значи да је програм бржи за 37,5%.
• Међутим, побољшањем дела B пет пута, што захтева и више напора, ће резултовати да укупан програм буде само 20% бржи.

Однос са Густафсоновим законом

Џон Л. Густафсон је 1988. године истакао Густафсонов закон: људи обично нису заинтересовани за решавање фиксних проблема у најкраћем временском року (као што описује Амдалов закон), већ ће радије решавати комплексније проблеме (тј. најпрецизнију могућу апроксимацију) у фиксном „разумном“ временском периоду. Ако се не-паралелизовани део проблема поправи, или ако расте јако споро са величином проблема (тј. O(log n)), онда додатни процесори могу повећати величину могућег проблема без икаквих ограничења.

Види још

• Муров закон
• Густафсонов закон

Референце

• Amdahl, Gene (1967). „Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities” (PDF). AFIPS Conference Proceedings (30): 483—485. 
• Rodgers, David P. (1985). „Improvements in multiprocessor system design”. ACM SIGARCH Computer Architecture News archive. New York, NY, USA: ACM. 13 (3): 225—231. ISSN 0163-5964. doi:10.1145/327070.327215. 

Спољашње везе

• Cases where Amdahl's law is inapplicable
• Oral history interview with Gene M. Amdahl Charles Babbage Institute, University of Minnesota. Амдал дискутује свој дипломски рад и свој WISC дизајн на универзитету у Висконсину. Дискутује своју улогу у дизајнирању неколико рачунара за IBM укључујући STRETCH, IBM 701, и IBM 704. Дискутује свој рад са Натанијелом Рохестером и IBM-овим менаџментом процеса дизајнирања. Помиње рад са Ramo-Wooldridge, Aeronutronic, и Computer Sciences Corporation
• Reevaluating Amdahl's Law
• 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
• Amdahl's Law explanation
• Blog Post: "What the $#@! is Parallelism, Anyhow?"
• Amdahl's Law applied to OS system calls on multicore CPU