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

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

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

Убрзање програма, који користи више процесора у паралелном окружењу, је ограничен временом које је потребно да се обради секвенцијални део програма. На пример, ако је програму потребно 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 пута веће од алгоритма који није паралелно импплементиран.

Технички, закон се бави убрзањеm које се остварује од побољшања до израчунавања које утиче на размеру 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.

или мало мање од 12 тј. почетног времена извршавања. Коришћењем формуле (P1/S1 + P2/S2 + P3/S3 + P4/S4)−1, укупан добитак на убрзању је 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{estimated} = \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{maximum speedup } \le \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{maximum speedup } \le \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{maximum speedup } \le \frac{2}{1 + 0.25 \cdot (2 - 1)} = 1.60

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

\text{percentage improvement} = \left(1 - \frac{1}{\text{speedup factor}}\right) \cdot 100
  • Побољшањем дела А дупло, добијамо повећање укупне брзине програма за 1.6 пута више, што значи да је програм бржи за 37.5%.
  • Међутим, побољшањем дела B пет пута, што захтева и више напора, ће резултовати да укупан програм буде само 20% бржи.


Однос са Густафсоновим законом[уреди]

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

Такође погледати[уреди]

Белешке[уреди]

  1. ^ Rodgers 85, pp. 226

Референце[уреди]

Спољашње везе[уреди]