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

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

Амдалов закон, исто така познат како Амдалов аргумент,^[1] се користи за да се најде максималното подобрување на севкупниот систем кога само дел од системот е подобрен . Често се користи во паралелното сметање за да се предвиди теоретскиот максимум и забрзување со користење на повеќе обработувачи. Законот е именуван по компјутерски архитект 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 , само во посебни случаи на имплементација на Амдалов закон. Ако еден избор оптимално ( во случаи на остварено забрзување) кое се подобрува, тогаш ќе се види монотоно опаѓање на подобрувањето. Ако , во секој случај, еден избор на не-оптималност, после подобрувањето на под-оптималната компонента и поместувањето до зголемување на повеќе оптимални компоненти, тогаш ќе се види зголемувањето како резултат. Да забележиме дека често е рационално да се подобри системот кој е не-оптимален во оваа смисла, со оглед на тоа дека некои подобрувања потешко се прифаќаат во времето на развој за разлика од другите.