Proiectarea Unui Algoritm Paralel
-
Upload
ayrin-iris -
Category
Documents
-
view
222 -
download
0
Transcript of Proiectarea Unui Algoritm Paralel
7/23/2019 Proiectarea Unui Algoritm Paralel
http://slidepdf.com/reader/full/proiectarea-unui-algoritm-paralel 1/6
Proiectarea unui algoritm paralel
Una dintre cele mai importante trăsături ale unui algoritm paraleleste divizarea problemei în subprobleme care pot fi distribuite pemai multe taskuri. Pentru proiectarea unuialgoritm paralel se pot
considera o serie de abordări. Prima ar fi paralelizareaunui algoritm secvențial deja existent. Pentru aceasta va trebui săse determine paralelismul care apare în mod natural în cadrulunui algoritm secvențial . Uneori, se preferă găsirea unei soluțiidiferite de cea oferită de algoritmul secvențial ceea ce presupuneo regândire a întregului algoritm. Indiferent de modul de abordare
în cadrul unui algoritm paralel nu se pot ignora o serie deconsiderații importante. Una din acestea este costul de
comunicație între procese. acă la un algoritm secvențial costulsau complexitatea este exprimată în spațiu !mărimea memorieiocupate" și timp !numărul de cicli de ceas" necesar pentru aexecuta un program, la cel paralel trebuie luat în considerare șimodul în care se comunică între procese.
Problema comunicației
#xistă unii algoritmi de calcul paralel care nu au nevoie de
comunicare între procese. $pre exemplu dacă ne imaginăm unalgoritm paralel care face conversia unei imagini color în una albnegru. atele din acea imagine pot fi distribuite pe mai multetaskuri independente. %cest tip de probleme sunt denumite&embarrassingl' parallel& ()* !paralelism jenant" deoarececomunicarea între taskuri este foarte redusă. +ei mai mulțialgoritmi paraleli sunt algoritmi complecși în care comunicația
între procese are o importanță majoră. +omplexitatea algoritmilor
paraleli este calculată în funcție de memoria folosită și timp. #itrebuie să mai optimizeze folosirea unei alte resurse,comunicarea între proceseprocesoare. $unt două modalități princare proceseleprocesoarele comunică- emorie partajată sau/olosind mesaje. odelul cu memorie partajată se referă laprogramarea într0un mediu multiprocesor pentru carecomunicația între procese se realizează prin intermediul uneimemorii comune. odelul cu transfer de mesaje este adecvat
implementării unui algoritm paralel într0o rețea de calculatoare.
7/23/2019 Proiectarea Unui Algoritm Paralel
http://slidepdf.com/reader/full/proiectarea-unui-algoritm-paralel 2/6
Pentru ca un program să poată fi executat în paralel acestatrebuie descompus într0o serie de procese. %ceastadescompunere presupune partiționarea algoritmului și alocareaproceselor. Partiționarea reprezintă specificarea setului de taskuri
care implementează algoritmul în modul cel mai eficient pe omașină de calcul paralel. %locarea reprezintă modul de distribuirea task0urilor procesoarelor.
Partiționarea problemei
Performanța unui algoritm de calcul paralel depinde de granularitate.Aceasta se referă la mărimea task-ului în comparație cu timpul necesarcomunicației și sincronizării datelor. Dacă timpul necesar comunicației
și sincronizării este mai mare decât timpul de execuție al task-uluiatunci granularitatea este mică. O soluție este partiționarea programuluiîn taskuri de dimensiuni mai mari cu o granularitate grosieră.Dezavantajul acestei metode este reducerea gradului de paralelism.m!unătățirea performanțelor unui algoritm de calcul paralel se face prin găsirea unui compromis între mărimea task-ului și consumulsuplimentar de resurse. De o!icei este găsită o corelare între numărul detaskuri" dimensiunea acestora și menținerea la minimu necesar a
consumului suplimentar de resurse. #ea mai !ună granularitate este ceao!ținută prin adaptarea algoritmului pe platforma 1ard2are pe carerulează. n majoritatea cazurilor over1ead-ul asociat comunicațiilor șisincronizării este mare în comparație cu timpul de execuție caz în carese preferă o granularitate grosieră. Partiționarea unui algoritm se poateface în două moduri$
).$tatică- Partiționarea se face înainte de execuție. %vantajul
acestei metode este acela că necesită un volum redus decomunicații. Pe de altă parte metoda aceasta prezintădezavantajul ca gradul de paralelism să fie dat de datele deintrare.
3.inamică- 4enerarea task0urilor este făcută în timpul deexecuție al programului. %vantajul acestei metode este datde menținerea procesoarelor ocupate cu prețul creșteriivolumului comunicației dintre procese.
7/23/2019 Proiectarea Unui Algoritm Paralel
http://slidepdf.com/reader/full/proiectarea-unui-algoritm-paralel 3/6
Alocarea
%locarea reprezintă distribuirea de taskuri procesoarelor.Planificarea ca și în cazul partiționării poate fi statică saudinamică. 5n cazul alocării statice sarcinile și ordinea de execuție
sunt cunoscute înainte de execuție. Algoritmii de calculparalel ce folosesc planificarea statică necesită un volum mic decomunicare între procese potrivită pentru cazurile când costurilede comunicație este mare. 5n cazul planificării dinamice alocareasarcinilor este făcută la rulare. %ceastă te1nică permitedistribuirea uniformă a încărcării procesoarelor și oferă flexibilitate
în utilizarea unui număr mare de procesoare. %stfel dacăun procesor termină mai repede task0ul alocat i se poate atribui
un alt task mărind în acest mod eficiența algoritmului.ezavantaje-
• volumul de &over1ead& este mare• modul de execuție este greu de urmărit• analiza performanțelor devine dificilă, ca urmare a alocării
task0urilor în timpul rulării.•
Limitele programării paralele
+onform legii lui %mda1l accelerarea unui program este dată de
următoarea formulă- , unde P reprezintă por țiuneadin cod care poate fi paralelizată. acă nici o por țiune aprogramului nu poate fi paralelizată atunci accelerarea este )
!algoritm secvențial". aca P6) !tot codul poate fi paralelizat",atunci accelerarea este infinită !cel puțin teoretic". acă luam înconsiderare că un algoritm paralel rulează pe mai multe
procesoare obținem următoarea formulă- , unde Preprezintă partea din algoritm care poate fi paralelizată, 7reprezintă numărul de procesoare și $ partea care nu a fostparalelizată.+u toate că un algoritm paralel are limitele sale
conform celei de0a doua formule putem concluziona că aceștia
7/23/2019 Proiectarea Unui Algoritm Paralel
http://slidepdf.com/reader/full/proiectarea-unui-algoritm-paralel 4/6
sunt foarte eficienți în rezolvarea problemelor de dimensiuni mari, în care partea secvențială rămâne nesc1imbată.
Factorii ce afectează performanța algoritmilor paraleli
•
5ncărcarea neec1ilibrată a porcesoarelor-).Imposibilitatea împăr țirii in taskuri perfect egale3.8ariația gradului de paralelism în cadrul algoritmului
• +alculele suplimentare ce apar în cazul în care cel mairapid algoritm secvențial nu poate fi paralelizat și se alege unalgoritm paralel greoi, dar paralelizabil
• +omunicația între procese• +oncurența la setul de date partajate
Biblioteca mpich2
%essage Passing &nterface
%P& este un protocol de comunicatie folosit pentru programarea paralela menit sa ofere functionalitate pentru sincronizarea sicomunicarea intre procese intr-un mod independent de lim!aj si de platforma ' exista implementari ale %P& pentru aproape orice platforma (. Programele %P& sunt orientate catre procese" asadar pentru o!tinerea de performante maxime tre!uiesc definite pe fiecarecomputer atatea procese cate procesoare exista ' sau core-uri (.
%P&#)* e o implementare free" open-source a %P&-*. #ele maiimportante componente ale %P&#) suntmpd ' multi-purpose daemon ( si mpiexec. %pd are rolul de managerin ceea ce priveste comunicarea si sincronizarea intre procese" iarmpiexec are rolul de a lansa in executie aplicatiile %P&.
+intaxa mpiexec$#el mai comun mod de utilizare al mpiexec este $
mpiexec ,n numar procese /-0ost 0ost1 aplicatie /$ -n numar procese -0ost 0ost aplicatie1
7/23/2019 Proiectarea Unui Algoritm Paralel
http://slidepdf.com/reader/full/proiectarea-unui-algoritm-paralel 5/6
%otive pentru utilizarea %P&$+tandardizare - %P& este singurul mesaj !i!lioteca trecerea care poate ficonsiderat un standard. 2l este sprijinit pe aproape toate platformele de)P#. Practic" le-a înlocuit toate !i!liotecile trecători mesajul anterior.
Porta!ilitate - 2xistă puține sau nici o nevoie de a modifica codul sursăatunci când portarea aplicațiilor la o platformă diferită care acceptă 'și
este compati!il cu( standardul %P&.Oportunități de performanță - implementări furnizor ar tre!ui să poatăsă exploateze caracteristicile 0ard3are native pentru a optimiza performanta.
4uncționalitate - 2xistă peste 556 de rutine definite în %P&-7" careinclude cea mai mare parte a celor de la %P&-* și %P&-8.
Disponi!ilitate - O varietate de implementari sunt disponi!ile" atâtvânzător și domeniul pu!lic.
Biblioteca OMP
Open%P $ AP& 'Application Program &nterface( utilizat pentru a controlaexplicit paralelismul cu memorie partajata si fire multiple de executie.
#omponente$-directive compilator9-functii runtime de !i!lioteca9-varia!ile de mediu.
Open%P este disponi!il pentru #:#;; si 4ortran. 2xista implementari pe o multitudine de platforme" inclusiv <nix si =indo3s.
Model de programare
7/23/2019 Proiectarea Unui Algoritm Paralel
http://slidepdf.com/reader/full/proiectarea-unui-algoritm-paralel 6/6
Open%P$ memorie partajata si fire multiple de executie.
- model de programare explicit 'nu automat( > programatorulare un control deplin asupra paralelismului.
modelul fork-join de executie paralela
Program Open%P incepe cu un proces singular 't0read master( -secvential - constructie de regiune paralela '4O?@( - mai multet0read-uri in paralel - O&B - t0read-ul master" etc.
Bumarul de t0read-uri $ se poate modifica dinamic. +tructura unui program Open%P $ #include <opm.h>
void main ( )
{
int var1, var2, var3
..... cod !ecvential .....
""incepe !ectiunea paralela > $%&'
#prama omp parallel private (var1, var2) !hared (var3)
{
..... !ectiune paralela eecutata de toate thread-urile .....
""toate thread-urile > *%+ > thread ma!ter
..... reia cod !ecvential .....