Legea lui Gustafson

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

Legea lui Gustafson[modificare | modificare sursă]

Prin paralelizarea unui program secvențial se urmareste in primul rand obtinerea unui timp de executie cat mai mic comparativ cu timpul secvential de executie. Cel mai important criteriu luat in considerare atunci cand se doreste evaluarea performantelor unui program paralel estea ccelerarea paralela sau cresterea de viteza (speedup) care exprima de cate ori programul paraleleste mai rapid fata de varianta secventiala. Accelerarea paralela se calculeaza ca raport intre timpul secvential de executie si timpul de executie paralela. Valoarea maxima a accelerarii paralele este egala cu numarul de procesoare din sistem. O astfel de valoare poate fi atinsa intr-un sistem ideal in care nu exista costuri de comunicare iarprocesoarele sunt incarcate echilibrat. Daca un algoritm paralel ar putea sa fie scalat continuu, atunci de fiecare data cand dublam numarul de procesoare, viteza de calcul ar trebui sa se dubleze. Dar algoritmii paraleli prezinta o accelerare liniara pentru un numar mic de procesoare si apoi cresterea vitezei se satureaza.

Legea lui Gustafson definește diferit creșterea vitezei (S) față de legea lui Amdahl. Gustafson susține că odată cu creșterea numărului de procesoare, accelerarea obținută prin paralelizare crește, căci paralelismul crește odată cu dimensiunea datelor. Creșterea vitezei va fi proporțională cu numărul de procesoare și cu (1 - α)

S(P)= \alpha + P\cdot(1-\alpha) = P - \alpha\cdot(P-1) .

unde

P este numărul de procesoare,
S este accelerația,
α este partea neparalelizabilă a programului.

Legea lui Amdahl presupune o dimensiune fixă a problemei și faptul că mărimea părții secvențiale este independentă de numărul de procesoare. Legea lui Gustafson nu face aceste ipoteze.

Derivare a Legii lui Gustafson[modificare | modificare sursă]

Timpul de executare al unui program este decompus în:

(a + b)

unde a este timpul secvential și b este timpul paralel, pentru orice procesor P.


Ipoteza lui Gustafson și Barsis este ca suma totala a lucrurilor de facut in paralel " variaza liniar cu numarul totol de procesoare". Apoi, implicarea practica este a unui singur procesor care este mult mai capabil decat asignarea singurei procesari pentru a fi executata in paralel cu alte asignari. Aceasta implica ca b, timpul de procesare paralela, ar trebui fixat ca P. Timpul corespunzator in scopul prelucrarii secventiale este

a + P\cdot b .

Viteza este:

(a + P\cdot b)/(a+b) .

Definitia:

\alpha = a/(a+b)

sa fie fractiunea secventiala a timpului de executie paralela

S(P)= \alpha + P\cdot(1-\alpha) = P - \alpha\cdot(P-1) .

Daca \alpha este mic, atunci viteza este aproximativ P, dupa cum se doreste. De asemenea, poate sa fie cazul ca \alpha sa diminueze pe masura ce P creste; daca acest lucru este adevarat, atunci S se apropie de P cu o crestere a lui P.


Astfel Legea lui Gustafson salveaza procesarea paralela din Legea lui Amdahl. Ea se bazeaza pe ideea ca, daca dimensiunea problemei creste cu P, atunci fractiunea secventiala a volumului de munca nu ar veni sa domine. Acest lucru este permis caci cele mai multe sarcini individual controlabile in scopul prelucrarii unui singur procesor. Astfel un singur procesor poate prevedea sarcini multiple, in timp ce o singura atribuire nu ar cuprinde mai mult de un singur procesor. Aceasta este, de asemenea, regula pentru proiectele cu privire la work-sites, avand mai multe proiecte pe site, dar un singur proiect per site.

Vezi și[modificare | modificare sursă]

Bibliografie[modificare | modificare sursă]