Legea lui Amdahl si Gustafson

Legea lui Amdahl

Prin paralelizarea unui program secvential se urmareste in primul rand obtinerea unui timpde 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 este accelerarea 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.

Prin urmare, potentialul accelerarii unui algortim paralel pe o platforma de calcul este dat de legea lui Amdahl, care a fost formulata initial de catre Gene Amdahl, inginer american, cunoscut datorită muncii sale in cadrul IBM. Acesta a definit limitarile fundamentale ale programarii paralele, propunand o evaluare a perfomantelor masinilor de calcul, in special in cazul utilizarii de procesoare multiple. Ceea ce inseamna ca o parte dintr-un program, care nu poate fi paralelizata, limiteaza drastic acceleratia globala care poate fi obtinuta din restul programului. Legea lui Amdahl paralelizata, limiteaza drastic scalabilitatea unui program paralel.

Acceleratia S pentru un sistem cu N procesoare este, prin definitie:

$S={\frac {T_{S}}{T_{N}}}$

unde

   TS este timpul de execuție pentru cel mai rapid algoritm secvențial care rezolvă problema pe un monoprocesor 
   TN este timpul de execuție al algoritmului paralel executat pe un sistem multiprocesor, cu N microprocesoare.

Daca notam cu f fractia (procentajul) din algoritm care are un caracter secvential, f [0,1], putem scrie:

         TN=f∙TS+((1-f)∙TS)/N

adica

         S=TS/(f∙TS+((1-f)∙TS)/N)

sau

         S=1/(f+(1-f)/N)

Legea lui G. Amdahl, 1≤S≤ N

Factorul de accelerare ne va spune de cate ori va rula mai repede masina de calcul dupa îmbunatatirea făcuta fata de inainte. Legea lui Amdahl ne ofera o modalitate rapida pentru aflarea factorului de accelerare pentru anumite îmbunatatiri functie de doi factori:

• fractiunea din timpul de calcul a masinii initiale care poate fi convertita pentru a putea profita de îmbunatatirea făcuta; aceasta fractiune este cel mult egala cu întregul timp de calcul
• imbunatatirea (performanta) castigata prin modul de executie îmbunatatit; reprezinta raportul dintre noul timp de executie (pentru portiunea din task care beneficiaza de îmbunatatirea făcuta) si timpul vechi de executie

Exemplu: daca 80% din program poate fi paralelizat, fractiunea care nu poate fi paralelizata va fi de 0.2. In concluzie, accelerarea maxima este de 1/0.2=5, indiferent de numarul de procesoare folosit.

În conformitate cu legea lui Amdahl, chiar si într-un sistem paralel ideal este foarte dificil de obtinut o accelerare paralela egala cu numarul de procesoare datorita faptului ca în cadrul oricarui program exista o fractie care nu poate fi paralelizata si care trebuie executata secvential. Restul de(1 - f) pasi de calcul se pot executa in paralel pe procesoarele disponibile in sistem.

Din acest motiv, accelerarea maxima care se poate obtine atunci cand o fractie f a programului nu poate fi paralelizata este indiferent de numarul de procesoare din sistem. Legea lui Amdahl exprima in mod clar necesitatea minimizarii fractiei f ce nu poate fi paralelizata prin stabilirea unei limite superioare a accelerarii paralele. Deoarece un sistem de calcul paralel cu n procesoare nu atinge o viteza de calcul de n ori mai mare decât fiecare procesor în parte, sistemul de calcul paralel, pentru a fi acceptat pe piata, trebuie macar sa fie convenabil la pret.

Pe de alta parte, calculul paralel se foloseste la probleme care necesita foarte multe calcule, dar numai daca acestea pot fi impartite în subprobleme independente, mai simple, care pot profita de paralelism.

Corolar la Legea lui Amdahl

Daca imbunatatirea este utilizata doar pentru o fractiune din task nu se poate accelera acel task mai mult de 1 / 1 – acea fractiune. Lege lui Amdahl poate servi pentru a vedea cu cat se imbunatateste performanta unui sistem de calcul si modul in care se pot distribui resursele pentru a imbunatati raportul cost/performanta.

Exemplu

Implementarea hardware a unei functii pentru extragerea radacinii patrate in virgula mobila duce la variatia semnificativa a performantelor. Presupunem ca aceasta unitate este responsabila pe 20 % din timpul de executie a unui program de test pentru o anume mașina. Alternativele ar fi implementarea hardware a unitatii de extragere a radacinii in virgula mobila, lucru ce ar accelera aceasta operatie de 10x, sau implementarea hardware a unei unitati ce va accelera de 2x toate operatiile in virgula mobila. Operatiile in virgula mobila reprezinta 50 % din timpul de rulare.

Relația cu legea retururilor diminuate

Legea lui Amdahl este de foarte multe ori asociată cu legea retururilor diminuate, dar numai un caz special al aplicării legii lui Amdahl o demonstrează. Dacă se alege componenta optimală pentru îmbunătățire(în termeni de accelerare obținută), atunci se va observa că în timp ce această componentă va fi îmbunătățită, altor componente le va scădea îmbunătățirea proporțional. Dacă însă se vor alege componente neoptimale pentru îmbunătățire, se pot observa creșteri de îmbunătățire. Astfel, este de multe ori practic ca un sistem să fie îmbunătățit într-o ordine neoptimală, mai ales datorită faptului că unele îmbunătățiri sunt mai grele sau consumatoare de timp și resurse decât altele.

Legea retururilor diminuate se regăsește în cazul legii lui Amdahl dacă se ia în considerare tipul rezultatului în cazul adaugării unui procesor la mașină; dacă se rulează un sistem care va folosi toate procesoarele la capacitățile maxime. Fiecare nou procesor adăugat în sistem va adăuga mai puțină putere decât cel dinainte. De fiecare dată când se dublează numarul de procesoare, rația de accelerare a sistemului va scădea, rezultatul tinzând către o limită de Analiza nu ia în calcul apariția potențialelor gâtuiri(restricții) ale sistemului, cum ar fi banda de frecvență a memoriei sau a I/O; adar dacă acestea ar fi luate în calcul, adăugarea de procesoare pentru paralelizare ar avea și mai multe diminuări.

Concluzie

Legea lui Amdahl ne ofera o perspectiva asupra performantelor castigate prin imbunatatirea unei portiuni dintr-o masina de calcul. Legea lui Amdahl si legea lui Gustafson sunt de fapt puncte de vedere diferite asupra aceluiasi adevar: una considera datele ca fiind de dimensiune fixa si prin urmare cantitatea de lucru de facut in paralel nu depinde de numarul de procesoare si cealalta lege considera problema ca fiind de dimensiune crescatoare si deci cantitatea totala de lucru e proportionala cu numarul de procesoare

Vezi și

• Legea lui Gustafson
• Legea lui Amdahl
• Calcul paralel

Bibliografie

• http://www.csci.csusb.edu/schubert/tutorials/csci610/w06/TKleffelAmdahl06w.pdf Arhivat în 17 iunie 2010, la Wayback Machine.
• http://www-inst.eecs.berkeley.edu/~n252/paper/Amdahl.pdf

Legături externe

• Reevaluating Amdahl's law in the multicore era
• Modeling Critical Sections in Amdahl’s Law and its Implications for Multicore Design Arhivat în 9 august 2017, la Wayback Machine.