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 .....