Curs 11 - cs.ubbcluj.rovniculescu/didactic/PPD/C11.pdf · Curs 11 Programare Paralela si...
44
Curs 11 Programare Paralela si Distribuita Metode de evaluare a performatei programelor paralele Granularitate Scalabilitate Curs 11 - PPD 1
Transcript of Curs 11 - cs.ubbcluj.rovniculescu/didactic/PPD/C11.pdf · Curs 11 Programare Paralela si...
Curs11ProgramareParalelasiDistribuita
MetodedeevaluareaperformateiprogramelorparaleleGranularitateScalabilitate
Curs11-PPD 1
Complexitate– considera=igenerale
• Dacaincazulalgoritmilorsecven=aliperformantaestemasurataintermeniicomplexita=ilor=mpsispa=u,incazulalgoritmilorparalelisefolosescsialtemasurialeperformantei,careauinvederetoateresurselefolosite.• Numaruldeprocesoareincazulprogramariiparalele=> oresursaimportanta
• Pentrucomparareacorectaavarianteiparalelecuceaseriala,trebuie– saseprecizezearhitecturasistemuluidecalculparalel,– sasealeagaalgoritmulserialcelmaibunsi– saseindicedacaexistacondi=onarialeperformanteialgoritmului
datoritavolumuluidedate.
2Curs11-PPD
Observa=i
• Incalcululparalel,ob=nereaunui=mpdeexecu=emaibunnuinseamnaneaparatu=lizareaunuinumarminimdeopera=i,asacumesteincalcululserial.
• Factorulmemorienuareoimportantaatatdemareıncalcululparalel(rela=v).
• Inschimb,oresursamajoraınob=nereauneiperformantebuneaalgoritmuluiparaleloreprezintanumaruldeprocesoarefolosite.
• Daca=mpuldeexecu=eauneiopera=iaritme=ceestemultmaimaredecat=mpuldetransferaldatelorintredouaelementedeprocesare,atunciintarziereadatoratareteleiestenesemnifica=va,dar,incazcontrar,=mpuldetransferjoacaunrolimportantındeterminareaperformanteiprogramului.
3Curs11-PPD
4
Timpdeexecu=e
Timpuldeexecu=ealunuiprogramparalelmasoaraperioadacares-ascursıntremomentulini=eriiprimuluiprocessimomentulcandtoateproceseleaufostterminate.
Curs11-PPD
Complexitatea=mp
• In=mpulexecu=eifiecareprocesorexecuta– opera=idecalcul,– decomunica=e,sau– esteinasteptare.
• Timpultotaldeexecu=esepoateob=nedinformula:• sauincazulechilibrariperfectealeincarcariidecalculpefiecareprocesor
dinformula:
5Curs11-PPD
Evaluareacomplexita=i
• Casiincazulprogramariisecven=ale,pentruadezvoltaalgoritmiparalelieficien=trebuiesaputemfaceoevaluareaperformanteiincadinfazadeproiectareaalgoritmilor.
• Complexitatea=mppentruunalgoritmparalelcarerezolvaoproblemaPncudimensiuneanadatelordeintrareesteofunc=eTcaredepindeden,darsidenumaruldeprocesoarepfolosite.
• Pentruunalgoritmparalel,unpaselementardecalculseconsideraafiomul=medeopera=ielementarecarepotfiexecutateinparaleldecatreomul=medeprocesoare.
• Complexitatea=mpaunuipaselementarseconsideraafiO(1).
• Complexitatea=mpaunuialgoritmparalelestedatadenumarareaatatapasilordecalculnecesaridarsiapasilordecomunica=eadatelor.
6Curs11-PPD
7
Overhead
• Tall==mpultotal(toateelementeledeprocesare).
• TS==mpserial.
• Tall-TS==mptotalincaretoateprocesoarelesuntimplicateinopera=icarenusuntstrictlegatedescopulproblemei(non-goal_computa=onwork).– nume->totaloverhead.
• Tall=pTP(p=nr.procesoare).
• To=pTP-TS
Curs11-PPD
Accelerarea(“speed-up”),
• AccelerareanotatacuSp,estedefinitacaraportuldintre=mpuldeexecu=ealceluimaibunalgoritmserialcunoscut,executatpeuncalculatormonoprocesorsi=mpuldeexecu=ealprogramuluiparalelechivalent,executatpeunsistemdecalculparalel.
• Dacasenoteazacut1=mpuldeexecu=ealprogramuluiserial,iartp=mpuldeexecu=ecorespunzatorprogramuluiparalel,atunci:
– nreprezintadimensiuneadatelordeintrare,– pnumaruldeprocesoarefolosite.
8Curs11-PPD
Variante
•rela+va,candtseste=mpuldeexecu=ealvarianteiparalelepeunsingurprocesoralsistemuluiparalel;
•reala,candsecompara=mpulexecu=eiparalelecu=mpuldeexecu=epentruvarianta
serialaceamairapida,peunprocesoralsistemuluiparalel;•absoluta,candsecompara=mpuldeexecu=ealalgoritmuluiparalelcu=mpulde
execu=ealceluimairapidalgoritmserial,executatdeprocesorulserialcelmairapid;•asimpto+ca,candsecompara=mpuldeexecu=ealceluimaibunalgoritmserialcu
func=adecomplexitateasimpto=caaalgoritmuluiparalel,ınipotezaexistenteinumaruluinecesardeprocesoare;
•rela+vasimpto+ca,candsefolosestecomplexitateaasimpto=caaalgoritmuluiparalelexecutatpeunprocesor.Analizaasimpto+ca(consideradimensiuneadatelornsinumaruldeprocesoarepfoarte
mari)ignoratermeniideordinmic,siestefolositoareınprocesuldeconstruc=ealprogramelorperformante.
9Curs11-PPD
Eficienta
• Eficientaesteunparametrucaremasoaragraduldefolosireaprocesoarelor.
• Eficientaestedefinitacafiind:
E=Sp/p• Sededucecavaloareaeficienteiesteıntotdeaunasubunitara.
10Curs11-PPD
11
LegealuiAmdahl
• Afirmacaaccelerareaprocesariidepindedeprocentulpar=isecve=alefatadeceaparaleizabila:
seq=frac=acalculuisecven=al;par=frac=acalculuiparalel;Seconsideracalcululserial=1unitateSpeedup=1/(seq+par/n)seq=(1–par),n=#procesoare• n->infinity,=>S~1/seq.• Limitasuperioaraaaccelerariiestelimitatadefrac=apar=isecven=ale.
• Nusefaceanalizainfunc7ededimensiuneaproblemei!.
Curs11-PPD
12
Prezentarealterna=va
Curs11-PPD
13
LegealuiGustafson• Consideracaatuncicanddimensiuneaproblemeicresteparteaserialase
micsoreazainprocent:
• m=dimensiuneaproblemei,n=#procesoare,Considerandcaprogramulparalelseexecutaintr-ounitatede4mp:
Tp=seq(m)+par(m)=1par(m)=1–seq(m),(Ts=seq(m)+n*par(m))Atuncispeedup=Ts/Tp=seq(m)+n*par(m)
speedup=seq(m)+n(1–seq(m))
Dacaseq(m)->0atuncicandn->∞->seob4ne~accelerareliniara.
Curs11-PPD
14
LegealuiGustafson–op=mistaLegealuiAmdahl-pesimista
• Presupunecaparteaseriala(costulei)ramaneconstant–nucresteodatacucrestereaproblemei.
• LegealuiAmdahlpresupuneodimensiunefixaaproblemeksicapartea
secven=alanudepindedenumaruldeprocesoare.
Curs11-PPD
15
Exemple
• Adunareaannumere
• Dacan=puterealui2=>T_p=logn
Curs11-PPD
16
Adunare–lognpasi
n=16;p=16s..Curs11-PPD
17
Exemplu(con=nuare)
=>• t_C=+mpptoopera+edeadunare• T_com=ts+tw,ptoopera4edecomunica4e(perword)
– suntO(n)opera=idecomunica=edarsiopera=iledecomunica=esepotexecutasimultanT_com=Θ(logn)
TP=Θ(logn)
• S=mcaTS=Θ(n)
• SpeedupS=Θ(n/logn)
Curs11-PPD
18
Accelerare–superliniara?
• S=0(theparallelprogramneverterminates).
• S<p(teore=c)– Incazcontrarunprocesorarfiimplicatincalculepentrurezolvarea
problemeiun=mpT<TS/p.
– Secontrazicepresupunereacasefolosestecelmairapidprogramserial(inevaluareaccelerare).
Curs11-PPD
19
SuperlinearSpeedups
Cautareintr-unarborenestructurat.
Curs11-PPD
20
Exemplu
Problema:edge-detection in images. Se aplica modificari pe celule de 3 x 3 pixeli. Daca o operatie aritmetica necesita tc, timpul serial pt o imagine de n x n este TS= tc n2.
Curs11-PPD
21
• Par==onareveri=cala=>n2/ppixels.
• Margineafiecaruisegment=>2npixels.• Nrdevaloricaretrebuiecomunicate=2n=>2(ts+twn).
TSp=9tcn2/p.
Curs11-PPD
22
Evaluaremetrici
• Timpulparalel:
• Accelerareasieficienta:
Curs11-PPD
Costul
• Costulsedefinestecafiindprodusuldintre=mpuldeexecu=esinumarulmaximdeprocesoarecaresefolosesc.
Cp(n)=tp(n)·p
• Aceastadefini=eestejus=ficatadefaptulcaoriceaplica=eparalelapoatefi
simulatapeunsistemsecven=al,situa=eincareuniculprocesorvaexecutaprogramulintr-un=mpegalcuO(Cp(n)).
• Oaplica=eparalelaesteop4madinpunctdevederealcostului,dacavaloareaacestuiaesteegala,sauestedeacelasiordindemarimecu=mpulceleimaibunevariantesecven=ale;
• aplica=aesteeficientadinpunctdevederealcostuluidacaCp=O(t1logp).
23Curs11-PPD
24
Costulunuisistemparalel(algoritm+sistem)
• Cost=pxTP
• Costulreflectasuma=mpuluipecarefiecareprocesorilpetreceinrezolvareaproblemei.
• Unsistemparalelsenumesteop=maldacacostulrezolvariiuneiproblemepeuncalculatorparalelesteasimptop=cegalcucostulserial.
• E=TS/pTP=>pentrusistemecostop=mal=>E=O(1).
• Cost~work~processor-7meproduct.
Curs11-PPD
“Work”
• volumuldelucru(“work”)–W,definitdenumarultotaldeopera=iexecutatedecatreprocesoareleac=ve.
• Putemvedeaacestvolumdelucrucasiintegralaprofiluluideparalelismalprogramului–adicanumaruldeproceseac=vecaofunc=ede=mp.
• Volumuldelucrupoatefievaluatsicafiindprodusuldintredimensiuneaproblemeinsinumarulmediudeopera=icaresefacasuprauneidatedeintrarec:W=n*c.
25Curs11-PPD
26
Exemplu
Adunarennumere.• TP=logn(ptp=n).
• C=pTP=nlogn.
• Ts=Θ(n)=>nuestecostop=mal.
Curs11-PPD
27
AnalizadeImpactptcostConsideramsortareaannumerefolosindnprocesoareintr-un=mp(logn)2.
• Daca=mpulserialestenlognatunciS=n/lognE=1/logn• C=pTP=n(logn)2.• Nuecostop=mal.• ?Transformare?
• Fiep<n,seatribuiecelentask-uriparalelelapprocesoaresirezultaTP=n(logn)2/p.• C=n(logn)2-nueop=m
• S=p/logn.
Dacancresteaccelerareascadedacasefolosesteacelasip!
Curs11-PPD
Scalabilitate
• Unprogrampoatescalaa.i.safoloseascamaimulteprocesoare.– Adica???
• Cumseevalueazascalabilitatea?• Cumseevalueazabenefiileadusedescalabiltate?• Evaluarecomra=va:
– Dacasedubleazanrdeprocesoarelaceartrebuisaneasteptam?– Estescalabilitatealiniara?
• Evaluareaeficienteicorespunzatoare– Sepastreazaeficientapemasuracecrestedimensiuneaproblemei?
Defini=egeneralaScalabilitateaplica+e:abilitateaunuiprogramparalelsaob+naocresteredeperformantapropor+onalcunumaruldeprocesoaresidimensiuneaproblemei.
28Curs 11 - PPD
Scalabilitate • Scalabilitatea masoara modul ın care se schimba performanta unui anumit
algoritm ın cazul ın care sunt folosite mai multe elemente de procesare. • Un indicator important pentru aceasta este numarul maxim de procesoare
care pot fi folosite pentru rezolvarea unei probleme. • In cazul folosirii unui numar mic de procesoare, un program paralel se poate
executa mult mai incet decat un program secvential. – Diferenta poate fi atribuita comunicatiilor si sincronizariilor care nu apar
ın cazul unui program secvential. (Overhead) • Numarul minim de componente pentru o anumita partitionare, poate fi de
asemenea un indicator important.
Curs 11 - PPD 29
30
Scalabilitate
• Scalabilitateaunuisistemparalelesteomasuraacapacita7idealivraoaccelerarecuocrestereliniarainfunc7edenumaruldeprocesoarefolosite.
• Analizascalabilita=isefacepentruunsistem(arhitectura+algoritm).
• Eviden7azacumseextrapoleazaperformantapentruproblemesisistememici =>laproblemesiconfigura7imaimari.
• Metricipentruscalabilitate–– func=adeisoeficienta(isoefficiency)– eficientaIsospeed–efficiency– Frac=aseriala/SerialFrac=onf
Curs11-PPD
31
Scalabilitateasistemelorparalele
Considerthreeparallelalgorithmsforcompu=ngann-pointFastFourierTransform(FFT)on64processingelements.
Acomparisonofthespeedupsobtainedbythebinary-exchange,2-Dtransposeand3-D
transposealgorithmson64processingelementswithtc=2,tw=4,ts=25,andth=2.• Estedificilsasaevaluezecaracteris=ciledescalareprinobserva=ipedatemicisipe
masinimici.
Curs11-PPD
Granularitate
• Granularitatea(“grain size”) este un parametru calitativ care caracterizeaza atat – sistemele paralele cat si – aplicatiile paralele.
• Granularitatea aplicatiei se defineste ca dimensiunea minima a unei unitati secventiale dintr-un program, exprimata ın numar de instructiuni.
– Prin unitate secventiala se ıntelege o parte programın care nu au loc operatii de sincronizare sau comunicare cu alte procese.
• Fiecare flux de instructiuni are o anumita granularitate. • Granularitatea aplicatiei se defineste ca valoarea minima a granularitatii pentru
activitatile paralele ale componentelor(proces, thread, task). • Granularitatea unui algoritm poate fi aproximata ca fiind raportul dintre timpul total
calcul si timpul total de comunicare.
Curs 11 - PPD 32
Granularitatea sistemului
• Pentru un sistem dat, exista o valoare minima a granularitatii aplicatiei, sub care performanta scade semnificativ. Aceasta valoare de prag este cunoscuta ca si granularitatea sistemului respectiv.
– Justificarea consta ın faptul ca timpul de overhead (comunicatii, sincronizari, etc.) devine comparabil cu timpul de calcul paralel.
• De dorit => un calculator paralel sa aiba o granularitate mica, astfel ıncat sa poata executa eficient o gama larga de programe. ⇒ programele paralele sa fie caracterizate de o granularitate mare, astfel ıncat sa
poata fi executate eficient de o diversitate de sisteme.
• Exceptii: clase de aplicatii cu o valoare a granularitatii foarte mica, dar care se executa cu succes pe arhitecturi specifice.
– aplicatiile sistolice, in care in general o operatie este urmata de o comunicatie. • aceste aplicatii impun insa o structura a comunicatiilor foarte regulata si
comunicatii doar intre noduri vecine
Curs 11 - PPD 33
34
Granularitate…cont.
• Fine-grainParallelism:– Rela7velysmallamountsofcomputa7onalworkaredonebetweencommunica7onevents– Lowcomputa7ontocommunica7onra7o– Facilitatesloadbalancing– Implieshighcommunica7onoverheadandlessopportunityfor
performanceenhancement– Ifgranularityistoofineitispossiblethattheoverheadrequiredforcommunica7onsandsynchroniza7onbetweentaskstakeslongerthanthecomputa7on.
• Coarse-grainParallelism:– Rela7velylargeamountsofcomputa7onalworkaredonebetweencommunica7on/synchroniza7onevents– Highcomputa7ontocommunica7onra7o– Impliesmoreopportunityforperformanceincrease– Hardertoloadbalanceefficiently
Curs 11 - PPD
35
Granularitate <-> descompunere in taskuri
• Numarul de task-uri in care o problema se descompune determina granularitatea.
• numar mare => fine-grained • numar mic => coarse grained decomposition
Exemplu:inmul=rematrice
Curs 11 - PPD
36
Granulariteadecompuneriitaskurilor
• Granularitateaestedeterminatadenumaruldetaskuricaresecreeazaptoproblema.
• Maimultetaskuri=>granularitatemaimica
Curs11-PPD
37
Efectulgranularita=iasupraperformantei
• Demulteorifolosireaamaipu=neprocesoareimbunatatesteperformatasistemuluiparalel.
• Folosindmaipu=neprocesoaredecatnumarulmaximposibilsenumestescalingdown(foraparallelsystem).
• Modalitateanaivadescalareestedeaconsiderafiecareelementdeprocesareini=aafiunulvirtualsisaseatribuiefiecareprocesorvirtualunuiareal(fizic).
• Dacanumaruldeprocesoarescadecuunfactorn/p,calcululefectualdecatrefiecareprocesorvacrestecuacelasifactor.
• Costulcomunica=einucrestepentrucacomunica=aintreuneleprocesoarevirtualesevafaceincadrulaceluiasiprocesor(real).
Curs11-PPD
38
Exemplu
• Adunarennumerecupprocesoare(ambelesuntputerialelui2)• Fiecaruiprocesordintrecelepiisuntatribuiten/pprocesoarevirtuale.
• Primiilogn-logpdinceilognpasiaialgoritmuluioriginalsesimuleazafolosindpprocesoareinΘ((n/p)(logn-logp))=Θ((n/p)log(n/p))
• Urmatoriilogppasinunecesitanicipar77onare(pnoduri–pprocesoare)
• T_p=Θ( (n/p)log(n/p)+logp)• C=O(nlogn),• T_s=Θ(n)=>Sistemulparalelnuestecostop=mal.
Curs11-PPD
39
Varianta2
Fiecareprocesorprimesten/pnumerepecareleadunaindependent.• Celepsumepar7alepotfiadunatein7mpuldeΘ(n/p).
=>programcostop=mal.
Curs11-PPD
40
Crestereagranularita=i…
• daca• atuncisistemulestecost-op=mal
Curs11-PPD
Important– alegenumaruldeprocesea.i.safieeficientcalculul!
Gradul de paralelism (DOP)
• DOP al unui algoritm este dat de numarul de operatii care pot fi executate simultan. • Similar cu granulatia sistemelor paralele
– fina–numar mare de procesoare, – medie, – bruta–numar mic de procesoare se poate defini similar si DOP unui algoritm.
Curs 11 - PPD 41
DOP
• GraduldeparalelismDOP(„degreeofparallelism”)=– (alunuiprogram)
• numaruldeprocesecareseexecutainparalelintr-unanumitintervalde=mp.• Numaruldeopera=icareseexecutainparalelintr-unanumitintervalde=mp
– (alunuisistem)• numarul de procesoare care pot fi in execu=e in paralel intr-un anumit
intervalde=mp
• Profilulparalelismului=graficulDOPinfunc=ede=mp(pentruunanumitprogram).
Depindede:-structuraalgoritmului;-op=mizareaprogramului;-u=lizarearesurselor;-condi=ilederulare.
Curs11-PPD 42
Inconcluzie:
-accelerareaindicacas=guldevitezadecalculintr-unsistemparalel;
-eficientamasoaraparteau=laaprelucrarii(lucrului)efectuatedenprocesoare;
-redundantamasoaradimensiuneacresteriiincarcariidelucru;
-u=lizareaindicagraduldeu=lizarearesurselorin=mpulcalcululuiparalel;
-calitatea combina efectele accelerarii, eficientei si redundantei intr-o singuraexpresiepentruaeviden=ameritulcalculuiparalel.
Curs11-PPD 43
Curs11-PPD 44
Referinte:AnanthGrama,AnshulGupta,GeorgeKarypis,andVipinKumar``Introduc=ontoParallelCompu=ng'',
