Estimări de accelerare. Legi ale lui Amdal și Gustavson - Barsis
Estimările anterioare au fost obținute pentru momentul soluționării problemei atunci când se utilizează procesoare p. Sa presupus că sarcina poate fi împărțită în module prin specificarea unui grafic de dependență, care determină ordinea posibilă de a apela modulele. Este interesant să luăm în considerare cazul când problema poate fi împărțită în două părți, dintre care una necesită o implementare succesivă, iar a doua poate fi paralelizată. Legile lui Amdahl și Gustavson-Barsis permit obținerea estimărilor pentru accelerare, în funcție de fracția de calcule consecutive în timpul total al soluționării problemei. Legile diferă numai în ceea ce privește determinarea procentului de calcule consecutive.
Legea lui Amdahl
Fie ca timpul de rezolvare a unei probleme de către un singur procesor să fie reprezentat ca sumă a momentelor de rezolvare a părții succesive și a părții care permite paralelizarea:
Împărțind ambele părți ale ecuației prin, să trecem la fracțiile de timp:
Timpul pentru rezolvarea problemei cu procesoarele p poate fi de asemenea reprezentat în două părți:
O fracție consecventă nu poate fi redusă prin creșterea numărului de procesoare. Pentru partea paralelă, există o estimare, astfel încât să fie respectată următoarea relație:
În ceea ce privește accelerarea, obținem:
Relația (30) este numită legea Amdahl. Se spune că accelerația este limitată de sus, de o cantitate care depinde de fracția de calcule succesive. Dacă, de exemplu, calculele secvențiale durează 10% din timpul total de calcul, atunci prin paralelizare nu puteți realiza mai mult de 10 ori accelerarea timpului de operare, câte procesoare nu ar fi implicate.
Natura pesimistă a legii lui Amdahl poate fi netezită prin reamintind că toate caracteristicile ar trebui considerate ca o funcție a n-parametrului care caracterizează cantitatea de date utilizate. În acest caz, legea lui Amdahl arată astfel:
În practică, adesea se întâmplă ca partea succesivă a problemei să fie constantă și să nu depindă de cantitatea de date. În acest caz, q (n) este o funcție descrescătoare, atunci pentru n mare este posibil să se obțină o accelerație bună fără a contrazice legea lui Amdahl.
Legea lui Gustavson-Barsis
Să scriem timpul optim de funcționare când folosim procesoare p sub forma unei sume de timp de două părți - paralel și secvențial:
Având în vedere faptul că partea serială este executată de către procesoarele p, atâta timp cât un procesor, iar timpul părții paralele în cazul optim poate fi redus cu un factor de p, obținem:
Împărțind ambele părți ale ecuației prin, să trecem la fracțiile de timp:
Acum, ia în considerare relația:
Două căi de paralelizare
Vorbind despre paralelizare, există două modalități principale de a efectua calcule paralele: paralelizarea prin sarcini și paralelizarea prin date.
Modelul considerat mai sus corespundea cazului de paralelizare prin sarcini. În acest model, diferite module ale aceluiași program ar putea fi executate în paralel.
Să analizăm acum o situație alternativă atunci când paralelizarea este efectuată pe date. În acest caz, un anumit set de date trebuie procesat de un singur modul.
Paralelizarea prin date
Să fie necesar să rezolvăm problema D pe un set finit de date. De multe ori, algoritm secvențial eficient poate obține o soluție la această problemă, în cazul în care este posibil să se reducă soluția problemei inițiale pentru rezolvarea subactivități k - în cazul în care fiecare sub-sarcină este soluția problemei inițiale, dar D. subsetul de date. Cea mai eficientă atunci când toate sub-sarcinile au aceeași dimensiune.
Un simplu, dar extrem de important în teoria algoritmilor
În cazul în care sarcina D (X) poate fi redusă la soluția acelorași sarcinile secundare dimensiune k si timpul liniar de a face sub k se poate obține soluția generală a problemei inițiale, complexitatea timpului de rezolvare a problemei inițiale T (n) este dată de:
Articole similare
Trimiteți-le prietenilor: