APD - Note Curs - 3 Complexitate

download APD - Note Curs - 3 Complexitate

of 26

Transcript of APD - Note Curs - 3 Complexitate

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    1/26

    42

    Capitolul 3 - Complexitatea algoritmilor paraleli i distribuii

    Orice proces de proiectare a unui algoritm urmrete obinerea unui rezultat corect i performant. n cazul algoritmilor paraleli i distribuii, performana nu poate ficaracterizat printr-o singur cifr. Ea depinde de categoria de aplicaii n care estefolosit algoritmul, de multe ori performana fiind o funcie de caracteristicile

    produsului program realizat (timp de execuie, memorie ocupat, numr de procesoareutilizate, scalabilitate, eficien, fiabilitate, toleran la defectri, portabilitate), daride costurile implicate de diferitele faze ale ciclului de via (proiectare, implementarei ntreinere). Ca n orice situaie n care exist mai multe alternative, i n cazulalgoritmilor paraleli alegerea trebuie fcut pe baza nelegerii costului diferitelorvariante. Estimarea costurilor reclam folosirea unor metrici i a unor modele de

    performan. Ele permit evaluarea comparativ a soluiilor, identificarea zonelor degtuire, eliminarea ineficienelor, nc nainte de a investi efort n implementarea lor.Deoarece i etapa de evaluare trebuie s fie eficient, modelele alese pentru afundamenta alegerea soluiei trebuie s fie un compromis ntre efortul de modelare iimportana mbuntirilor realizate prin consumarea lui.

    Recunoscnd importana tuturor factorilor de performan, descrierea care urmeaz selimiteaz la o parte a lor, concentrndu-se n special pe analiza timpului de execuie ia scalabilitii. Alegerea este determinat de faptul c, de cele mai multe ori, acesteareprezint aspectele cele mai problematice ale proiectrii aplicaiilor paralele idistribuite. n analizele concrete pe care un proiectant le face, evaluarea acestor

    performane trebuie realizat n codiiile nelegerii contextului dat de ceilali factori

    menionai mai sus.

    3.1. Sortarea pe un vector de procesoare

    Pentru a discuta msurile de performan asociate algoritmilor paraleli, pornim de laun exemplu simplu: sortarea unui ir de numere folosind un sistem vectorial (untablou unidimensional de procesoare), ca i cel prezentat n figura 3.1.

    Figura 3.1

    intrare

    ieire

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    2/26

    43

    3 0 5 1 2 iniial

    3 0 5 1 dup pasul 1

    3 0 5 dup pasul 2

    dup pasul 9

    2

    2

    53210

    Fiecare procesor interior este conectat prin legturi bidirecionale cu vecinii si, din

    dreapta i din stnga. Procesoarele extreme pot avea doar cte o legturi pot servica puncte de intrare/iesire pentru celelalte procesoare.

    Fiecare procesor are o memorie local i propriul su program. Sistemul are ofuncionare sincron: un ceas global comand execuia simultan a operaiilor de ctre

    procesoare. La fiecare pas, fiecare procesor realizeaz operaiile urmtoare: recepia unor date de la vecini; inspecia memoriei locale; execuia calculelor specificate de program; modificarea memoriei locale; transmiterea unor date ctre vecini.

    O astfel de funcionare se numete sistolic.

    Pentru a sorta o list de N numere, folosim un vector de N procesoare. Fiecareprocesor execut un algoritm compus din doua faze. In fiecare pas al primei faze,fiecare procesor realizeaz urmtoarele operaii:1) accept o valoare de la vecinul din stnga;2) compar valoarea cu cea memorata local;3) transmite valoarea mai mare vecinului din dreapta;4) memoreaz local valoarea mai mic.Un exemplu este ilustrat n figura 3.2.

    Figura 3.2

    Nu este greu de artat c dup 2N-1 pai, celulele conin elementele irului n ordinecresctoare. Astfel, prima celul examineaz N elemente din ir, reine valoarea cea

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    3/26

    44

    mai mic i transmite restul spre dreapta. A doua celul, examineaz restul de N-1

    valori, o reine pe urmtoarea mai mic i transmite restul celorlalte celule. Prininducie, rezult c celula N primete valoarea maxim a irului. Similar, deoarece ovaloare ajunge n prima celul dup un pas, n celula a doua dup trei pai .a.m.d.,rezult prin inducie c valoarea maxim ajunge n ultima celula dupa 2N-1 pai.

    In a doua faz a algoritmului, valorile ordonate sunt scoase, prin celula din stnga.Exist mai multe variante:1. fiecare procesor ncepe s transmit spre stnga, imediat ce numerele sunt sortate;2. cunoscnd poziia sa din vectori numrnd valorile inspectate, fiecare procesor

    calculeaz momentul cnd ncepe s transmit spre stnga;3. procesorul din dreapta este special; el ncepe s transmit spre stnga imediat ce

    primete o valoare; toate celelalte ncep s transmit spre stnga imediat ceprimesc o valoare dinspre dreapta;

    4. fiecare procesor ncepe s transmit spre stnga imediat ce nu mai primete ovaloare dinspre stnga.

    Din cele patru metode doar ultimele doua nu impun cunoaterea poziiei procesoarelorn vectori contorizarea valorilor. Metoda 3 reclama 4N-3 pai, n timp ce 4 cere 3N-1 pai pentru ambele faze de sortare i de scoatere a rezultatelor.

    Exerciiu. Alctuii descrieri pentru metodele 3 si 4, considernd pe rnd modelelede calcul paralel cu memorie comuna i cu transmitere de mesaje. n primul caz,comunicarea ntre procese se realizeaz prin variabile comune special dedicate.

    3.2. Msuri de performana

    Msurile obinuite de apreciere a algoritmilor paraleli sunt: timpul total T necesar execuiei i numarul de procesoare utilizate P.

    In algoritmul prezentat, P = N i T = O(N).

    Observaie. In seciunea curent timpii se refer la cazul cel mai defavorabil.

    De multe ori, se compar performanele atinse de un algoritm cu cele mai buneperformane ale unui algoritm secvenial care rezolva aceeai problem. Astfel, dac

    G este timpul de execuie al celui mai rapid algoritm secvenial, se defineteaccelerarea S (speedup) corespunztoare unui algoritm paralel ca raportul dintre G siT, adic S = G/T. In cazul algoritmului precedent, S= O(N log N)/ O(N) = O(log N).

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    4/26

    45

    Ideal ar fi ca algoritmul paralel gsit s fie de P ori mai rapid dect cel mai bunalgoritm secvenial, sau mcar S = O(P). Un exemplu este cutarea unei valori ntr-unfiier distribuit, folosind maini SIMD cu acces concurent la citire i exclusiv lascriere. Fiecare procesor inspecteaz un sub-fiier de lungime n/P n timp O(n/P).Timpul necesar unui algoritm secvenial pentru cutarea n ntreg fiierul de lungimen, este O(n). Spunem, n acest caz, c acceleraia este linear. Teoretic, nu se poateobtine o acceleraie mai bun. Astfel, dat fiind un algoritm paralel care se execut n T

    pai pe P procesoare, putem oricnd folosi un singur procesor pe care procesele s seexecute secvenial n TP pasi. Ca urmare, G

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    5/26

    46

    In cazul nostru avem C = O(N2). Aceast msur poate fi folosit n caracterizareaineficienei datorate nefolosirii complete a procesoarelor, de ctre un algoritm paralel.

    Mai precis, eficiena E a unui algoritm paralel este raportul E = G/C dintre timpul delucru al algoritmului secvenial optim i costul algoritmului paralel. Avem

    E = G/C = G/(TP) = S/Pdeci eficiena poate fi exprimat i ca raportul dintre accelerare i numrul de

    procesoare. In cazul exemplului dat avem E = O((log N)/N).

    3.3. Cazul unui numr redus de procesoare

    Majoritatea msurilor de performana sunt calculate pentru situaia ideal n carenumrul de procesoare utilizate egaleaza numrul de procese. In exemplul datanterior, numrul de procesoare utilizate este N, programul de sortare cuprinznd N

    procese. Ce se ntampl n cazul unui numar mai mic de procesoare?

    Exist o procedur general foarte simpl de execuie a unui algoritm proiectat pentruo reea de P1 procesoare, pe o reea de P2 procesoare, unde P2

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    6/26

    47

    de date, precum i de interesul teoretic pe care astfel de msuri de complexitate l

    prezint.

    Punctul cheie n detalierea operaiilor algoritmului de sortare la nivel de bit lconstituie comparaiile. O metod simpl este compararea numerelor bit cu bit,secvenial, ncepnd cu bitul cel mai semnificativ. A doua metod folosete un arbore

    binar complet. Numerele sunt comparate bit cu bit, informaiile rezultate fiind apoicondensate prin mperecheri succesive, pn la obinerea rspunsului final. Procedeuleste ilustrat n figura 3.3.

    Figura 3.3(msb cel mai semnificativ bit; lsb cel mai puin semnificativ bit; s- valoarea din

    stnga; d - valoarea din dreapta)

    Arborele binar este superior algoritmului secvenial, din dou motive. Mai nti, elutilizeaz log k + 1 pai pentru a afla rezultatul, n timp ce primul cere k pai. Apoi,acelai arbore poate fi folosit pentru a specifica procesoarelor care dintre cele douanumere trebuie trecut mai departe i care trebuie pstrat (aa cum reiese din figura3.4).

    s d

    msb

    lsb

    =

    s

    d

    s

    s

    =

    =0 0

    0 0

    1 0

    0 1

    pas 3pas 2pas 1

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    7/26

    48

    Figura 3.4

    Cu aceasta, dupa 2*log k pai, comparaia celor dou numere este terminati cei kbii ai numarului mai mare pot fi mutai simultan spre urmtoarea celul. Inlocuindfiecare procesor din vectorul folosit pentru sortare, cu un arbore complet de

    procesoare de un bit, putem construi o reea cu (2k-1)N procesoare de un bit, care face(2N-1)*2*log k pai pentru a executa prima faz a algoritmului.

    Exist ns un algoritm mai bun de comparare, care, n mod surprinztor, se bazeaz pe un tablou linear de procesoare i nu pe un arbore complet. Secretul const nutilizarea acestuia n linie de asamblare (pipeline).

    Ideea de baz este ilustrat n figura 3.5, n care se consider un vector de trei procesoare pe bit, folosit pentru a gsi cea mai mic dintre valorile 2, 0, 5, 1, 2(evident, n reprezentarea lor binar).

    Vectorul de procesoare face, n mod repetat, compararea valorii memorate cu valoareaprimit din stnga, o reine pe cea mai mici o transmite n dreapta pe cealalt.

    Soluia are urmtoarele particulariti: execuia n linie de asamblare face ca n timp ce un procesor compar o perechede bii a dou numere succesive, procesorul de sub el s lucreze cu biii mai puinsemnificativi ai perechii de numere anterioare, iar procesorul de deasupra s lucrezecu biii mai semnificativi ai perechii de numere succesoare;

    la fiecare pas, un procesor primete la intrare un bit, iar de la procesorul dedeasupra o informaie asupra comparaiei fcute de el la pasul anterior (aceasta

    s d

    msb

    lsb

    s

    s

    s

    s

    s

    s

    s0 0

    0 0

    1 0

    0 1

    pas 3pas 2pas 1

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    8/26

    49

    comparaie se refer la biii mai semnificativi ai acelorai numere) - s dac numrul de

    la intrare este mai mare, d dac numrul memorat este mai mare, = dac cele dounumere sunt egale (n rangurile mai mari dect rangul curent);

    3 0 5 1 2 0 1/ / / / / / s /1 0 1 1 0 [ ] 0

    iniial dup pasul 4---------------------------------------------------------------

    0 0 1 0 [0] [0] -> 0 0 1 0/ / / / = / /1 0 0 0 1 [ ] 1 [0] -> 0 0 1/ / / / = / /1 0 1 1 0 [ ] 1 0 [1] -> 1 0

    dup pasul 1 dup pasul 5------------------------------------------------------------

    0 0 1 [0] -> 0 [0] -> 0 0 1 0/ / / = / / /1 0 0 0 [1] [0] -> 1 0 0 1/ / / s / / /1 0 1 1 0 [ ] 1 [0] -> 1 1 0

    dup pasul 2 dup pasul 6-------------------------------------------------------------

    0 0 [0] -> 1 0 [0] -> 0 0 1 0/ / s / / / /

    1 0 0 [0] -> 1 [0] -> 1 0 0 1/ / d / / / /1 0 1 1 [0] [0] -> 1 1 1 0

    dup pasul 3 dup pasul 7-------------------------------------------------------------rezultat -> 0 3 1 5 2

    Figura 3.5

    dac primete s, procesorul transmite bitul de la intrare la ieire i transmite s njos; dac primete d, procesorul transmite bitul memorat la ieire, memoreaz bitul dela intrare i transmite d n jos; dac primete =, transmite bitul mai mare la ieire, memoreaz bitul mai mic itransmit n jos s, d sau = n mod corespunzator;

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    9/26

    50

    cnd nu mai primete nimic la intrare, procesorul scoate n stanga valoareamemorati apoi toate valorile primite din dreapta (faza a doua).

    Se poate observa c aciunea vectorului de procesoare pe un bit este similara celei aprimului procesor de cuvnt, din algoritmul de ordonare. In ambele cazuri, cea maimic valoare este pastrat, restul valorilor fiind transmis spre dreapta. Putem, deci,combina N vectori de cte k bii, formnd astfel o matrice de procesoare, pentru arealiza sortarea celorN numere. Prima faz a sortrii se poate executa n (k-1)+(2N-1)= 2N+k-2 pai, la nivel de bit. A doua faz a sortrii se poate derula la fel ca nmodelul "cuvnt", ceea ce conduce la sortarea complet a N cuvinte de cte kbii n3N+k-2 pai cu N*kprocesoare pe un bit.

    3.5. Limite inferioare

    Exemplul anterior este util sub dou aspecte. Mai nti, el arat rolul topologieireelelor de procesoare n atingerea unor performane bune n calculul paralel. Ne

    putem imagina cu uurin c diferitele combinaii de aciuni exemplificate aici pentruoperaii foarte simple, pot apare n general, n calculul paralel, deci i pentru aciunide o complexitate mai mare.

    In al doilea rnd, el ne permite discutarea unor aspecte legate de optimalitateaalgoritmilor paraleli. Dac ne referim la algoritmul prezentat n termenii vitezei saueficienei, putem spune ca el nu este optimal, deoarece exist algoritmi mai rapizi careutilizeaz chiar mai puine procesoare. Reeaua necesar pentru aceti algoritmi este

    ns mai complex dect o matrice k*N. Dac ne limitm la matrice k*N, atunciputem afirma c algoritmul este optim, deoarece orice algoritm de sortare executat peo astfel de configuraie reclam un timp O(k+N). Motivele sunt urmtoarele:

    1) Dac sunt folosite numai kprocesoare pentru introducerea datelor, sunt necesari Npai numai pentru citirea tuturor celorN numere.

    2) Diametrul unei reele este distana maxim ntre oricare doua noduri ale sale.Distana ntre dou noduri este numrul minim de legturi traversate pentru a ajungede la un nod la celalalt. Pentru o reea de k*N noduri, diametrul este N+k-2.Diametrul este o indicaie bun asupra complexitii, deoarece comunicareainformaiei ntre nodurile aflate la o distand consumd pai ai algoritmului.

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    10/26

    51

    De exemplu, presupunnd c la sortare numerele x1 = x110...01, x2=...=xN= 010...0

    sunt dispuse iniial n matricea de procesoare astfel c bitul i cel mai semnificativ alnumruluij este dispus n matrice n poziia i,j, atunci timpul trebuie s fie cel puink+N-2. Aceasta deoarece bitul cel mai puin semnificativ al celui mai mare numr este1 daci numai dac x11 = 1, ceea ce nseamn c informaia din pozitia 1,1 trebuie

    s ajung n poziia k,N pentru ca sortarea s fie terminat.

    3) Lrgimea biseciei unei reele este numrul minim de legturi care trebuieindepartate pentru a mpri reeaua n dou subreele separate, avnd acelai numrde noduri (sau diferena de un nod). Aceast caracteristic este important deoareceuneori valorile calculate de o jumatate a reelei sunt necesare celeilalte jumti.

    De exemplu, n sortare, este posibil ca numerele mai mari s fie plasate n jumtateastng a matricei de procesoare, iar numerele mai mici n dreapta. Ca urmare, (k*N)/2bii trebuie s treac din stnga n dreapta reelei i invers. Cu o lrgime a biseciei dek legturi, sunt necesari cel putin N/2 pai.

    Caracteristicile prezentate trebuie folosite cu grij n calculul complexitii. Existexemple care arat c luarea lor n consideraie fr discernmnt poate conduce laaprecieri eronate. Astfel, n [Leighton92] se menioneaz cazul sortrii a N numere deK bii folosind un arbore binar complet. O configuraie posibil este prezentat nfigura 3.6.

    Figura arat coninutul procesoarelor frunz, dup sortare. Procesorul rdcina are log

    N celule (unde N este numrul valorilorirului de sortat). Procesoarele din nodurileintermediare ale arborelui sunt de o celula. In fine, procesoarele frunz au cte Kcelule (unde Keste numrul de bii din reprezentarea unei valori din irul de sortat).

    Diametrul reelei este 2.log N + 2.K - 2, iar lrgimea benzii de intrare a datelor esteK.N (presupunnd c toate numerele sunt introduse deodat). In fine, lrgimea

    biseciei este 1, dac log N = 1 i 2 n celelalte cazuri.

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    11/26

    52

    Figura 3.6

    Deoarece, n cel mai ru caz, algoritmul trebuie s mute KN bii prin bisecie, artrebui ca algoritmul de sortare s solicite O(KN) pai. Cu toate acestea, pentru situaiin care keste mic, rezultatul este cu totul altul. In particular, pentru k=1, exist unalgoritm O(log N) care realizeaz sortarea.

    3.6. Proprieti ale modelului de evaluare

    Exemplele de evaluare prezentate au evideniat modul de considerare a timpului decalcul i de comunicare n analiza algoritmilor paraleli. Sistematizm n continuareproprietile pe care se bazeaz aceste analize.

    Proprietile procesoarelor. Fiecare procesor are un control local. Aciunile luidepind de coninutul memoriei locale i de intrrile proprii. Complexitatea depinde denivelul operaiilor considerate: pe bit sau pe cuvant. Uneori pachetul este consideratca unitate de date, operaiile uzuale fiind recepia, memorarea i transmisia unui

    pachet.

    Proprietile interconexiunilor. Presupunerile care se fac uzual despre reeaua deprocesoare sunt urmtoarele:

    topologia este fix; gradul fiecrui nod este limitat;

    1

    14

    0

    1

    1

    1

    9

    0

    0

    0

    5

    1

    0

    1

    0

    1

    1

    0

    0

    rocesorul rdcin are lo N celule

    rocesoare intermediare

    procesoarefrunza cu

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    12/26

    53

    dimensiunea reelei este o funcie polinomial (uzual linear) de dimensiuneaproblemei.

    Proprietile protocolului de intrare/iesire. Constrngerea uzual este ca o intrareeste prevazut o singura dat. Complexitatea include astfel i costul difuzarii intrrii,dac este cazul. In plus, locul i momentul apariiei fiecrei intrri i, corespunztor afiecrei ieiri, trebuie specificate n avans (adic nainte de nceperea execuieialgoritmului).

    3.7. Modele generale

    Cele prezentate anterior evideniaz faptul c analiza complexitii algoritmilor paraleli presupune folosirea unui model formal, care s permit evaluarea parametrilor de performan, cum sunt timpul de execuie, lucrul, accelerarea etc.Modelul folosit n exemplul dat este particular unei anumite categorii de maini

    paralele, SIMD cu memorie local. Din pcate, acesta nu este singurul model folositn calculul paralel, deoarece organizarea mainilor paralele difer mult mai mult ntreele dect cea a mainilor secveniale. Pe de alt parte, folosirea unui model particular,care s surprind ct mai fidel caracteristicile fiecrei categorii de maini estenepractic, datorit numrului mare de modele care ar fi necesare. O alternativ estefolosirea unui numr mic de modele abstracte, care nu ncearc s reproduc fidelcomportarea vreunei maini paralele particulare, dar au avantajul c algoritmiidezvoltai pe baza lor pot fi tradui cu uurin n programe care se dovedesc eficiente

    pe mainile paralele reale.

    Modelele paralele generalizeaz modelul secvenial RAM, prin introducerea maimultor procesoare. Ele se clasific n trei categorii, n care este uor s plasmarhitecturile de maini paralele definite n capitolul anterior: maini cu memorie local (din care face parte i modelul folosit anterior) maini cu memorie modulari maini paralele cu acces aleator la memorie PRAM.O main cu memorie local cuprinde o mulime de procesoare, fiecare cu propria samemorie, ataate unei subreele de interconectare. Fiecare procesor poate accesadirect propria memorie i prin intermediul reelei de interconectare celelalte memorii.Accesul local se consider c dureaz o unitate de timp, accesul distant, la memoria

    unui alt procesor depinde de performanele reelei de interconectare i de nivelultraficului celorlalte procesoare.

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    13/26

    54

    O main cu memorie modular const din N procesoare i M module de memorie,ataate unei reele comune. Un procesor acceseaz un modul de memorie printransmiterea unei cereri prin reea. Uzual, timpul de aces al oricrui procesor laoricare modul este uniform, dar depinde de performanele reelei i de "tiparul"operaiilor de acces la memorie.

    O main PRAM const din N procesoare conectate la o memorie comun, partajat.Se consider c, ntr-un singur pas, procesele pot avea acces simultan, direct lamemoria partajat.

    Desigur, modelele sunt foarte generale i destul de ndeprtate de structura ifuncionarea mainilor reale. De exemplu, nici o main real actual nu seconformeaz n mod ideal modelului PRAM, realiznd ntr-o unitate de timp, oriceacces la memoria partajat. Cu toate acestea, modelele menionate au fost folosite ndezvoltarea algoritmilor paraleli i distribuii, datorit simplitii lori a uurinei defolosire n proiectarea algoritmilor.

    3.7.1. Modelul grafurilor orientate aciclice (work-depth)

    O alternativ natural la utilizarea unor modele orientate pe categorii de maini estefolosirea unor modele orientate spre algoritmi. Fr a ine seama de particularitilesistemelor de calcul paralele i distribuite pe care urmeaz a fi executai algoritmiidezvoltai, modelele faciliteaz exprimarea fr constrngeri artificiale a rezolvrii

    problemelor (cum ar fi numrul de procesoare sau topologia sistemului distribuit),exploatnd la maximum paralelismul intrinsec al problemelor. O clas important aunor astfel de modele este cea denumit "lucru-adncmie", la care ne referim ncontinuare.

    Multe calcule pot fi reprezentate n forma unor grafuri (circuite) orientate aciclice,dup urmtoarele reguli: fiecare intrare este reprezentata ca un nod fr arce de intrare fiecare operatie este reprezentat ca un nod ale crui arce de intrare provin de lanodurile care reprezint operanzii o ieire este reprezentat ca un nod fr arce de ieire.

    Un exemplu este prezentat n figura 3.7, care descrie un algoritm de calcul al

    sumei elementelor unui tablou unidimensional.

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    14/26

    55

    Figura 3.7

    Graful descrie operaiile executate de algoritm i constrngerile de preceden asupraordinii n care operaiile sunt executate. Modelul este independent de orice arhitecturi orice numr concret de procesoare. El pune n eviden: lucrul efectuat de algoritm, adic numrul total de operaii adncimea, adic lungimea celui mai lung lan de dependene secveniale dinalgoritm.

    Raportul lucru / adncime se numete paralelismul algoritmului. In exemplul dinfigura 3.7, lucrul cerut de calculul sumei este de 7 operaii. Adncimea este de treioperaii i poate fi calculat uor pornind de la orice frunzi numrnd operaiile pecalea pn la rdcina arborelui.

    In acest caz, generalizarea este foarte simpl: pentru nsumarea a n numere suntnecesare n-1 operaii, adncimea fiind de log n.

    3.7.2. Folosirea modelului pentru calculul complexitii

    Modelul de graf poate fi folosit pentru aprecierea complexitii algoritmilor paraleli pornind de la forma acestora ntr-un limbaj de descriere. S relum problema

    anterioar, a crei descriere este urmtoarea:

    a[1]

    +

    +

    +

    a[3]

    a[5]

    a[7]

    a[2]

    a[4]

    a[6]

    a[8]

    +

    +

    +

    +

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    15/26

    56

    var a, b: array [1:n] of real; /* presupunem n = 2k */

    var s: real;fa i := 1 to n do in parallel b[i] := a[i] af;fa h := 1 to log n dofa i := 1 to n/2hdo in parallel

    b[i] := b[2*i-1] + b[2*i]af

    af;s := b[1];

    Descrierea nu conine nici o mentiune despre numrul de procesoare, sau despre feluln care operaiile vor fi alocate procesoarelor. In schimb, el poate fi analizat n numrde unitti de timp necesare, n fiecare unitate de timp executndu-se n paralel oricenumr de operaii.

    Astfel, numrul total de uniti de timp este log n + 2, deci T(n) = O(log n). In prima unitate de timp sunt executate n paralel n operaii. In iteraia h se fac n/2hoperaii, unde 1

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    16/26

    57

    pai paraleli.

    ExemplificarePentru exemplificare, s considerm c executm algoritmul de nsumare aelementelor unui tablou pe un sistem PRAM cu p procesoare, unde p = 2q = p = 2qceeace echivaleaz cu

    k-h >= qatunci operaiile se mpart egal procesoarelor. Altfel, operaiile sunt executate de cele2k-h procesoare de indici inferiori.

    var A, B: array [1:n] of real; /* n = 2k si p = 2q */var S: real; l: int := n/p;fa s := 1 to p do in parallel

    fa j := 1 to l -> B[l*(s-1)+j] := A[l*(s-1)+j] af;fa h := 1 to log n ->

    if k-h-q >= 0 ->fa j := 2 k-h-q(s-1) + 1 to 2 k-h-q s ->

    B[j] := B[2*j-1] + B[2*j]af

    [] k-h-q < 0 ->if s B[s] := B[2*s-1] + B[2*s]fi

    fiafif s = 1 -> S := B[1] fi

    af;

    Not. Algoritmul merge pentru p >= n/2.

    Pentru a estima timpul de execuie al algoritmului, observm c primul pas ia O(n/p)uniti de timp, deoarece fiecare procesor execut n/p atribuiri. Iteraia h din ciclu iaO(n/(2h p)), deoarece un procesor are de executat cel mult sup(n/(2h p)) operaii.

    Ultimul pas ia o unitate de timp. Ca urmare, timpul de execuie pentru p procesoare,Tp(n) este inferior lui

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    17/26

    58

    n/p + h=1, log n sup(n/(2hp))

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    18/26

    59

    3.7.5. Implementare pentru reele de procesoare

    In cazul implementrii algoritmilor paraleli pe reele de procesoare, exist mai multeposibiliti de alegere a topologiei: liniar, inel, arbore, matrice, cub, hipercub. Deregul, folosirea unor topologii diferite conduce la rezolvri diferite ale aceleiai

    probleme. Transpunerea soluiei pentru un hipercub este deosebit de simpl, datoritcapacitii acestuia de adaptare la diferite topologii, printre care i aceea de arbore.

    Un hipercub const din p = 2d procesoare, indexate de la 0 la p-1, interconectate intr-un cub boolean d-dimensional, definit dup cum urmeaz. Fie reprezentarea binar alui i, 0

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    19/26

    60

    iar n ultimul pas, n A[0] obinem ntreaga sum.

    In algoritmul urmtor, i(l) denot indexul obinut din i prin complementarea bitului l.Operaia A[i] := A[i] + A[i(l)] se face n doi pai: n primul pas, procesorul P[i]copiaz valoarea A[i(l)] preluat de la procesorul P[i(l)] pe legtura dintre cele dou;n al doilea pas, P[i] face adunarea i memoreaz suma in A[i].

    var A: array [0:n-1] of real; /* n = 2d */fa i := 0 to n-1 do in parallel

    fa l := d-1 to 0 ->if i

    A[i] := A[i] + A[i(l)]fi

    af

    af

    Algoritmul se termin n O(log n) uniti de timp, la fel ca i implementarea PRAM.

    Problem. Descriei algoritmul de nsumare pentru cazul n care numrul deprocesoare p este mai mic dect numrul de elemente ni fiecare nod memoreazn/pelemente ale tabloului A.

    3.8. Execuia programelor distribuite

    In cazul programelor distribuite, timpul total de execuie se definete ca timpul scurs

    Figura 3.8 (Foster 1995)

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    20/26

    61

    din momentul cnd primul procesor ncepe execuia sa (mai precis a unuia din

    procesele programului distribuit) pn n momentul n care ultimul procesor terminexecuia. n evoluia unui proces se disting mai multe perioade: de calcule, decomunicare i de inactivitate, astfel c timpul total de execuie se exprim ca sumatimpilor de calcul (Tcomp), de comunicare (Tcommun) si de inactivitate (Tidle) raportat lanumarul de procesoare (P):

    T = (1/P) (Tcomp + Tcommun + Tidle)sau

    T = (1/P) ( i=0,P-1 Ticomp + i=0,P-1 T

    icommun + i=0,P-1 T

    iidle)

    unde:Ticomp = timpul total de calcul pe procesorul iTicommun = timpul total de comunicare al procesorului iTiidle = timpul total de inactivitate al procesorului i.

    n calculul analitic al timpului total de execuie, se neglijeaz, de regul, timpul deinactivitate.

    Timpul de calcul depinde de dimensiunea problemei, N, numarul de taskuri sau deprocesoare si de caracteristicile procesoarelor si memoriei.

    Timpul de comunicare este timpul consumat pentru transmiterea i pentru recepiamesajelor. Acetia difer de la un tip de comunicaie la alta; astfel, dac dou procesesunt executate de procesoare diferite, comunicarea ntre ele are o durat mai mare

    (comunicarea ntre procesoare consum mai mult timp); comunicarea ntre dou procese executate de acelai procesor este mai eficient (consum mai puin timp).Pentru simplificare, se consider c cele dou tipuri de comunicri au duratecomparabile i se utilizeaz o formul comun de calcul. Timpul de comunicare aunui mesaj (transmitere sau recepie) are dou componente:ts - corespunde timpului consumat de operaiile de pregtire a comunicrii i esteindependent de lungimea mesajului;tw corespunde timpului de comunicare a unui cuvnt din mesaj.

    Cu acestea, timpul de comunicare a unui mesaj de lungime L devine:

    Tmsg = ts + twL

    Formula este confirmat experimental (Foster 1995) prin msurarea durateitransmisiei dus-ntors a unui mesaj (round-trip time).

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    21/26

    62

    ntr-un model de cost mai detaliat, se poate lua n considerare competiia ntre procesepentru comunicarea pe un acelai canal. Evident aceast competiie lungete timpul decomunicare. Daca S procese vor sa utilizeze n acelai timp un canal, duratacomunicarii efective se mrete de S ori (evident, timpul de pregtire nu este afectat):

    Tmsg-b = ts + twSL

    Valoarea lui S difer de 1 doar dac cele S procese transmit n acelai sens pe uncanal, aa cum se arat n Figura 3.9: n cazul (b), P0 i P1 partajeaz canalul (P1,P2),n timp ce n cazul (c), P0 i P3 transmit n sensuri diferite pe acest canal i seconsider c transmisiile nu interfer.

    (a) S = 1 (b) S = 2 (c) S = 1

    Figura 3.9 (Foster 1995)

    Ca aplicaie, considerm algoritmul lui Floyd pentru calculul drumurilor celor maiscurte ntr-un graf reprezentat prin matricea de adiacene I, a crui variant secvenialeste urmtoarea:

    fa k := 0 to N-1 ->fa i := 0 to N-1 ->

    fa j := 0 to N-1 ->I[i,j]k+1 = min(I[i,j]k, I[i,k]k + I[k,j]k)

    af

    af

    af

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    22/26

    63

    Dac tc este durata unei iteraii n algoritmul precedent, timpul total de execuie al

    algoritmului secvenial este:Tsecv = tc N

    3

    Vom analiza dou variante distribuite, ambele folosind P procesoare. n primavariant, se face o descompunere uni-dimensional a matricei I n P grupuri de linii(fiecrui procesor i se asociaz N/P linii). Algoritmul poate folosi cel mult N

    procesoare, deci ntotdeauna numrul de procesoare este mai mic dact dimensiuneamatricei, Pfa i = p_i_start to p_i_end ->

    fa j = 0 to N-1 ->I[i,j]k+1 = min(I[i,j]k, I[i,k]k + I[k.j]k)

    af

    af

    af

    Figura 3.10 (Foster 1995)

    n pasul k, procesoarele au nevoie de linia k a matricei Ik (Figura 3.10). Procesorulcare pstreaz aceast linie o comunic n log P pai folosind algoritmul de difuzare,nainte ca fiecare din celelalte procesoare s nceap calculul liniilor matricei Ik+1 decare rspund. Deoarece fiecare mesaj are N cuvinte, timpul de difuzare a unei linii

    este:log P ( ts + twN).

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    23/26

    64

    Timpul total de execuie al acestei variante distribuite este:

    Tdist-1 = tc N3/P + N log P ( ts + twN)

    El este compus din timpul de calcul tc N3/P, care este timpul algoritmului secvenial

    mprit la numarul de procesoare plus timpul de comunicare N log P ( ts + twN), careeste de N ori timpul de difuzare a unei linii.

    n a doua variant, facem o descompunere bi-dimensional, pe linii i coloane:fiecare procesor pstreaz local elementele aflate pe una sau mai multe linii isimultan pe una sau mai multe coloane din I i este responsabil de calculul valorilorelementelor din liniile i coloanele respective. Evident, numarul de procesoare P nu

    poate fi mai mare de N2. Cele P procesoar se dispun ntr-o matrice de P linii pe Pcoloane. Dac procesorul p pstreaz elementele aflate pe liniile de la p_i_start lap_i_endi simultan pe coloanele de la p_j_start la p_j_end atunci codul su se

    poate descrie n felul urmtor:

    fa k := 0 to N-1 ->fa i := p_i_start to p_i_end ->

    fa j := p_j_start to p_j_end ->I[i,j]k+1 = min(I[i,j]k, I[i,k]k + I[k,j]k)

    af

    af

    af

    Figura 3.11 (Foster 1995)

    n fiecare pas k, fiecare proces are nevoie de datele sale locale i de cte N/P valoride la alte dou procese care pstreaz:

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    24/26

    65

    - elementele din linia ki coloanele de la p_j_start la p_j_end

    - elementele din coloana ki liniile de la p_i_start la p_i_end.

    Fiecare din cele dou mesaje are N/P elemente, astfel nct difuzarea unuia dureazlog P ( ts + twN/P)

    deoarece difuzarea se face unui numr de P procese.

    n cei N pai, operaia se repet de 2N ori. Ca urmare, timpul total de execuie:

    Tdist-2 = tc N3/P + 2N log P ( ts + twN/P)

    = tc N3/P + N log P ( ts + twN/P).

    3.9. Modelul LogP

    Un model mai adecvat studiului performanelor pe maini reale este LogP (Figura3.12).

    Figura 3.12 Modelul LogP

    Modelul consider P procesoare, fiecare cu memoria sa local, legate printr-o reea deinterconectare. Parametrii modelului sunt: L latena, sau ntrzierea de transmitere a unui mesaj coninnd un numr mic

    de cuvinte, de la procesorul / memoria surs la destinatar o - overhead, durata pentru care procesorul este angajat n transmiterea sau

    recepia fiecrui mesaj; n timpul acesta procesoul nu poate face alte operaii

    P M P M P M

    Reea de interconectare

    overhead

    latena L

    overheadgap g

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    25/26

    66

    g - gap, intervalul minim de timp ntre dou transmiteri succesive sau dourecepii succesive la acelai modul

    P - numrul de module procesor / memorie.Reeaua are o capacitate limitat, astfel c cel mult sup(L/g) mesaje pot fi n tranzit laun moment dat, de la orice procesor sau la oricare procesor. Cea mai simpl operaiede comunicare, transmiterea unui singur pachet de la o main la alta, cere un timp deL+2o. O operaie cerere/rspuns, precum o citire sau o scriere blocant, ia un timp de2L+4o. Fiecare procesor este implicat un timp de 2o, restul timpului putnd fi utilizat

    pentru calcul, sau pentru alte operaii de intrare/ieire.

    Ca aplicaie considerm difuzarea unei valori. Conform modelului PRAM,

    transmiterea are loc conform tiparului urmtor:P0 -> P1 de la P0 la P1P0, P1 -> P2, P3 de la P0 i P1 la P2 i P3P0, P1, P2, P3 -> P4, P5, P6, P7 ...

    Presupunnd g>=0 i lund P=8, o=2, g=4, L=6, obinem din calcul un timp total dedifuzare egal cu 30 de unitai.

    Pentru modelul LogP, adoptm convenia corice procesor care primete o valoare,o transmite imediat altor procesoare, cu condiia ca nici un procesor s nu

    primeasc mai mult de o valoare. Graful corespunztor variantei optime este cel din

    figura 3.13. Timpul corespunztor este de 24 de uniti.

    Figura 3.13. Graful optim

    0

    10 14 18 22

    20 24 24

    P0

    P5 P3 P2 P1

    P7 P6 P4

  • 8/8/2019 APD - Note Curs - 3 Complexitate

    26/26

    67

    P0 o o o o

    P1 o

    P2 o

    P3 o o

    P4 o

    P5 o o o

    P6 o

    P7 o

    timp 02 04 06 08 10 12 14 16 18 20 22 24 26

    Figura 3.14. Schema de difuzare

    Exerciiu

    Alctuii graful optim i schema de difuzare corespunztoare modelului PRAM,pentru aceleai valori ale parametrilor LogP.