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

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

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

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

Дефиниција[уреди | уреди извор]

Дадено:

  • , број на нитки за извршување,
  • , дел од алгоритмот кој е строго сериски,

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

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

Опис[уреди | уреди извор]

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

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

За да видиме како оваа формула е изведена, времето на извршување на старата пресметка беше 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 го наоѓаме новото време на извршиување:

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

Паралелизација[уреди | уреди извор]

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

.

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

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

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

.

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

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

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


See also[уреди | уреди извор]

Notes[уреди | уреди извор]

  1. (Rodgers 1985, стр. 226)

References[уреди | уреди извор]

Further reading[уреди | уреди извор]

External links[уреди | уреди извор]