Crearea de versiuni paralele permite aplicațiilor să îmbunătățească în mod semnificativ viteza de procesare a datelor. Succesul paralelizării este de obicei determinat de accelerarea programului paralel în raport cu versiunea sa serioasă. În acest caz, este util să comparați rezultatul cu o limită superioară. Acest lucru se poate face cu legile Legii lui Amdahl și Legea lui Gustafson.
Datele de intrare
Un timp de rulare mai scurt vă permite să procesați seturi mari de date (de exemplu, mai multe înregistrări, pixeli sau utilizați modele fizice de o scară mai mare) într-o perioadă acceptabilă de timp. Unul dintre indicatorii de creștere a acestui tip de productivitate este accelerarea.
În general, accelerația este raportul dintre timpul secvențial și timpul de execuție paralelă a programului. De exemplu, dacă aplicația secvențială rulează în 6720 secunde și aplicația paralelă corespunzătoare în 126,7 secunde (folosind 64 fire și miezuri), accelerația este de 53x (6720 / 126,7 = 53,038).
Pentru modelele extrem de scalabile, accelerația ar trebui să crească aproape proporțional cu creșterea numărului de nuclee (fluxuri). Dacă accelerația măsurată nu crește proporțional, dar rămâne la același nivel sau începe să scadă, înseamnă că aplicația este redusă la scară redusă pe seturile de date utilizate. Dacă aceste seturi de date sunt tipice pentru această aplicație, atunci nu se va scala bine.
Închiderea în sensul indexului de accelerație este măsura de eficiență. Dacă accelerația arată cât de mult executarea paralelă este mai rapidă decât executarea secvențială, atunci eficiența arată cât de bine utilizează programul resursele de calcul ale sistemului. Pentru a calcula eficiența unei aplicații paralele, trebuie să luăm accelerația observată și să împărțim numărul de nuclee utilizate. Acest număr este exprimat ca procent. De exemplu, o accelerare de 53 de ori pe 64 de nuclee dă o eficiență de 82,8% (53/64 = 0,828). Aceasta înseamnă că, în medie, în procesul de execuție, fiecare nucleu este inactiv în jur de 17% din timp.
Înainte de începerea proiectului de paralelizare, dezvoltatorul ar putea fi interesat să evalueze accelerația pe care o poate atinge teoretic. În cazul în care procentul de cod de serie care pot fi executate în paralel, este cunoscută (sau estimate), atunci el poate folosi Legea Amdahl pentru a calcula limita superioară a accelerării aplicațiilor, fără a fi nevoie de pre-scris, orice cod concurente. În literatură există mai multe variante ale formulei legii Amdahl. In fiecare dintre ele a folosit procentul timpului (destinate) executării paralele (pctPar), execuție secvențială (1 - pctPar), iar numărul de fire / miezuri (p). Mai jos este o formulare simplă a legii Amdahl pentru calculul accelerației unei aplicații paralele pe nucleele p:
Această formulă reprezintă timpul de execuție secvențial, normalizat la 1 și împărțit la timpul estimat de execuție paralelă utilizând procentul timpului de execuție secvențial normalizat. timpul de execuție paralelă se calculează ca procent de execuție secvențială (1 - pctPar) și procentul de execuție în paralel, împărțit la numărul de nuclee folosite (pctPar / p). De exemplu, dacă 95% din timpul de execuție secvențială poate fi realizată în paralel pentru 8 nuclee, accelerația estimată, în conformitate cu legea lui Amdahl să fie de aproximativ 6x (1 / (0,05 + 0,95 / 8) = 5,925).
Pe lângă raportul mai mic sau egal cu (≤) din formula, formularea legii lui Amdahl implică faptul că calculele care pot fi efectuate în paralel vor fi împărțite într-un număr infinit de nuclee. Această presupunere elimină al doilea termen al numitorului, ceea ce înseamnă că cea mai mare accelerație posibilă este pur și simplu egală cu inversul executării secvențiale reziduale.
Legea lui Amdahl este adesea criticată pentru ignorarea costurilor de comunicare, sincronizare și alte acțiuni de gestionare a fluxului, precum și presupunerea unui număr infinit de procesatori. Pe lângă ignorarea costurilor inerente algoritmilor paraleli, una dintre cele mai puternice remarci este că, pe măsură ce numărul de nuclee crește, cantitatea de date prelucrate crește de obicei. Legea lui Amdahl implică utilizarea unui set fix de date pentru orice număr de nuclee și că procentajul timpului de execuție secvențial va rămâne același.
Dacă o aplicație paralelă poate utiliza opt nuclee pentru a procesa un set de date de opt ori mai mare decât cea precedentă, crește timpul de funcționare al părții secvențiale? Chiar dacă crește, cantitatea de date crește disproporționat. Practica reală arată că timpul de execuție consecutivă rămâne practic constant.
Legea lui Gustafson, cunoscută și sub denumirea de "accelerated". ia în considerare creșterea numărului de date proporțional cu creșterea numărului de nuclee și calculează (limita superioară) accelerarea aplicației, ca și cum o cantitate mai mare de date ar putea fi procesată secvențial. Formula de accelerare scalabilă arată astfel:
Ca și în formula legii Amdala, p înseamnă numărul de nuclee. Pentru a simplifica scrierea, s este procentul timpului de execuție secvențială din aplicația paralelă pentru dimensiunea specificată a setului de date. De exemplu, dacă 1% din timpul de execuție pe 32 nuclee este executat secvențial, atunci accelerarea executării unei astfel de aplicații pe același set de date în comparație cu executarea pe un singur nucleu cu un fir (se presupune că acest lucru este posibil) este egal cu:
Să vedem ce ne-ar da Legea lui Amdahl în astfel de ipoteze. Dacă procentul de execuție secvențială este egală cu 1%, prin Legea lui Amdahl - 1 / (0,01 + (0.99 / 32)) = 24.43x. Totuși, acesta este un rezultat fals, deoarece acest procentaj de timp consecutiv este estimat să funcționeze pe 32 nuclee. Din acest exemplu, nu este clar ce procentaj din execuția secvențială poate fi pentru un număr mai mare sau mai mic de nuclee. În cazul în care codul este perfect scalabil și volumul de date crește, respectiv, numărul de nuclee, acest procent poate rămâne același, și legea lui Amdahl ar prevedea accelerarea sarcinilor single-core (dimensiune fixă) la 32 de nuclee.
Pe de altă parte, în cazul în care timpul total de execuție în paralel este cunoscut pentru 32 de nuclee, în timp ce punerea în aplicare pe deplin de serie poate fi calculată, iar accelerarea acestei probleme o dimensiune fixă (ceea ce înseamnă că poate fi calculată pe același miez) poate fi determinată prin aplicarea legii Amdahl pentru 32 de nuclee. Presupunând că timpul total de rulare al aplicației paralele este de 1040 secunde pe 32 nuclee, atunci 1% din acest timp va fi consecvent, adică 10,4 secunde. Inmultind numarul de secunde (1029.6) miez executie paralela 32, se constată că valoarea totală a lucrărilor efectuate de aplicație, ocupă 1029.6 * 32 + 10,4 = 32957.6 secunde. Ora non-paralelă (10,4 secunde) este de 0,032% din timpul total de funcționare. Folosind acest rezultat, legea lui Amdahl ne dă o accelerație de 1 / (0.00032 + (0.99968 / 32)) = 31.686x.
În ceea ce privește Legea Gustafson necesar să se cunoască procentul de timp secvențial execuție paralelă, această formulă este de obicei utilizată pentru calcularea execuției paralele accelerare scalabile (creșterea volumului de date corespunzătoare numărului de nuclee) în raport cu succesiunea sarcinilor de aceeași mărime. Din exemplele de mai sus, rezultă că utilizarea strictă a datelor privind punerea în aplicare a programului în formula Legea Amdahl dă o evaluare mult mai pesimiste decât formula de accelerare scalabile.
recomandări
Când se calculează accelerația, trebuie să folosiți cel mai bun algoritm secvențial și cel mai rapid cod de serie pentru comparație. Se întâmplă adesea că este mai ușor să nu paralelizăm cel mai optim algoritm secvențial. Chiar și în aceste cazuri, este puțin probabil ca oricine va folosi orice cod secvențial dacă există versiuni mai rapide ale acestuia. Astfel, chiar dacă algoritmii utilizați sunt diferiți, pentru a calcula accelerația aplicației paralele corespunzătoare, este necesar să se utilizeze timpul de execuție cel mai rapid al celui mai rapid cod.
Când se specifică valoarea accelerației, trebuie utilizat factorul de multiplicare. Accelerația anterioară a fost exprimată în procente. În cazul nostru, utilizarea interesului poate duce la confuzie. De exemplu, dacă se spune că codul paralel este cu 200% mai rapid decât secvențial, înseamnă că funcționează pentru jumătate din timpul versiunii serial sau pentru o treime? Accelerarea în 105% va fi aproape egală cu munca consecutivă sau de două ori mai rapidă? Timpul secvențial de bază este o accelerație de 0% sau 100%? Pe de altă parte, dacă aplicația paralelă are o accelerație de 2x, atunci este clar că jumătate din timp a mers la lucru (și anume că versiunea paralelă a reușit să ruleze de două ori în timpul în care codul secvențial funcționează odată).
În cazuri foarte rare, accelerația aplicației depășește numărul de nuclee. Acest fenomen este cunoscut sub numele de accelerare superlineară. Motivul standard pentru apariția accelerației superline este că atunci când descompunerea blocurilor de date devine suficient de mică pentru a se încadra în întregime în memoria cache a nucleului local. În operația secvențială, datele trebuiau să treacă constant prin cache, iar procesorul a trebuit să aștepte ca datele cache să apară. Dacă cantitatea de date a fost suficient de mare pentru a înlocui liniile cache anterioare, atunci orice utilizare ulterioară a acestor linii de cache obligă procesorul să aștepte ca acestea să apară din nou. Dacă datele sunt rupte în blocuri care sunt complet plasate în memoria cache a nucleului, atunci după ce așteptați toate liniile de cache, timpul de așteptare nu mai este petrecut. Astfel, utilizarea mai multor nuclee poate elimina o parte din costurile asociate execuției secvențiale pe un singur nucleu. Seturile prea mici de date care sunt mai mici decât dimensiunea standard pot da un sentiment fals de îmbunătățire a performanței.
Instrucțiuni de utilizare
Au fost propuse modele alternative de executare paralelă care clarifică într-o anumită măsură contradicțiile prezente în modelul simplu al legii lui Amdahl.
Cu toate acestea, datorită simplității și înțelegerii faptului că aceasta este limita superioară teoretică, care este cel mai probabil imposibil de realizat sau de depășit, legea lui Amdahl este un indicator simplu și valoros al potențialului de accelerare într-o aplicație consecventă.