Legea lui Gustafson

John L. Gustafson a aratat in 1988 ceea ce este acum cunoscut sub numele de Legea lui Gustafson: oamenii de obicei nu sunt interesați de rezolvarea unei probleme fixe în cel mai scurt interval de timp, cum descrie Legea lui Amdahl, ci mai degrabă în rezolvarea problemei cele mai mari într-un timp rezonabil. În cazul în care partea non-parallelizabila a remediat problema, sau creste foarte incet cu dimensiunea problemei, atunci procesoare suplimentare pot crește dimensiunea problemei fără limită.

Legea lui Gustafson

Prin paralelizarea unui program secvențial se urmărește în primul rând obținerea unui timp de execuție cât mai mic comparativ cu timpul secvențial de execuție. Cel mai important criteriu luat în considerare atunci când se dorește evaluarea performanțelor unui program paralel este accelerarea paralelă sau creșterea de viteză (speedup) care exprimă de câte ori programul paralelește mai rapid față de varianta secvențială. Accelerarea paralelă se calculează ca raport între timpul secvențial de execuție și timpul de execuție paralelă. Valoarea maximă a accelerării paralele este egală cu numărul de procesoare din sistem. O astfel de valoare poate fi atinsă într-un sistem ideal în care nu există costuri de comunicare iar procesoarele sunt încărcate echilibrat. Dacă un algoritm paralel ar putea să fie scalat continuu, atunci de fiecare dată când dublăm numărul de procesoare, viteza de calcul ar trebui să se dubleze. Dar algoritmii paraleli prezintă o accelerare liniară pentru un număr mic de procesoare și apoi creșterea vitezei se saturează.

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)=1-P(1-\delta ).

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

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 că suma totală a lucrurilor de făcut în paralel " variază liniar cu numărul totol de procesoare". Apoi, implicarea practică este a unui singur procesor care este mult mai capabil decât asignarea singurei procesări pentru a fi executată în paralel cu alte asignări. Aceasta implică că b, timpul de procesare paralelă, ar trebui fixat ca P. Timpul corespunzător în scopul prelucrării secvențiale este

a+P\cdot b.

Viteza este:

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

Definitia:

\alpha =a/(a+b)

să fie fracțiunea secvențială a timpului de execuție paralelă

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

Dacă $\alpha$ este mic, atunci viteza este aproximativ P, după cum se dorește. De asemenea, poate să fie cazul ca $\alpha$ să diminueze pe măsură ce P crește; dacă acest lucru este adevărat, atunci S se apropie de P cu o creștere a lui P.

Astfel Legea lui Gustafson salvează procesarea paralelă din Legea lui Amdahl. Ea se bazează pe ideea că, dacă dimensiunea problemei crește cu P, atunci fracțiunea secvențială a volumului de muncă nu ar veni să domine. Acest lucru este permis căci cele mai multe sarcini individual controlabile în scopul prelucrării unui singur procesor. Astfel un singur procesor poate prevedea sarcini multiple, în timp ce o singură atribuire nu ar cuprinde mai mult de un singur procesor. Aceasta este, de asemenea, regula pentru proiectele cu privire la work-sites, având mai multe proiecte pe site, dar un singur proiect per site.

Vezi și

Bibliografie

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.6348
Computer Architecture, A Quantitative Approach, 3rd edition, J.L. Hennessy and D.A. Patterson