Indrumar Laborator ALCP

7/21/2019 Indrumar Laborator ALCP

1/163

MiticCraus Cristian-Mihai AmarandeiBogdan Romanescu

ALGORITMI I LIMBAJEPENTRU CALCULUL PARALEL

Indrumar de laborator

Iai 2005


2/163

2

Partea I : Algoritmi paraleli

Primitive ale calculului paralel..............................................................9Comprimarea (Reducerea) ...............................................................9Calculul Prefixelor (Scan) ...............................................................11Dublarea (scurtcircuitarea) ............................................................13

Comunicri colective ............................................................................15Difuzarea unu-la-toi .......................................................................15Comunicarea personalizatunu-la-toi (scatter) ..........................20Difuzarea toi-la-toi ........................................................................22Comunicarea personalizattoi-la-toi ..........................................26

Sortarea paralel ..................................................................................29Sortarea paralelbazata pe metoda numrrii ............................29Sortarea par-impar (Odd-Even-Sort)............................................31Sortarea prin interclasarea de secvene bitone .............................32Sortarea rapidpe hipercub...........................................................37

Calcul matricial ....................................................................................38

Transpunerea unei matrice.............................................................38Inmulirea a doumatrici ...............................................................40Sisteme de ecuatii..................................................................................44Drumuri optime n grafuri ..................................................................47

Comentarii bibliografice .................................................................53

Partea a-II-a : Introducere in MPI

Standardul MPI ....................................................................................57Modelul de execuie ..............................................................................58Tipuri de date n MPI ..........................................................................59

Comunicarea ntre procese ..................................................................60Comunicri unu-la-unu blocante ...................................................60Comunicri unu-la-unu neblocante ...............................................64

Comunicri colective ............................................................................69Bariera ..............................................................................................70Difuzia (Broadcast) ..........................................................................70Comunicarea personalizatunu-la-toi (Scatter) .........................72Comunicarea toi-la-unu - Colectarea datelor (Gather) ..............73Operaii de reducere........................................................................76Calculul prefixelor ...........................................................................81Corectitudinea operaiilor colective ...............................................82

Tipuri de date definite de utilizator ...............................................86


3/163

3

Constructori pentru tipuri de date.................................................87Utilizarea tipurilor de date derivate ..............................................92Lungimea mesajelor ........................................................................93

Topologii pentru procese .....................................................................94Topologii virtuale.............................................................................95Instructiuni de instalare, compilare i execuie a aplicaiilor care

folosesc biblioteca MPI..................................................................103

Partea a-III-a : Exemple de programe MPI 109

Bibliografie .....................................................................................163


4/163

4


5/163

5

Prefa

Intenia autorilor acestei lucrri a fost de a oferi studenilor de laFacultatea de Automatic si Calculatoare ansamblul de informaiinecesare realizrii lucrrilor de laborator aferente disciplineiAlgoritmi i Limbaje de Calcul Paralel. Lucrarea se adreseaznstuturor celor care doresc iniierea n calculul paralel.

Atunci cnd au fost selectate temele abordate s-a considerat cestecunoscut coninutul cursului Algoritmi i Limbaje de Calcul paralel

sau al crii Algoritmi pentru prelucrri paralale, Editura Gh.Asachi, Iai, 2002 , autor MiticCraus.Autorii mulumesc studenilor masteranzi Raluca Macovei,

Roxana Ungureanu i Ionu Vasiliu, pentru contribuia lor larealizarea seciunii Comunicri colective .


6/163

6


7/163

7

PARTEA I

ALGORITMI PARALELI

Autor: MiticCraus


8/163

8


9/163

9

Primitive ale calculului paralel

-Comprimarea (reducerea)-Calculul prefixelor (scan)-Dublarea (scurtcircuitarea)

Comprimarea (Reducerea)Fie M o mulime de n = 2m elemente, M = {ai | i = 1,...,n} Mr.

Mulimea M urmeaza fi procesatpentru a calcula valoarea a1...anunde este o lege de compoziie asociativdefinitpe Mr. Mulimea dereferinMrpoate fi R iar poate fi +,min,max, etc.

Pentru simplitate se presupune c datele de intrare sunt iniialmemorate ntr-un tablou unidimensional A[0..n-1] iar n este de forma n= 2d.

Algoritm recursiv de comprimareproccomprim_rec (A,l,l+m-1)begin

if (m < 2) thenreturnA[l]

elsereturncomprim_rec(A,l,l+m/2-1)

comprim_rec(A,l+m/2,l+m-1))end

Algoritm iterativ de comprimare

Iniial cele n elemente a1, a2,...,ansunt memorate n locaiileA[n], A[n+1],...,A[2n-1] ale unui tablou de dimensiune 2n.

procsum(A,)begin

fork = m-1 down to0 dofor allj:2kj 2k+1-1 par do A[j]=A[2j]A[2j+1];

end


10/163

10

Exemplu de comprimare

ComplexitateaLa terminarea execuiei algoritmului A[1] = a1...an.Complexitatea timp paralel a algoritmului de comprimare

(implementat pe o mainCREW-PRAM sau pe o ahitecturVLSI detip arbore binar) este O(logn). Aceasta deoarece adncimea arborelui decalcul este logn.

Numrul procesoarelor utilizate este p n/2.

Reducerea numrului de procesoareSe poate observa cn fiecare pas l, l = 0,...,m-1, sunt active [n/( 2l)]

procesoare. Aceasta sugereaz faptul ca este posibil reducereanumrului de procesoare fr a afecta complexitatea algoritmului.Presupunnd ca p < n/2, se partiionez mulimea celor n elementea1,...,an n p submulimi astfel: primele p-1 submultimi contin k =

n/pelemente, iar ultima conine n-(p-1)n/p (

n/p) elemente. Fiecreisubmulimi i se asociaz un procesor. Procesorul asociat uneisubmulimi S = {ai1,...,aik} rezolv problema determinrii valoriiai1...aik n

n/p-1 uniti de timp. Acionnd n paralel, cele pprocesoare reduc problema iniial la o problem similar dedimensiune p, n n/p-1 uniti de timp.

In continuare, aplicnd comprimarea asupra problemei rezultate, seobine rezultatul final n logp uniti de timp. Rezultun timp total de


11/163

11

n/p-1+logp uniti de timp. Dac p = [n/ logn] atunci n/p-1+logp

2logn-1-loglogn O(logn).

Calculul Prefixelor (Scan)

Tehnica calculrii prefixelor dezvolt tehnica comprimrii recursive

n care parcurgerea arborelui asociat execuiei se face dinspre frunzespre rdcin. Algoritmii de calcul a prefixelor parcurg arborele nambele sensuri.

Utiliznd notaiile anterioare, calculul prefixelor const ndeterminarea valorilora1, a1a2, , a1...an undeeste o operaiebinar asociativ. Se presupune c datele de intrare sunt iniialmemorate ntr-un tablou unidimensional A[0..2n-1] (A[n+i]=ai) iar neste de forma n = 2d.

Algoritmi de calcul al prefixelor

Operaia admite element simetricproccalcul_prefixe(A,B,)begin

fork = m-1 down to 0 dofor allj:2kj 2k+1-1 par do A[j]=A[2j]A[2j+1];

B[1]= A[1];fork = 1 tom do

for allj:2kj 2k+1-1 par doifbit0(j) = 1 then

B[j]=B[[(j-1)/2]];else

B[j]=B[j/2](-A[j+1]);End

Complexitatea

In final, valorile A[n]...A[n+j], j = 0,...,n-1 vor fi memorate nlocaiile B[n+j] ale tabloului B[1..2n-1].

Timpul de execuie este de O(logn).Numrul procesoarelor utilizate este O(n).Reducerea numrului procesoarelor se poate face printr-o tehnic

asemntoare celei descrise la reducere.


12/163

12

Exemplu

Operaia nu admite element simetric

proccalcul_prefixe_gen(A,B,)begin

fork = m-1 down to 0 dofor allj:2kj 2k+1-1 par do A[j]=A[2j]A[2j+1];fork = 0 tom do

for allj:2kj 2k+1-1 par doifj = 2kthen

B[j]=A[j]else

ifbit0(j) = 1 thenB[j]=B[[(j-1)/2]]

elseB[j]=B[[(j-2)/2]]A[j]);

end


13/163

13

ComplexitateaTimpul de execuie = O(logn)Numrul de procesoare = O([n/logn])

Aplicaii ale operaiei scan la recurene

Fie recurena Xk= Xk-1A[k], k > 1, X1= A[1]Daceste un operator binar asociativ atunciXk= A[1] A[2] ... A[k]Astfel, recurene simple pot fi rezolvate cu algoritmi paraleli pentru

calculul prefixelor.

Dublarea (scurtcircuitarea)Fie L o list simplu nlnuit format din n elemente. Fiecare

element k L are asociat un numar val[k] i un pointer p[k]. Sepresupune cfiecrui element k L i este asignat un procesor Pk.

Algoritm de scurtcircuitare

proc scurtcircuitare(L,value,)begin

repeat logn timesfor all k:k L par do

ifp[k] p[p[k]] thenval[k] = val[k]val[p[k]];

p[k] = p[p[k]]endObs: este o operaie binaroarecare.

ComplexitateaComplexitatea timp a algoritmului de scurtcircuitare (implementat pe

o mainCREW-PRAM) este O(logn).


14/163


15/163

15

Comunicri colectiveComunicrile colective pot fi clasificate astfel:

-unu-la-toi: difuzare comunicare personalizat

-toi-la-toi difuzare comunicare personalizat

-toi-la-unu

Difuzarea unu-la-toiUn procesor trimite acelai mesaj M la toi ceilali:

Difuzarea unu-la-toi pe un inel

Procesoarele sunt numerotate de la 0 la p. Procesorul 0 este emitentulmesajului M de lungime m, unde m este numrul componentelor

atomice (cuvinte) ale mesajului. Fiecare pas de transmisie este ilustratprintr-o sgeat de la surs la destinaie, punctat i numerotat.Numrul semnific pasul n care este transmis mesajul. Sursa trimitemesajul celor 2 vecini ai si n pai diferii. Fiecare procesor primete unmesaj de la unul din vecinii si i l trimite mai departe la cellalt vecin.Procesul continu s fie activ pncnd toate procesoarele au primit ocopie a mesajului. Pentru o reea de tip inel cu p procesoare, difuzia va fifinalizatn [p/2] pai. Timpul de difuzie este dat de relaia:

Tone_to_all =( ts+twm ) p/2


16/163

16

unde ts este timpul necesar iniializrii unui transfer iar tw este timpulnecesar transferului unei componente atomice a mesajului M de la unnod la unul din vecinii si.

Difuzarea unu-la-toi pe o plastoroidalConsiderm problema difuziei unu-la-toi pe o plasa toroidal cu

p liniii si p coloane. Procesoarele sunt numerotate de la 0 la p.

Procesorul 0 este emitentul mesajului. In prima fazde comunicare esteexecutato difuzie de la surs la cele ( p -1) procesoare de pe aceeai

linie. Dup ce toate procesoarele de pe linie au primit mesajul, esteiniiat o difuzie unu-la-toi pe coloana corespunztoare. La sfritulfazei a doua, fiecare procesor din plas conine o copie a mesajuluiiniial. Paii de comunicare sunt prezentai n figura de mai jos, undeprocesorul 0 este sursa. Paii 1 i 2 corespund primei faze, iar paii 3 i 4corespund celei de-a doua faze.

Dac dimensiunea mesajului este m, difuzia unu-la-toi pe liniedureaz (ts+twm)[ p /2] (timpul necesar unei difuzii unu-la-toi pe un

inel cu p procesoare). n a doua faz, difuzia unu-la-toi pe coloane sedesfoarn paralel, iar timpul de transmisie este egal cu cel din primafaz. Timpul total de difuzie este:

Tone_to_all =2( ts+twm ) [ p /2]

Putem folosi o procedursimilarpentru difuzia unu-la-toi pe o plastridimensional. In acest caz, liniile de p1/3procesoare care corespund lacele 3 dimensiuni ale plasei sunt tratate ca inele. Aplicnd procedurapentru inel n trei faze, cte una pentru fiecare dimensiune, timpul dedifuzie unu-la-toi este:

Tone_to_all =3( ts+twm ) [ p /2]


17/163

17

Difuzarea unu-la-toi pe hipercub

Figura de mai jos exemplificdifuzia unu-la-toi pe un hipercub cu 8procesoare, procesorul 0 fiind sursa mesajului.

Aa cum se poate observa din figur, procesul are 3 faze de comunicare.Se poate de asemenea observa cordinea n care sunt alese dimensiunilepentru comunicare nu afecteazrezultatul. In planificarea ce corespundefigurii, comunicarea ncepe de-a lungul celei mai mari dimensiuni ( cecorespunde bitului cel mai semnificativ al reprezentrii binare a eticheteiunui procesor) i continu de-a lungul dimensiunilor mai mici, n paiconsecutivi.

Algoritm de difuzare unu-la-toi pe un cub d-dimensionalIn algoritmul prezentat mai jos se consider nodul 0 ca surs a

mesajului M difuzat. Procedura se execut n paralel pe toateprocesoarele. Fiecare procesor i cunoate propriul identificator my_id.


18/163

18

Procedura execut p pai de comunicare, unul pe fiecare dimensiune ahipercubului. Comunicarea se desfoar de la dimensiunea cea maimare spre cea mai mic (desi aceasta ordine nu conteaz). Indicele i albuclei indicdimensiunea curentpe care are loc comunicarea. Numaiprocesoarele ce au valoarea 0 pe cei mai puin semnificativi i biiparticip la comunicarea pe dimensiunea i. De exemplu, pentru

hipercubul tridimensional din figura anterioari are valoarea 2 n primafaz. De aceea numai procesoarele 0 si 4 comunic, avnd cei mai puinsemnificativi 2 biti 0. In faza urmtoare, cnd i = 1 toate procesoarele cuultimul bit 0 (0, 2, 4, 6) participla comunicare.

Variabila mask este folositpentru determinarea procesoarelor ce iauparte la comunicare ntr-o iteraie. Variabila mask are d(=log p) cifrebinare care iniial sunt toate 1. La nceputul fiecarei iteraii, cel maisemnificativ bit diferit de 0 este resetat la 0. Apoi se determinprocesoarele ce vor participa n acest pas la comunicare. De exemplu,pentru hipercubul din figura anterioar, mask are iniial valoarea 111 iva deveni 011 n timpul iteraiei corespunztoare lui i = 2.

Dintre procesoarele alese pentru comunicare de-a lungul dimensiuniii, procesoarele cu bitul i =0 trimit mesajul, iar cele cu bitul i=1 primescmesajul.

Algoritmul se termin dup ce comunicarea s-a desfurat pe toatedimensiunile.

proc ONE_TO_ALL_BC(d, my_id, M)begin

mask =2d-1; /*Toate cele d cifre binare ale matii mask devin 1*/ for i = d-1 downto 0 do

mask = mask XOR 2i; /* Bitul i din mask devine 0 */if (my_id AND mask)=0 then

/* Dacultimele i cifre binare din my_id sunt 0 */if (my_id AND 2i)=0 then

msg_destination = my_id XOR 2i;send M to msg_destination;

elsemsg_source = my_id XOR 2i;receive M from msg_source;

end


19/163

19

Fiecare din cei logp pai de comunicare dureaz ts+twm pentrutransferul unui singur mesaj pe fiecare dimensiune. Astfel, timpul totalnecesar pentru difuzia unu-la-toi pe un hipercub cu p procesoare este:

Tone_to_all =( ts+twm ) log p

Procedura de mai sus funcioneaz corect numai dac nodul 0 estesursa difuziei. Pentru o surs arbitrar trebuie ca procesoarelehipercubului s fie renumerotate cu valoarea rezultat din aplicareaoperaiei XOR etichetei iniiale i celei a sursei. Procedura cefuncioneaz corect pentru orice surs din multimea {0, p-1} esteurmtoarea:

procGENERAL_ONE_TO_ALL_BC(d, my_id, source, M)begin

my_virtual_id = my_id XOR source;mask = 2d 1;for i = d - 1 downto0 do/* Bucla externa*/begin

mask = mask XOR 2i; /* Seteaza bitul i al mastii in 0*/if(my_virtual_id AND mask) = 0 then

if(my_virtual_id AND 2i) = 0 thenbegin

virtual_dest = my_virtual_id XOR 2i;sendM to (virtual_dest XOR source);/* Converteste virtual_dest in eticheta destinatiei

fizice*/end

else

beginvirtual_source = my_virtual_id XOR 2i;receive M from (virtual_source XOR source);/*Converteste virtual_source in eticheta sursei fizice */

endend

end


20/163

20

Comunicarea personalizatunu-la-toi (scatter)Un procesor trimite cte un mesaj Mpla fiecare procesor p.

Comunicarea personalizata unu-la-toi pe hipercubComunicarea unu-la-toi personalizateste diferitde difuzia unu-la-

toi deoarece procesorul surs trasmite p mesaje cte unul pentrufiecare procesor. Spre deosebire de difuzia unu-la-toi, acest tip decomunicare nu implicmultiplicarea mesajelor.

Operaia invers este comunicarea toi-la-unu (gather), n care unsingur procesor colecteazmesaje unice de la toate celelate procesoare.Operatia de gather este diferitde cea de acumulare deoarece nu implicoperaii de combinare sau comprimare (reducere a datelor).

Comunicarea personalizat unu-la-toi pe diferite arhitecturi estesimilara cu cea a difuziei unu-la-toi. Din aceste considerente va fiprezentat detaliat doar comunicarea personalizat unu-la-toi pehipercub.

Figura de mai jos descrie paii de comunicare pentru comunicarea

personalizat unu-la-toi pe un hipercub cu 8 procesoare. Iniial, nodulsurs (procesorul 0) conine mesajele destinate fiecrui nod alhipercublui. In figurmesajele sunt definite ca etichete ce indicnoduldestinaie. In prima etap, sursa trimite jumtate din mulimea mesajelorde care dispune unuia dintre vecinii si. n pai consecutivi, fiecareprocesor care dispune de mesaje, transfera jumtate din mulimeamesajelor de care dispune unui vecin care nu a primit ncnici un set demesaje. Vor fi log p pai de comunicare, corespunztor celor logpdimensiuni ale hipercubului. Modul n care se desfoar comunicrileeste identic cu cel de la difuzia toi-la-toti. Numai dimensiunea iconinutul mesajelor sunt diferite.


21/163

21

Toate muchiile unui hipercub cu p procesoare de-a lungul uneianumite dimensiuni leagdousubcuburi cu p/2 procesoare. Dupcumeste ilustrat n figur, n fiecare pas de comunicare personalizat,mesajele trec de la un subcub la altul. Din mulimea mesajelor de caredispune un procesor nainte de nceperea comunicrii ce corespunde la oanumitdimensiune, jumatate trebuie trimise unui procesor din cellalt

subcub. In fiecare pas, un procesor pstreaz jumtate din mulimeamesajelor de care dispune, mesaje necesare procesoarelor din propriulsubcub i trimite cealalta jumtate a mulimii mesajelor ctre procesoaredin cellalt subcub. Timpul n care datele sunt distribuite este:

Tone_to_oll_pers= tslog p + twm ( p/2+p/4+p/8++1) == tslog p + twm ( p-1)


22/163

22

Difuzarea toi-la-toiFiecare procesor trimite un mesaj Mpla toi ceilali. Operaia invers

o reprezintacumularea multinod, n care fiecare procesor este destinaiaunei acumulri ntr-un nod.

O modalitate de a executa o operaie de difuzare toi-la-toi este aceeade a executa p operaii de difuzare unu-la-toi. Canalele de comunicaiipot fi utilizate mai eficient prin concatenarea mesajelor transmise ntr-unpas de comunicare ntr-un singur mesaj.

Difuzarea toi-la-toi pe un inelIn difuzarea unu-la-toi pe inel, cel mult douci de comunicare sunt

active la un moment dat. In cazul difuzrii toi-la-toi, toate canalele potfi ocupate simultan deoarece ntotdeauna fiecare procesor va avea oinformaie ce trebuie trimisvecinilor si. Fiecare procesor trimite ntimesajul su unuia dintre vecini. In fiecare pas ulterior, mesajul primit dela un vecin este trimis celuilalt vecin. Timpul necesar difuziei toi-la-toipe un inel este:

Tall-to-all=(ts+twm)(p-1)


23/163

23

Difuzarea toi-la-toi pe o plasbidimensional

Ca i n cazul difuzrii unu-la-toi, difuzarea toi-la-toi pe o plasbidimensional e bazatpe algoritmul pe inel, liniile i coloanele fiindtratate ca inele. Comunicarea se desfoar n 2 faze. In prima faz, pefiecare linie din plas se execut o difuzare toi-la-toi utilizndprocedura pe inel. In aceast faz procesoarele colecteaz cele p

mesaje de la cele p procesoare corespunztoare unei linii. Fiecare

procesor grupeazmesajele ntr-un singur mesaj. A doua fazreprezinto difuzare toi-la-toi pe coloane a mesajelor rezultate n urma gruprii.Timpul total necesar comunicarii este:

Tall-to-all=2ts( p - 1)+twm(p - 1)


24/163

24

procALL_TO_ALL_BC_MESH(my_id, my_msg, p, result)begin

/*Comunicatie de-a lungul liniilor*/

left = (my_id - 1) mod p;right = (my_id + 1) mod p;result = my_msg;fori = 1 to p -1 do

send msg to right;receivemsg from left;result= result U msg;

end;/* Comunicatie pe coloane*/

up= (my_id - pp) mod p;

down= (my_id + pp) mod p;msg = result;fori = 1 to p -1 do

send msg to down;receivemsg from up;result = result msg;

end;end.


25/163

25

Difuzarea toi-la-toi pe hipercubProcedura necesit logp pai. In fiecare pas, comunicarea se

desfoar pe cte o dimensiune a hipercubului cu p procesoare. nfiecare pas, perechi de procesoare schimb mesaje i dubleazdimensiunea mesajului ce va fi transmis n pasul urmtor concatenndmesajul su cu cel primit. Figura de mai jos prezintaceti pai pentru

un hipercub cu 8 noduri, cu canale de comunicaie bidirecionale.Dimensiunea mesajului transmis n pasul i este 2(i-1)m. Timpul necesarunei perechi de procesoare s primeasc i s transmit mesaje unulceluilalt este ts+2(i-1)twm.Timpul necesar ntregii proceduri este:

Tall-to-all=tslog p+twm(p - 1)

Algoritm de difuzare toi-la-toi pe un cub d-dimensionalproc ALL_TO_ALL_BC_HCUBE(my_id, my_msg, d, result)begin

result = my msg;for i=0 to d-1 do

partner = my_id XOR 2i;send result to partner;receive msg from partner;result = result U msg;

end


26/163

26

Comunicarea personalizattoi-la-toiFiecare procesor s trimite cte un mesaj Msdla fiecare procesor d.

Comunicarea personalizattoi-la-toi pe un inel

Figura de mai jos descrie paii unei comunicri personalizate toi-latoi pe un inel de 6 procesoare. Pentru a efectua aceasta opera ie, fiecareprocesor trimite p-1 mesaje, fiecare de dimensiune m. In figur acestemesaje sunt definite de perechile de ntregi (i, j), unde i reprezintsursai j destinaia finala mesajului.

In primul pas, fiecare procesor trimite toate mesajele sale ca un mesajde dimensiune m(p-1) la unul dintre vecinii si (toate procesoarele trimit

n aceeai direcie). Din cele m mesaje primite de un procesor n acestpas, un singur mesaj i este adresat. De aceea fiecare procesor extrageinformaia ce i aparine i trimite mai departe restul mesajelor (p-2).Acest proces continu. Dimensiunea mesajului transmis scade cuvaloarea m n fiecare pas. Intr-un pas, fiecare procesor adaug n listamesajelor primite un mesaj diferit de cele din lista sa. Deci, n p-1 pai,fiecare procesor primete mesajele trimise de celelalte procesoare.Dimensiunea unui mesaj transmis n faza i pe un inel de procesoare fiindm(p-1), timpul total al acestei operaii este:

Tall_to_all_pers= (ts+ twmp)(p-1)


27/163

27

In procedura descris mai sus, toate mesajele au fost trimise naceeai direcie. Dacjumtate din mulimea mesajelor este trimisntr-o direcie i cealalt jumtate este expediat n direcia opus, valoarealui twpoate fi redusla jumtate.

Comunicarea personalizattoi-la-toi pe o plas

bidimesionalIn cazul comunicrii personalizate toi-la-toi pe o plas cu p

procesoare ( p p ), fiecare procesor i grupeaz cele p mesaje n

funcie de coloana procesorului destinaie. In figura de mai jos esteprezentato plasde 3x3 procesoare, n care fiecare procesor are iniial9 mesaje de dimensiune m cte unul pentru fiecare procesor. Fiecareprocesor grupeaz mesajele n 3 pachete de cte 3 mesaje fiecare (ngeneral ppachete de cte p mesaje fiecare). Primul pachet conine

mesajele destinate procesoarelor 0, 3, 6; al doilea pachet conine mesajepentru procesoarele 1, 4, 7; ultimul pachet conine mesaje pentru

procesoarele 2, 5, 8. Dupa ce mesajele au fost mpachetate, comunicareapersonalizat toi-la-toi este executat independent pe fiecare linie, cupachete de dimensiune m p . Un pachet conine mesajele pentru toate

cele p procesoare de pe o coloana.

La sfritul celei de-a doua faze, procesorul i are mesajele({0,i},...,{8,i}), unde 0i 8. Grupurile de procesoare ce comunic n

fiecare fazsunt ncercuite cu o linie punctat.


28/163

28

Inainte de a doua faza comunicrii, mesajele n fiecare procesor suntsortate din nou, n funcie de linia procesorului destinaie de aceastdat. Apoi comunicarea se desfoar similar primei faze, n coloaneleplasei. La sfritul acestei faze fiecare procesor a primit un mesaj de latoate celelalte procesoare. Timpul total al comunicrii personalizate toi-la-toi cu mesaje de dimensiune m pe o retea bidemensional cu p

procesoare este: Tall_to_all_pers= (2ts+ twmp)( p -1)

Expresia de mai sus nu ia n considerare timpul necesar rearanjriidatelor.

Comunicarea personalizattoi-la-toi pe un hipercubPaii de comunicare necesari realizrii acestei operaii pe un hipercub

cu p noduri (procesoare) sunt n numr de logp. In fiecare pas,comunicarea se desfoarpe cte o dimensiune a hipercubului i fiecareprocesor conine p mesaje de dimensiune m. In timpul comunicrii pe oanumit dimensiune, procesorul trimite p/2 din aceste mesaje.Destinaiile acestor mesaje sunt procesoarele din cellalt subcub. Timpultotal de comunicare este:

Tall_to_all_pers= (2ts+ twmp)log p


29/163

29

Sortarea paralel

Exist o vast literatur avnd ca subiect probleme de sortare.Aceasta se explicprin faptul c sortarea apare ca substask n soluiilealgoritmice a foarte multe probleme.

Problema poate fi enunatastfel:

Date fiind n numere a1,...,an, se dorete renumerotarea lor astfel nctaiaj, i,j{1,...,n}: i


30/163

30

Exemplu: 2,6,3,8

i \ j 1 2 3 4

1 1 3 2 4

2 1 1 1 2

3 0 2 1 2

4 1 1 1 1

5 0 1 0 1

6 0 1 1 1

7 0 0 0 1

Explicare algoritmProcedura are trei faze:Faza 1: determinarea rangurilor relative R[i+n-1,j]; sunt necesare n2

procesoare CREW-PRAM i O(1) uniti de timp sau n2/lognprocesoare si O(logn) uniti de timp.

Faza 2: calcularea poziiilor P[j]; timpul de execuie este de O(logn)cu nn/lognprocesoare CREW-PRAM .

Faza 3: permutarea (plasarea) elementelor aj pe poziiile corecte; nprocesoare, O(1) timp.

Complexitatea timpAlgoritmul necesit O(logn) timp si O(n2/logn) procesoare CREW-PRAM . Citirile simultane din prima faz pot fi evitate fr a afectacomplexitatea.


31/163

31

Sortarea par-impar (Odd-Even-Sort)Versiune a algoritmului BubbleSort pe un lant de procesoare

procedure ODD-EVEN_PAR(n)begin

id = eticheta procesoruluifor i=1to n doif i este impar then

if id este impar then compare-exchange_min(id+1) ;else compare-exchange_max(id-1) ;

if i este par thenif id este par then compare-exchange_min(id+1) ;else compare-exchange_max(id-1) ;

endforend

Exemplu:Sortarea a 8 elemente cu algoritmul Par-Impar


32/163

32

ComplexitateaO(n) timp cu n processoare CREW-PRAM. Algoritmul este optimal

pentru arhitectur. Fiecare procesor este solicitat O(n) timp. Totui,costul nu este optimal: nr.procesoaretimpul paralel = n2, iar timpul

pentru cel mai rapid algoritm secvential = O(nlogn).

Sortarea prin interclasarea de secvene bitoneOperaia de baz: sortarea unei secvene bitone.O secvenbiton este o secventde elemente cu

urmtoarele proprieti:1. Existi a.. este monoton cresctoare i

este monoton descresctoare SAU2. Existo permutare circulara.. sfie satisfacutcondiia anterioar.

Exemple de secvene bitone : nti crete i apoi descrete, i = 3. : shift stnga cu 4 poziii, i = 3.

Proprieti ale secvenelor bitoneFie s = o secvenbiton,s1= is2=

1. In secvena s1existbi= min{ai, an/2+i} atfel nct toate elementele

din faa lui bi sunt din secvena cresctoare i toate elementele dedupbisunt din secvena descresctoare.2. Secvena s2are i ea un punct similar.3. Secvenele s1i s2sunt bitone.4. Fiecare element din s1este mai mic dect fiecare element din s2.

Esena sortrii unei secvene bitoneProblema sortrii unei secvene bitone de lungime n se reduce la

sortarea a dousecvene bitone de dimensiune n/2.


33/163

33

Exemplu de sortare a unei secvene bitone

Comparatori pentru sortarea a doua numere

Reea de sortare R1 de secvene bitone (n=16)


34/163

34

Conversia unei secvene oarecare ntr-o secvena bitonPentru a sorta o secven de n elemente, prin tehnica sortrii unei

secvene bitone, trebuie sdispunem de o secvenbitonformatdin nelemente.1. Douelemente formeazo secvenbiton.2. Orice secven nesortat este o concatenare de secvene bitone de

lungime 2.Ideea de sortare: Combinarea ntr-o secvena mai larg pn cnd seobine o secvenbitonde lungime n.

Reea de comparatori (R2) care transformo secvenoarecare ntr-o secvenbiton

ConcluziiCele dou reele combinate n ordinea (R2,R1) transform o

secvenoarecare ntr-o secvensortat.

Algoritm de sortare paralelbazatpe interclasarea desecvene bitoneRemarcabil pentru simplitatea sa este algoritmul lui Batcher, 1968,

cunoscut sub numele de ,,bitonic-merge-sorting. Algoritmul utilizeazparadigma combinrii recursive, uor modificat.

Convenii:

1. A[0:n-1] este tabloul de intrare;


35/163

35

2. d este un parametru binar specificnd ordinea cresctoare (d = 0) saudescresctoare (d = 1) a cheilor de sortare;

3. COMP_EX(x,y;d) desemneazoperaia care aranjeazdounumerex i y n ordine cresctoare (d=0) sau descresctoare(d=1).

Algoritmul Batcher de sortare bitonic

proc sortare_bitonica(A[i:i+b-1],d)begin

if(b = 2) (A[i],A[i+1]) = COMP_EX(A[i],A[i+1];d)elsesortare _bitonica (A[i:i+b/2-1],0);sortare _bitonica (A[i+b/2:i+b-1],1);interclasare _bitonica (A[i:i+b-1],d);

end

Algoritm de interclasare a dousecvene bitone

proc interclasare_bitonica(A[i:i+b-1],d)beginifb = 2 (A[i],A[i+1]) = COMP_EX(A[i],A[i+1];d)elsefor all j:0 j < b/2 par do

(A[i+j],A[i+b/2+j]) = COMP_EX(A[i+j],A[i+b/2+j];d);interclasare _bitonica (A[i:i+b/2-1],d);interclasare _bitonica (A[i+b/2:i+b-1],d)

end

Implementare pe o mainCREW-PRAM

Interclasarea_bitonic necesit n procesoare i O(logn) timp,rezultnd pentru sortare_bitonicaun timp de O(log2n) i un necesar deO(n) procesoare.

Eficiena algoritmului este, evident, O(1/logn).

Implementare pe o reea de sortareReeaua (R2,R1) implementeazalgoritmul lui Batcher. Numrul de

faze este logn. Fazele sunt compuse din O(logn) pai.


36/163

36

Implementarea algoritmului lui Batcher pe hipercubCubul binar multidimensional este o arhitectur ideal pentru

implementarea procedurii sortare_bitonica. Sortarea bitonica const nd faze de combinare (merging): M0,M1,...,Md-1, unde Mi realizeazcombinarea perechilor de secvene de lungime 2i. Modelul algoritmiceste paradigma combinrii recursive n varianta execuiei combinarii

naintea celor dou apeluri recursive. Execuia fazei Mi pe hipercubnecesitutilizarea succesiva dimensiunilor Ei,Ei-1,...,E1,E0.

Planificare dimensiunilorPlanificarea utilizrii dimensiunilor pentru o sortare completpoate fi

reprezentatprin urmatoarea paradigm:

Faz Dimensiuni activeM0 : E0M1 : E1E0M2 : E2E1E0

. . . . . . . . . . . .Md-1: Ed-1Ed-2... E1E0

Planificarea dimensiunilor unui hipercub de ordinul 4

Planificarea dimensiunilor corespunde la fazele sortrii prininterclasarea de secvene bitone.


37/163

37

Sortarea rapidpe hipercubSne amintim cun hipercub cu d dimensiuni este format din dou

hipercuburi cu d-1 dimensiuni. Ideea de sortare rapidpe hipercub estede a plasa cele dousecvene rezultate n urma operaiei de partiionaren jurul pivotului a secvenei de sortat memorat n nodurilehipercubului. Operaia se repet apoi recursiv pe subcuburi. Selectarea

pivotului este problema cheie. Selectarea unui pivot care spartitionezesecvena de sortat n dousubsecvente de dimensiuni aproximativ egaleeste dificil.

Algoritmul de sortare rapida pe hipercub

proc sortare_rapida_pe_hipercub(B, n)begin

id = eticheta procesorului;for i=1 to d do

x =pivot;partiioneazB n B1i B2a.. B1 x B2;if ithbit is 0 then

trimite B2procesorului vecin pe a dimensiunea i;C = subsecvena primitde la vecinul dimensiune i;B = B1U C;

elsetrimite B1procesorului vecin pe a dimensiunea i;C = subsecvena primitde la vecinul dimensiune i;B = B2 U C;

Apliclui B sortarea rapidsecvenial;

end


38/163

38

Calcul matricial

Transpunerea unei matriceFormularea problemei:

Datfiind matricea Ann se cere sse calculeze matricea

AT

[i,j] = A[j,i] pentru toi i,j=1,2,,nObs. Nu se efectuezcalcule, ci doar micari de elemente.Timpul secvenial Ts(n) = (n

2).Algoritmul implementat pe o maina EREW PRAM este banal i are

cost (1).

Algoritmul secvenial standard:proc MAT_TRANSP(A)begin

for i = 0 to n-1 doforj = i+1 to n-1 do

interchange(A[i,j],A[j,i]) ;end

Transpunerea unei matrice 44 cu o plasa de 16 de procesoare

Paii de comunicare Configuraia final


39/163


40/163

40

Algoritm recursiv de transpunere a unei matrice 88 - Pasii III-IV

Ultima divizare Configuraia final

Implementare pe un hipercub cu p procesoareHipercubul este divizat n 4 subcuburi cu p/4 procesoare. Sferturile de

matrice (quadranii) sunt mapate pe cele 4 subcuburi. In fiecare subcubse interschimbblocurile stnga-jos cu dreapta-sus. Se repetprocedeuln fiecare subcub.

ComplexitateaRecusia se oprete cnd dimensiunea blocului este n2/p. Numrul de

pai = log4p=(log2p)/2 . Fiecare pas de comunicare se realizeazpe doudin dimensiunile hipercubului (2 muchii). Transpunerea local este(n2/p). Rezulturmtoarele:

-Timpul total este ((n2/p)logp)-Costul = (n

2

logp) nu este optimal.Inmulirea a doumatrici

proc MAT_MULT (A,B,C)begin

for i = 0 to n-1 doforj = 0 to n-1 do

C[i,j] =0 ;for k =0 to n-1 do

C[i,j] = C[i,j] +A[i,k]B[k,j];end


41/163

41

Algoritmul nmulirii de blocuri

proc MAT_MULT (A,B,C)begin

for i = 0 to q-1 doforj = 0 to q-1 do

Ci,j= [0] ;for k =0 to qdo

Ci,j= Ci,j +Ai,kBk,j;endMatricile A si B sunt divizate n blocuri Ai,ki respectiv Bk,j, de

dimensiuni (n/q)(n/q).

Implementare standardArhitectura naturala este arhitectura cu topologie de tip plas.

Numrul de procesoare p=q2. Fiecare procesor Pi,j dispune n memoria

localde blocul Ai,ji un bloc Bi,ji calculeaza Ci,j. Pentru a calcula Ci,jprocesorul Pi,j are nevoie de Ai,k si Bk,j k=0,,q-1. Pentru fiecare k,blocurile Ai,k i Bk,j sunt obinute printr-o difuzie toi-la-toi pe linii iapoi pe coloane.

Algoritmul lui CannonAlgoritmul lui Cannon este asemntor cu cel corespunztor

implementrii standard dar cu consum mai mic de memorie. Diferentaconst n faptul c fiecare bloc este procesat la momente diferite nlocuri diferite. Pentru aceasta, blocurile sunt deplasate ciclic. Iniialblocurile sunt aliniate prin deplasri ciclice la stnga (n A) i n sus (n

B). Urmeaza p-1 pai de nmuliri locale i adunri locale de blocuri,urmate de deplasri ciclice la stnga (n A) i n sus (n B).


42/163

42

Alinierea iniial(prima faz)

A si B dupa alinierea iniial Poziiile blocurilor dupprimadeplasare

Poziiile blocurilor dup Poziiile blocurilor dupaa II-a deplasare III-a deplasare


43/163

43

Complexitatea implementrii pe o plasde proecesoareTimpul consumat de algoritmul lui Cannon este acelai cu cel din

cazul implementarii standard dar consumul de memorie este mult maimic.


44/163

44

Sisteme de ecuatii

Sistem standard de ecuatii liniare

Reducerea la forma triunghiular(eliminarea Gaussiana)

Algorimul eliminrii Gaussiene

proc GAUSSIAN ELIMINATION (A, b, y)begin

for k = 0 to n-1 doforj = k+1 to n-1 do

A[k,j] = A[k,j] / A[k,k]; /* pasul de divizare */y[k] = b[k] / A[k,k];A[k,k] = 1;

for i = k+1 to n-1 doforj = k +1 to n-1 do/* pasul de eliminare */A[i,j] = A[i,j] - A[i,k] A[k,j];

b[i] = b[i] - A[i,k]y[k];A[i,k] = 0;

end


45/163

45

Versiunea paralelproc GAUSSIAN ELIMINATION (A, b, y)begin

for k = 0 to n-1 doforj = k+1 to n-1 do

A[k,j] = A[k,j] / A[k,k]; /* pasul de divizare */

y[k] = b[k] / A[k,k];A[k,k] = 1;for i = k+1 to n-1 par do

forj = k +1 to n-1do/* pasul de eliminare */

A[i,j] = A[i,j] - A[i,k] A[k,j];b[I] = b[i] - A[i,k]y[k];

A[i,k] = 0;end

Implementare pe o reea liniar

Cele n procesoare se noteaz cu P0,.Pn-1. Fiecare procesor Pidispune n memoria localde coeficienii ecuaiei a i-a (linia i a matriceiA a sistemului de ecuaii plus bi).

Timpul consumat n iteraia k este (n-k-1). Rezulta pentru ntregulalgoritm timpul (n2).

Implementarea pasului de divizare

forj = k+1 to n-1 do A[k,j] = A[k,j] / A[k,k];y[k] = b[k] / A[k,k];A[k,k] = 1;


46/163

46

Difuzia unu-la-toi a liniei A[k,*]

Implementarea pasului de eliminare

forj = k +1 to n-1doA[i,j] = A[i,j] - A[i,k] A[k,j];

b[i] = b[i] - A[i,k]y[k];A[i,k] = 0;


47/163

47

Drumuri optime n grafuri

Problema algebrica drumurilorProblema algebric a drumurilor unific strategiile utilizate n

rezolvarea a trei clase mari de probleme, fiecare dezvoltatindependent,cu algoritmi proprii: determinarea nchiderii tranzitive a unei relaii,determinarea drumurilor minime ntr-un graf, rezolvarea sistemelor deecuaii liniare (metoda Gauss-Jordan).

Algoritmul lui KuceraAlgoritmul lui Kucera, dezvoltat pentru o main CREW-PRAM,

pentru problema drumurilor minime poate fi considerat de baz.Algoritmul utilizeaz ca date iniiale matricea Dnn a ponderilor

muchiilor unui graf G = (V,E), (V = {1,...,n}, E VV).i,j {1,...,n} : D[i,j] = dij, dac(i,j) E

, dac(i,j) Eunde dijeste distana dintre nodurile i i j (dii= 0).

Rezultatul execuiei algoritmului lui Kucera este o matrice Cnnunde :C[i,j] = 0, daci = jC[i,j] = min[((i,i1,,ik,j)) || drum in G]{ D[i,i1]+D[i1,i2]++D[ik,j]}, daci j

Pseudocod pentru Algoritmul lui Kucera

for alli,j:1 i,j n par doC[i,j] = D[i,j];repeatlogn times

for alli,j,k: 1 i,j,k n par dow[i,k,j] = C[i,k]+C[k,j];

for alli,j: 1 i,j n par doC[i,j] = min{C[i,j],mink{w[i,k,j]; k = 1,...,n}};

end

ComplexitateaOperaia min{C[i,j],mink{w[i,k,j]; k = 1,...,n}} poate fi implementat

prin procedura sum, ,, fiind n acest caz operatorul de minimizare.Daca se utilizeazmodelul CREW-PRAM, complexitatea timp a acestei

operaii este O(logn) iar numrul de procesoare utilizate este n/logn.


48/163

48

Rezult pentru algoritm un timp de execuie T(n)=O(log2n) si unnecesar de procesoare de O(n3/logn).

Pe o main CRCW-PRAM, operaia de minimizare anteriormenionat se poate efectua n timp constant cu n2 procesoare.Consecina este reducerea timpului de execuie la O(logn), rezultnd nso cretere a numrului procesoarelor la O(n4).

Definirea problemei algebrice a drumurilorInlocuind n algoritmul lui Kucera: D cu A (matricea de adiacen), +

cu i logic, min cu sau logic, se obtine un algoritm pentru problemanchiderii tranzitive. Menionm c pentru un graf G, problemanchiderii tranzitive constn determinarea unei matrice Cnn:

C[i,j] = 1, daca exista n G un drum de la i la j0, altfel

Generaliznd, problema algebrica drumurilor poate fi definitastfel:Dat fiind un graf ponderat G = (V,E,w), unde w:E H, iar (H,,)formeazun inel cu unitate, sse determine matricea Cnnastfel nct

C[i,j] = w(p)[p drum de la i la j]

Obs. Daca p = i0i1...ik-1ikatunci w(p) =1

0

=k

lw[il,il+1].

Implementari sistoliceAbordrile sistolice ale problemei algebrice a drumurilor sunt foarte

numeroase. ntre acestea, implementarea algoritmului lui Kleen pe oretea de tip plas, dat de Y. Robert si D. Trystram, 1986, esteremarcabil.

Parametrii algoritmului sunt T = 5n-2 si A O(n2).


49/163

49

Algoritmul sistolic al lui Y. Robert si D. Trystram

Retea sistolicpentru drumuri cu aceeai sursReeaua lui Y. Robert i D. Trystram poate fi modificatsi adaptat

problemei drumurilor de cost minim sau maxim de la un nod n la toatecelelalte n-1 noduri ale unui digraf aciclic G = (V,A), V = {1,2,...,n}, E VV. Vom prezenta n continuare o arhitectur sistolic pentruproblema drumurilor de cost maxim de la un nod n la toate celelalte n-1noduri ale unui digraf aciclic G = (V,A). Iniial, Cnn este matriceaCostnn a costurilor arcelor digrafului aciclic G. cij este costul arcului(i,j).


50/163


51/163

51

Exemplu de aplicare a algoritmului de drumuri maximentr-un digraf aciclic


52/163

52


53/163

53

Comentarii bibliografice

Seciunea Primitive ale calculului paralel are la baz cartea,Efficient Parallel Algorithms, Cambridge University Press, 1988,autori A. Gibbons, W. Rytter [1].

Seciunile Comunicri colective, Calcul Matricial i Sisteme deecuaii sunt inspirate din cartea Introduction to Parallel Computing:Design and Analysis of Algorithms, Benjamin-Cummings,1994, autoriV. Kumar, A. Grama A. Gupta i G Karypis [2].

Seciunile Sortarea paralel i Drumuri optime n grafuri suntsinteze realizate pe baza lucrrilor [1]-[5].

Unele figuri i/sau exemple sunt preluate din crile [1], [2], [5].


54/163

54


55/163

55

PARTEA a-II-a

INTRODUCERE N MPI

Autor: Cristian-Mihai Amarandei


56/163

56


57/163

57

Standardul MPIMPI (Message Passing Interface) reprezint o bibliotec pentru

programarea paralel. MPI a fost creat n cadrul grupului MPI Forumntre 1993 i 1994, cnd a fost elaborat i standardul 1.2. Acest standarddefinete mai mult de 120 de funcii care ofersuport pentru: Comunicri point-to-point: Operaiile de baz n recepia itrimiterea mesajelor de ctre procese cu MPI sunt send i receive cu

variantele de implementare a acestora. Operaii colective: Sunt operaii definite pentru comunicri care

implicun grup de procese. Grupuri de procese i contexte de comunicare Topologia proceselor: n MPI un grup de procese este o colecie de

nprocese n care fiecare proces are atribuit un rangntre 0i n-1. nmulte aplicaii paralele o atribuire liniar a rangurilor nu reflectlogica comunicrii ntre procese. Adesea procesele sunt aranjate nmodele topologice ca de exemplu o plas cu 2 sau 3 dimensiuni.

ntr-un caz i mai general procesele pot fi descrise de un graf i vomface referire la aranjarea acestor procese ntr-o topologie virtual.O distincie clartrebuie fcutntre o topologie virtuali topologiade baz a suportului, hardware-ul propriu-zis. Topologia virtualpoate fi exploatat de sistem n atribuirea proceselor ctreprocesoarele fizice, dacacest lucru ajutla creterea performanelorde comunicare pentru o anumitmain, dar realizarea acestui lucrunu face obiectul MPI. Descrierea unei topologii virtuale depindenumai de aplicaie i este independentde sistemul de calcul.

Suport pentru limbajele Fortran77 i C: Aplicaiile paralelefolosind MPI pot fi scrise in limbaje ca Fortran77 i C.

Obinerea informaiilor despre mediu i managementul acestora:Sunt introduse rutine pentru obinerea i setarea unor parametripentru execuia programelor corespunztoare diferitelorimplementri ale MPI.

Standardul MPI a ajuns la versiunea 2.0 i ofern plus suport pentru: Extinderea operaiilor colective: n MPI-1 intercomunicarea

reprezenta comunicarea ntre dou grupuri de procese disjuncte. nmulte funcii argumentul de comunicare poate fi unul deintercomunicare, excepie facnd operaiile colective. Acest lucrueste implementat n MPI-2 care extinde utilizarea funciilor pentru

operaiile colective.


58/163

58

Crearea proceselor i managementul dinamic al acestora:Obiectivele principale sunt oferirea posibilitaii de a crea aplicaii cuun numar variat de task-uri (task farm) i cuplarea aplicaiilor dupmodelul client/server.

One-sided Communication: Ideea de bazeste aceea ca un task saibacces direct la memoria altui task (asemantor modeluluishared

memory), ca taskul proprietar al unei zone de memorie s permitaccesul i oferirea unor metode de sincronizare. Parallel File I/O: Mecanismele care oferoperaii de I/O paralele,

permit taskurilor sacceseze fiierele ntr-un mod controlat dar suntdependente de arhitectur. MPI-2 definete rutine de nivel naltpentru a furniza un model de programare unic pentru operaiile deI/O paralele.

Suport pentru alte limbaje de programare: Este oferit suportulpentru C++. De asemenea exist i o variant pentru Java i ovariantorientatobiect (OOMPI).

Modelul de execuieExecuia unui program scris cu apeluri MPI const n rularea

simultan a mai multor procese, definite n mod static (MPI-1) saudinamic (MPI-2), identice sau diferite i care comuniccolectiv sau de launul la altul (point-to-point). Procesele comunicante fac parte din acelaicomunicator, care definete domeniul de comunicare. n cadruldomeniului de comunicare fiecare proces are un rang. De faptcomunicatorul asigur un mecanism de identificare a grupurilor deprocese i de protecie a comunicrii. Un comunicator poate fi de doufeluri: intracomunicator pentru procese din interiorul aceluiai grup i

intercomunicatorpentru comunicrile dintre grupuri.Existase apeluri de funcii mai importante care ar putea fisuficiente pentru scrierea unui program MPI:

MPI_Init iniiazun calcul MPI; MPI_Finalize terminun calcul MPI; MPI_Comm_size determinnumrul proceselor; MPI_Comm_rank determinidentificatorul procesului; MPI_Send trimite un mesaj; MPI_Receive primete un mesaj.


59/163

59

Observaie:Dupapelul MPI_Finalize nu se mai poate apela nici ofuncie MPI.

Exemplu:main(int argc, char **argv){

MPI_Init (&argc, &argv);

MPI_Comm_size (MPI_COMM_WORLD, count);MPI_Comm_rank (MPI_COMM_WORLD, &myrank);printf (Eu sunt %d din %d, myrank, count);MPI_Finalize();

}

Parametrul MPI_COMM_WORLD precizeaz c toate proceseleaparin aceluiai grup i reprezintcomunicatorul iniial care este valabilpentru toate procesele aceluiai grup.

Procesele pot executa instruciuni diferite, dar pentru aceasta trebuiesse asigure un mecanism de difereniere:

Exemplu :main(int argc, char **argv)

{ MPI_Init (&argc, &argv);............MPI_Comm_size (MPI_COMM_WORLD, count);MPI_Comm_rank (MPI_COMM_WORLD, &myrank);if (myrank == 0)

master();else

slave();............MPI_Finalize();}

Tipuri de date n MPITrebuie observat faptul c de fiecare dat este specificat lungimea

mesajului ca numr de intrri, nu ca numr de bytes. Tipurile de datede bazcorespund tipurilor de date de bazale limbajului folosit. Astfelavem:

MPI datatype C datatypeMPI_CHARMPI_SHORTMPI_INTMPI_LONG

signed charsigned short intsigned int

signed long int


60/163


61/163

61

[OUT buf] - adresa zonei de memorie n care este recepionat mesajul

n cazul n care este primit corespunztor parametrilorfunciei

[IN count] - numrul de elemente care pot fi primite n zona tampon[IN datatype] - tipul datelor pentru fiecare element din buffer primit[IN source] - identificatorul procesului surs[IN tag] - identificator de mesaj[IN comm] - comunicatorul[ OUT status] - variabilutilpentru aflarea dimensiunii, identificatorului

de mesaj i a sursei, codurilor de eroare

Prototipul funciei este urmtorul:int MPI_Recv(void* buf, int count, MPI_Datatype

datatype, int source, int tag, MPI_Comm comm,MPI_Status *status)

Exemplu:#include "mpi.h"main( int argc, char **argv ){char message[20];int myrank;MPI_Status status;MPI_Init( &argc, &argv );MPI_Comm_rank( MPI_COMM_WORLD, &myrank );if (myrank == 0) /* codul pentru procesul zero */{

strcpy(message,"Hello");MPI_Send(message, strlen(message), MPI_CHAR, 1, 99,

MPI_COMM_WORLD);}else /* codul pentru procesul 1 */{

MPI_Recv(message, 20, MPI_CHAR, 0,99,MPI_COMM_WORLD,&status);

printf("received :%s:\n", message);}MPI_Finalize();

}

Moduri de realizare a comunicriiExist mai multe moduri de realizare a comunicrii, indicate n

numele funciei printr-o literastfel: B pentru bufferat, S sincroniR pentru ready.


62/163

62

O operaie de tip send n mod buffered poate fi iniiat indiferentdacoperaia receivecorespunztoare a fost iniiatsau nu. n acest modterminarea nu depinde de apariia unei operaii receive. Pentru a terminaoperaia poate fi necesar ca mesajul s fie ntr-un buffer local. n acestscop, bufferul trebuie furnizat de ctre aplicaie. Spaiul (de memorie)ocupat de buffer este eliberat atunci cnd mesajul este transferat ctre

destinaie sau cnd operaia este anulat.O operaie de tip send n mod sincronpoate fi iniiat chiar dacooperaie receivecorespunztoare a fost sau nu iniiat. Oricum, operaiava fi ncheiatcu succes numai daco operaie receive corespunztoarea fost iniiat i a nceput recepia mesajului trimis prin send. Astfel,ncheierea operaiei send sincronenu indicnumai cbufferul poate fireutilizat, dar de asemenea indici faptul creceptorul a ajuns ntr-unanumit punct din execuia sa i anume faptul c a iniiat o operaiereceive corespunztoare.

Observaie:Modul sincron asigur faptul c o comunicare nu seterminla fiecare sfrit de proces nainte ca ambele procese sajungla aceeai operaie de comunicare.

n modul sincron operaia de comunicare este ncheiatsimultan dectre ambele funcii indiferent care este primul apel.

O operaie de tip send n mod ready poate fi iniiat numai dac ooperaie receive a fost deja iniiat, altfel operaia este o sursde erori.Pe unele sisteme acest lucru poate permite nlturarea operaiilor de tiphand-shake i au ca rezultat creterea performanelor. De aceea, ntr-unprogram scris corect o operaie ready send poate fi nlocuit de unastandard fr a avea alt efect asupra comportrii programului dectperformana.

Apelul funciei Bsend:MPI_Bsend (buf, count, datatype, dest, tag, comm)

[ IN buf] -adresa zonei tampon (bufferului) pentru datele de trimis[ IN count] - numrul de elemente de trimis din buffer[ IN datatype] - tipul datelor pentru fiecare element din buffer[ IN dest] - rangul destinaiei[ IN tag] - identificator de mesaj[ IN comm] - comunicatorul

Prototipul funciei este urmtorul:int MPI_Bsend (void* buf, int count, MPI_Datatype

datatype, int dest, int tag, MPI_Comm comm)


63/163

63

Observaie:n modul de lucru cu zon tampon (buffered), trebuie s se asigure

spaiul tampon, prin apelul MPI_buffer_attach(), dup care esteeliberat cuMPI_buffer_detach().

Apelul funciei Ssend:MPI_Ssend (buf, count, datatype, dest, tag, comm)

[ IN buf] - adresa zonei tampon (bufferului) pentru datele de trimis[ IN count] - numrul de elemente de trimis din buffer[ IN datatype] - tipul datelor pentru fiecare element din buffer[ IN dest] - rangul destinaiei[ IN tag] - identificator de mesaj[ IN comm] - comunicatorul

Prototipul funciei este urmtorul:int MPI_Ssend(void* buf, int count, MPI_Datatype

datatype, int dest, int tag, MPI_Comm comm)

Observaie:n modulsincron, indiferent care este primul apel, operaia se ncheie

simultan de ctre ambele funcii.

Apelul funciei Rsend:MPI_Rsend (buf, count, datatype, dest, tag, comm)

[ IN buf] - adresa zonei tampon (bufferului) pentru datele de trimis[ IN count] - numrul de elemente de trimis din buffer[ IN datatype] - tipul datelor pentru fiecare element din buffer

[ IN dest] - rangul destinaiei[ IN tag] - identificator de mesaj[ IN comm] - comunicatorul

Prototipul funciei este urmtorul:int MPI_Rsend(void* buf, int count, MPI_Datatype datatype,

int dest, int tag, MPI_Comm comm)

Observaie:n modul readyapelul receive trebuie s-l preceadobligatoriu pe cel

pentru operaia send.


64/163

64

Comunicri unu-la-unu neblocanteUn mecanism care adesea conferperformae mai bune este utilizarea

comunicrilor neblocante. Comunicrile neblocante pot fi folosite n celepatru moduri ca i cele blocante: standard, bufferate, sincrone iready. Modul de folosire este acelai cu cel de la comunicrile blocante.

Cu excepia modului readyoperaia send neblocantpoate fi iniiatchiar daco operaie receive a fost sau nu iniiat, iar una de tip readynumai dac a fost iniiat o operaie receive. n toate cazurile operaiasend este iniiat local i returneaz imediat indiferent de starea altorprocese.

Apelul funciei Isend:MPI_Isend(buf, count, datatype, dest, tag, comm, request)

[ IN buf] -adresa zonei tampon (bufferului) pentru datele de trimis[ IN count] - numrul de elemente de trimis din buffer[ IN datatype] - tipul datelor pentru fiecare element din buffer[ IN dest] - rangul destinaiei[ IN tag] - identificator de mesaj[ IN comm] - comunicatorul[ OUT request] - communication request

Prototipul funciei este urmtorul:int MPI_Isend(void* buf, int count, MPI_Datatype datatype,

int dest, int tag, MPI_Comm comm, MPI_Request*request)

Apelul funciei Irecv:MPI_Irecv(buf, count, datatype, source, tag, comm,

request)

[ IN buf] - adresa zonei tampon (bufferului) pentru datele detrimis

[ IN count] - numrul de elemente de trimis din buffer[ IN datatype] - tipul datelor pentru fiecare element din buffer[ IN source] - identificatorul procesului surs[ IN tag] - identificator de mesaj[ IN comm] - comunicatorul[ OUT request] - communication request

Prototipul funciei este urmtorul:


65/163

65

int MPI_Irecv(void* buf, int count, MPI_Datatype datatype,int source, int tag, MPI_Comm comm, MPI_Request*request)

Din apelul de recepie se revine chiar dac nu exist nici un mesajprimit. Acest mod de lucru poate conduce la erori i n acest caz sefolosesc funcii de detectare a terminrii operaiei: MPI_Wait() i

MPI_Test().

Exemplu:MPI_Comm_Rank (MPI_COMM_WORLD,&myrank);if (myrank == 0) {

int a;MPI_Isend(&a,1,MPI_INT,msgtag,MPI_COMM_WORLD,req1);calcul();MPI_Wait(req1, status);

}else if (myrank == 1) {

int b;MPI_Recv(&b,1,MPI_INT,0,mesgtag,MPI_COMM_WORLD

,status);}

Funcia MPI_Wait() se termin dup terminarea operaiei, iarMPI_Test()se terminimediat i returneazun indicator a crui starearatdacoperaia s-a ncheiat sau nu.

n afar de aceste funcii mai exist MPI_Waitany(),MPI_Testany(),MPI_Waitall(),MPI_Testall(),MPI_Waitsome(),MPI_Testsome().

Pentru mai multe detalii despre aceste tipuri de funcii consultai help-ul distribuiei MPI.

Observaie:1. Funciile de comunicare fr blocare ofer posibilitatea

suprapuneriin timp a operaiilor de comunicare cu cele de calcul, ceeace poate reduce timpul de execuie al aplicaiei.

2. Funcia receive poate fi apelatnumai n modul standard.

Exemplu:MPI_Comm_Rank (MPI_COMM_WORLD,&myrank);if (myrank == 0) {

int a;MPI_Isend(&a,1,MPI_INT,msgtag,MPI_COMM_WORLD,req1);

calcul();


66/163

66

MPI_Wait(req1, status);}else if (myrank == 1) {nt b;MPI_Irecv(&b,1,MPI_INT,0,mesgtag,MPI_COMM_WORLD,req1);MPI_Wait(req1, status);}

Exemplu:Model de aplicaie care implementeaz problema productori-

consumatori (cazul n:1 ) folosind comunicri neblocante [1]....typedef struct{

char data[MAXSIZE];int datasize;MPI_Request req;}Buffer;

Buffer *buffer;MPI_Status status;...MPI_Comm_rank(comm, &rank);MPI_comm_size(comm, &size);

if (rank!=size-1) { //codul pentru producator//initializare producatorul aloca un bufferbuffer= (Buffer *)malloc(sizeof(Buffer));while(1) { //bucla principala//producatorul umple dufferul cu date si intoarce//numarul de bytes din bufferproduce(buffer->data, &buffer->datasize);//trimite dateleMPI_Send(buffer->data, buffer->datasize, MPI_CHAR,size-1, tag, comm);} //end while

}//end if

else{ // rank==size-1; codul pentru consumator//initializare consumatorul aloca un buffer pentru//fiecare producatorbuffer=(Buffer )malloc(sizeof(Buffer)*(size-1));// se apleleaza un receive pentru fiecare producatorfor(i=0; i


67/163

67

//un nou receiveMPI_Irecv(buffer[i].data, MAXSIZE, MPI_CHAR, i,

tag, comm, &(buffer[i].req));}//end for}//end else

Exemplu:

Model de aplicaie care implementeaz problema productori-consumatori (cazul n:1 ) folosind funcia de comunicare neblocante ifuncia MPI_Test()[1] .

...typedef struct{

char data[MAXSIZE];int datasize;MPI_Request req;}Buffer;

Buffer *buffer;MPI_Status status;...MPI_Comm_rank(comm, &rank);

MPI_comm_size(comm, &size);if (rank!=size-1) { //codul pentru producator//initializare producatorul aloca un bufferbuffer= (Buffer *)malloc(sizeof(Buffer));while(1) { //bucla principala

//producatorul umple dufferul cu date si intoarce//numarul de bytes din bufferproduce(buffer->data, &buffer->datasize);//trimite dateleMPI_Send(buffer->data, buffer->datasize,

MPI_CHAR, size-1, tag, comm);} //end while

}//end ifelse{ // rank==size-1; codul pentru consumator

//initializare consumatorul aloca un buffer pentru//fiecare producator

buffer=(Buffer )malloc(sizeof(Buffer)*(size-1));// se apleleaza un receive pentru fiecare producatorfor(i=0; i


68/163

68

// consumatorul elibereaza bufferul de dateconsume(buffer[i].data, buffer[i].datsize);//un nou receive

MPI_Irecv(buffer[i].data, MAXSIZE, MPI_CHAR,i, tag, comm, &(buffer[i].req));

}//end while}//end else

Alte funcii neblocante: MPI_Ibsend,MPI_Issend,MPI_Irsend.

Apelul funciei Ibsend:MPI_Ibsend(buf,count,datatype,dest,tag,comm,request)

[ IN buf] - adresa zonei tampon (bufferului) pentru datele letrimis

[ IN count] - numrul de elemente de trimis din buffer[ IN datatype] - tipul datelor pentru fiecare element din buffer[ IN dest] - rangul destinaiei[ IN tag] - identificator de mesaj[ IN comm] - comunicatorul[ OUT request] - communication request

Prototipul funciei este urmtorul:int MPI_Ibsend(void* buf, int count, MPI_Datatype

datatype,int dest, int tag, MPI_Commcomm, MPI_Request *request)

Apelul funciei Issend:MPI_Issend(buf,count,datatype,dest,tag,comm,request)

[ IN buf] - adresa zonei tampon (bufferului) pentru datele detrimis

[ IN count] - numrul de elemente de trimis din buffer[ IN datatype] - tipul datelor pentru fiecare element din buffer[ IN dest] - rangul destinaiei[ IN tag] - identificator de mesaj[ IN comm] - comunicatorul[ OUT request] - communication request

Prototipul funciei este urmtorul:int MPI_Issend(void* buf, int count, MPI_Datatype

datatype, int dest, int tag, MPI_Comm comm,MPI_Request *request)

Apelul funciei Irsend:MPI_IRSEND(buf,count,datatype,dest,tag,comm,request)


69/163

69

[ IN buf] - adresa zonei tampon (bufferului) pentru datele de trimis[ IN count] - numrul de elemente de trimis din buffer[ IN datatype] - tipul datelor pentru fiecare element din buffer[ IN dest] - rangul destinaiei[ IN tag] - identificator de mesaj[ IN comm] - comunicatorul[ OUT request] - communication request

Prototipul funciei este urmtorul:int MPI_Irsend(void* buf, int count, MPI_Datatype

datatype,int dest, int tag, MPI_Comm comm,MPI_Request *request)

Observaii:Sistemele de comunicare cu transfer de mesaje sunt n general

nedeterministe, adic nu garanteaz c ordinea n care se transmitmesajele este aceeai cu ordinea n care mesajele sunt recepionate,programatorului revenindu-i sarcina gsirii mecanismelor necesarepentru obinerea unui calcul determinist.

Comunicri colectiveConceptul cheie al comunicrilor colective este acela de a avea un

grup de procese participante. Pentru aceasta biblioteca MPI oferurmtoarele funcii:

bariera - sincronizarea prin barier pentru toi membrii grupului(MPI_Barrier);broadcast - transmiterea de la un membru al grupului ctre ceilalimembri (MPI_Bcast);gather - adunarea datelor de la toi membrii grupului la un singur

membru din grup (MPI_Gather);scatter - mprtierea datelor de la un membru la toi membriigrupului (MPI_Scatter);all gather - o variaie a MPI_Gather n care toi membrii grupuluiprimesc rezultatele, nu numai procesul root (MPI_Allgather);all-to-all scatter/gather - adunarea/mpratierea datelor de la toimembrii grupului ctre toi membrii (MPI_Alltoall o extensie aMPI_Allgather n care fiecare proces trimite date distincte ctrefiecare proces din grup);operaii de reducere adunare, nmulire, min, max, sau funciidefinite de utilizator n care rezultatele sunt trimise la toi membrii

grupului sau numai la un membru.


70/163

70

Observaii:

-Toate funciile sunt executate colectiv (sunt apelate de toateprocesele dintr-un comunicator); toate procesele folosesc aceeaiparametri n apeluri.

-Funiile nu au un identificator de grup ca argument explicit. nschimb avem un comunicator ca argument. Un inter-comunicatornu este permis ca argument n funciile ce realizeaz operaiilecolective dect n implementrile standardului MPI 2.0.

Caracteristicile comunicrilor colective:-Comunicrile colective i cele de tip unu-la-unu nu se vor influena

reciproc.-Toate procesele trebuie sexecute comunicri colective.-Sincronizarea nu este garantat, excepie realiznd doar bariera.-Nu existcomunicri colective neblocante.-Nu existtag-uri.-Bufferele de recepie trebuie sfie exact de dimensiunea potrivit.

BarieraBariera este un mecanism de sincronizare a unui grup de procese.

Dac un proces a fcut apelul MPI_Barrier(com), unde com estecomunicatorul, atunci el va atepta pncnd toate procesele au efectuatacest apel.

Apelul funciei Barrier:

MPI_Barrier( comm )[IN comm] - comunicator

Prototipul funciei este:int MPI_Barrier(MPI_Comm comm )

Difuzia (Broadcast)Funcia MPI_Bcast trimite un mesaj de la procesul cu rangul root

ctre toate procesele din grup, inclusiv procesului root.


71/163

71

Funcia este apelat de toi membrii grupului, folosind acelaiargument pentru comunicator, root. La ieirea din funcie, coninutulbuffer-ului de comunicare al procesului root a fost copiat de toateprocesele.

Apelul funciei Bcast:

MPI_Bcast( buffer, count, datatype, root, comm )

[ INOUT buffer] - adresa de nceput a buffer-ului pentru date[ IN count] - numrul de intrri din buffer[ IN datatype] - tipul datelor din buffer[ IN root] - rangul procesului root care iniiazcomunicarea[ IN comm] - comunicator

Prototipul funciei este urmtorul:int MPI_Bcast(void* buffer, int count, MPI_Datatype

datatype, int root, MPI_Comm comm )

Exemplu 8:

#includevoid main (int argc, char *argv[])

{int rank;double param;MPI_Init(&argc, &argv);MPI_Comm_rank(MPI_COMM_WORLD,&rank);if(rank==5) param=23.0;MPI_Bcast(&param,1,MPI_DOUBLE,5,MPI_COMM_WORLD);printf("P:%d dupa broadcast parametrul este %f\n", rank,param);MPI_Finalize();}

A0

A0

A0

A0

A0

A0

broadcastA0

P0

P1

P3

P2

P4

P5

P0

P1

P3

P2

P4

P5


72/163

72

Comunicarea personalizatunu-la-toi (Scatter)Procesul root trimite coninutul sendbuffer-ului ctre toate procesele

din grup (inclusiv ctre procesul root).

Rezultatul este acelai ca i cum procesul root ar executa noperaii detipsend

MPI_Send(sendbuf+i* sendcount* extent(sendtype), sendcount,sendtype, i,...),

i fiecare proces executo operaie receiveMPI_Recv(recvbuf, recvcount, recvtype, i,...).

Apelul funciei Scatter:MPI_Scatter (sendbuf, sendcount, sendtype, recvbuf,

recvcount, recvtype, root, comm)

[IN sendbuf] - adresa de nceput a zonei buffer-ului pentru datelede trimis

[IN sendcount] - numrul de elemente din buffer[IN sendtype] - tipul datelor din buffer[OUT recvbuf] - adresa buffer-ului de recepie[IN recvcount] - numrul de elemente pentru fiecare recepie n parte[IN recvtype] - tipul datelor din buffer-ul de recepie[IN root] - rangul proceselor care trimite datele[IN comm] - comunicator

Prototipul funciei este urmtorul:MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype

sendtype, void* recvbuf, int recvcount,MPI_Datatype recvtype,int root, MPI_Comm comm)

Observaii:

-ntr-o alt interpretare, funcia Scatter ar nsemna: procesul root

trimite un mesaj cu MPI_Send(sendbuf, sendcount-n,

A0

A1

A3

A2

A4

A5

scatterP0 P0

P1

P3

P2

P4

P5

A0 A1 A2 A3 A4 A5


73/163

73

sendtype, ...). Acest mesaj este mprit n n segmente egale,segmentul i fiind transmis la procesul i din grup i fiecare procesprimete mesajul dupdescrierea anterioar.

-Toate argumentele funciei sunt semnificative numai n procesulroot, n timp ce pentru celelalte procese numai argumentele recvbuf,recvcount, recvtype, root i commsunt semnificative.

-Sendbuffereste ignorat n procesele care nu au rangul root.

Exemplu:

Transmiterea a 100 de ntregi de ctre procesul root ctre fiecareproces din grup (inversul exemplului 8).

MPI_Comm comm;int gsize,*sendbuf;int root, rbuf[100];...MPI_Comm_size( comm, &gsize);sendbuf = (int *)malloc(gsize*100*sizeof(int));

...MPI_Scatter( sendbuf, 100, MPI_INT, rbuf, 100,

MPI_INT, root, comm);

Comunicarea toi-la-unu - Colectarea datelor(Gather)Fiecare proces (inclusiv procesul root) trimite coninutul sendbuffer-

ului ctre procesul root. Procesul root primete mesajele i le stocheazn ordinea rangului.

100 100 100

100 100 100

sendbuf

Procesul root

Toate procesele


74/163

74

Rezultatul este acelai ca i cum fiecare proces (inclusiv procesulroot) ar executa un apel al funciei

MPI_Send(sendbuf, sendcount, sendtype, root, ...)i procesul root ar executa napeluri

MPI_Recv(recvbuf+i*recvcount*extent(recvtype), recvcount,recvtype, i ,...)

unde extent(recvtype)este tipul obinut din apelul MPI_Type_extent( )-vezi help-ul.

Apelul funciei Gather:MPI_Gather( sendbuf,sendcount,sendtype,recvbuf, recvcount,

recvtype, root, comm)

[ IN sendbuf] - adresa de nceput a zonei buffer-ului pentru date[ IN sendcount] - numrul de elemente din buffer[ IN sendtype] - tipul datelor din buffer[ OUT recvbuf] - adresa buffer-ului de recepie (are semnificaie numai

la procesul root)[ IN recvcount] - numrul de elemente pentru fiecare recepie n parte

(are semnificaie numai la procesul root)[ IN recvtype] - tipul datelor din buffer-ul de recepie (are semnificaie

numai la procesul root)[ IN root] - rangul proceselor care recepioneazdatele[ IN comm] - comunicator

Prototipul funciei este urmtorul:int MPI_Gather(void* sendbuf, int sendcount, MPI_Datatype

sendtype, void* recvbuf, int recvcount,MPI_Datatype recvtype, int root,MPI_Comm comm)

A0

A1

A3

A2

A4

A5

atherP0 P0

P1

P3

P2

P4

P5

A0 A1 A2 A3 A4 A5


75/163

75

Observaii:

-ntr-o altintrepretare, funcia Gather ar nsemna: n mesaje trimisede procesele din grup sunt concatenate n ordinea ranguluiproceselor i mesajul rezultat este primit de procesul root.

-Buffer-ul de recepie este ignorat pentru procesele care nu au rangulroot.

-Argumentul recvcount la procesul root indic dimensiunea datelorprimite de la fiecare proces i nu numrul total de date primite.

Exemplu: Recepia a 100 ntregi de la fiecare proces din grup

MPI_Comm comm;int gsize,sendarray[100];int root, *rbuf;...

MPI_Comm_size( comm, &gsize);rbuf = (int *)malloc(gsize*100*sizeof(int));MPI_Gather( sendarray, 100, MPI_INT, rbuf,100,

MPI_INT, root, comm);

Exemplu:

Exemplul de mai sus modificat numai procesul root alocmemoriepentru buffer-ul de recepie.

MPI_Comm comm;int gsize,sendarray[100];int root, myrank, *rbuf;

100 100 100

100 100 100

recvbuf

Procesul root

Toate procesele


76/163

76

...MPI_Comm_rank( comm, myrank);if ( myrank == root) {

MPI_Comm_size( comm, &gsize);rbuf = (int *)malloc(gsize*100*sizeof(int));}

MPI_Gather( sendarray, 100, MPI_INT, rbuf, 100,MPI_INT, root, comm);

Operaii de reducereFunciile pe care le vom prezenta n continuare realizeazoperaii de

reducere peste toi membrii unui grup.Operaiile de reducere implic date distribuite peste un grup de

procese. Funciile de reducere globale sunt urmtoarele: o operaie dereducere care ntoarce rezultatul la un singur nod, o operaie carentoarce rezultatul la toate nodurile i o operaie de scanare (prefixulparalel). n plus exist o operaie de tipul reduce-scatter care combinfuncionalitatea operaiei de reducere i a operaiei scatter.

Operaiile care se realizeaz asupra datelor pot fi predefinite saudefinite de utilizator.

Funcia MPI_Reducecombinelementele din buffer-ul de intrare alfiecrui proces din grup, folosind operaia op, i ntoarce rezultatul nbuffer-ul de ieire al procesului root.

+reduce();

data

reduce();

data

reduce();

data

buff

P0 P1 Pn-1

A0 B0 C0

A1 B1 C1

A2 B2 C2

A0+A1+A2 B0+B1+B2 C0+C1+C2reduceP0

P1

P2

P0

P1

P2


77/163

77

Apelul funciei Reduce:

MPI_Reduce(sendbuf,recvbuf,count,datatype,op,root,comm)

[IN sendbuf] - adresa buffer-ului de trimitere[OUT recvbuf] - adresa buffer-ului de recepie (are semnificaie numai

pentru procesul root)

[IN count] - numrul de elemente din buffer-ul de trimitere[IN datatype] - tipul datelor din buffer-ul de trimitere[IN op] - operaia de reducere[IN root] - rangul procesului root[IN comm] - comunicator

Prototipul funciei este urmtorul:int MPI_Reduce (void* sendbuf, void* recvbuf, int count,

MPI_Datatype datatype, MPI_Op op, int root,MPI_Comm comm)

Standardul MPI include variante pentru fiecare operaie de reduceren care rezultatul este returnat tuturor proceselor din grup ca n figura de

mai jos ( MPI_Allreduce). De asemenea trebuie ca toate procesele careparticipla aceste operaii sprimeascacelai rezultat.

Apelul funciei Allreduce:MPI_Allreduce(sendbuf,recvbuf,count,datatype,op, comm)

[IN sendbuf] - adresa buffer-ului de trimitere[OUT recvbuf] - adresa buffer-ului de recepie[IN count] - numrul de elemente din buffer-ul de trimitere[IN datatype] - tipul datelor din buffer-ul de trimitere[IN op] - operaia de reducere[IN comm] - comunicator

Prototipul funciei este urmtorul:

A0 B0 C0

A1 B1 C1

A2 B2 C2

A0+A1+A2 B0+B1+B2 C0+C1+C2

A0+A1+A2 B0+B1+B2 C0+C1+C2

A0+A1+A2 B0+B1+B2 C0+C1+C2

allreduceP0

P1

P2

P0

P1

P2


78/163

78

int MPI_Allreduce (void* sendbuf, void* recvbuf, intcount, MPI_Datatype datatype, MPI_Op op, MPI_Commcomm)

Reduce-scatter este varianta n care rezultatul este transmis folosindscatter ctre toate procesele din grup.

Apelul funciei Allreduce:MPI_Reduce_scatter(sendbuf,recvbuf,recvcounts,datatype,op,

comm)

[ IN sendbuf] - adresa buffer-ului de trimitere[ OUT recvbuf] - adresa buffer-ului de recepie[ IN recvcounts] - ir de ntregi care specificnumrul de elemente din

rezultatul distribuit ctre fiecare proces. Acesta trebuiesa fie identic la toate apelurile din procese.

[ IN datatype] - tipul datelor din buffer-ul de trimitere[ IN op] - operaia de reducere[ IN comm] - comunicator

Prototipul funciei este urmtorul:int MPI_Reduce_scatter (void* sendbuf, void* recvbuf, int

*recvcounts, MPI_Datatype datatype, MPI_Op op,MPI_Comm comm)

Operaii de reducere predefinite

Urmtoarele operaii sunt predefinite pentru operaia de reducere:

MPI_MAX maximumMPI_MIN minimumMPI_SUM sumMPI_PROD produsMPI_LAND i logic

MPI_BAND i pe bii

A0 B0 C0

A1 B1 C1

A2 B2 C2

A0+A1+A2

B0+B1+B2

C0+C1+C2

reduce-scatterP0

P1

P2

P0

P1

P2


79/163

79

MPI_LOR sau logicMPI_BOR sau pe biiMPI_LXOR xor logicMPI_BXOR xor pe biiMPI_MAXLOC max value and locationMPI_MINLOC min value and location

Operaii de reducere definite de utilizatorDefinirea unei operaii de ctre utilizator se face folosind funcia

MPI_Op_create:

Apelul funciei este:MPI_Op_create( function, commute, op)

[IN function] 1. funcia definitde utilizator[IN commute] 2. daca este comutativtrue, altfel

false[OUT op] 3. operaia

Prototipul funciei este urmtorul:int MPI_Op_create (MPI_User_function *function, int

commute, MPI_Op *op)

Operaiile definite de utilizator se presupun a fi asociative. Daccommute = true, atunci operaia trebuie sfie i comutativi asociativ.Dac commute = false, atunci ordinea operanzilor este fix i estedefinit s fie ascendent, n ordinea rangului proceselor, pornind cuprocesul zero. Ordinea evalurii poate fi schimbat, avnd avantajul

asociativitii operaiei. Dac commute =true atunci ordinea evaluriipoate fi schimbat, avnd avantajele comutativitii i asociativitii.

function este funcia definitde utilizator i trebuie saiburmtorulprototip:

void MPI_User_function( void *invec, void *inoutvec,int *len, MPI_Datatype *datatype);

Exemplu:Un exemplu de implementare ineficienta funciei MPI_Reduce:

if (rank > 0) {

MPI_Recv(tempbuf, count, datatype, rank-1,...)


80/163

80

User_reduce( tempbuf, sendbuf, count, datatype)}if (rank < groupsize-1) {

MPI_Send( sendbuf, count, datatype, rank+1, ...)}/*avem raspunsul n procesele groupsize-1 i le

trimitem la root*/

if (rank == groupsize-1) {MPI_Send( sendbuf, count, datatype, root, ...)

}if (rank == root) {

MPI_Recv(recvbuf, count, datatype, groupsize-1,...)}

Operaia de reducere ncepe, secvenial, de la procesul 0 la procesulgroup_size-1. Aceast ordine este aleas pentru a se respecta ordineaunui operator ne-comutativ definit de funcia User_reduce().

O implementare mai eficient este obinut folosind avantajulasociativitii. Comutativitatea poate fi folosit pentru a avantaja

cazurile n care argumentul commuteal MPI_Op_createeste true.Operaiile de reducere predefinite pot fi implementate ca o bibliotec

de operaii definite de utilizator.Cnd nu mai este nevoie de operaia definit de utilizator trebuie

eliberatmemoria. Acest lucru se face folosind funcia MPI_Op_free cese apeleazastfel:

MPI_Op_free( op)

[ IN op] operaia

Prototipul funciei este urmtorul:int MPI_op_free ( MPI_Op *op)

Exemplu:

Calculul produsului unui ir de numere complexe (vezi i anexa):

typedef struct {double real,imag;

} Complex;

/* funcia definitde utilzator */void myProd( Complex *in, Complex *inout, int *len,MPI_Datatype *dptr){

int i;


81/163

81

Complex c;

for (i=0; i< *len; ++i) {c.real = inout->real*in->real -

inout->imag*in->imag;c.imag = inout->real*in->imag +

inout->imag*in->real;*inout = c;

in++; inout++;}

}.../* fiecare proces are un ir de 100 numere complexe */

Complex a[100], answer[100];MPI_Op myOp;MPI_Datatype ctype;

/* se spune MPI cum este definit tipul Complex */MPI_Type_contiguous( 2, MPI_DOUBLE, &ctype );MPI_Type_commit( &ctype );

/*se creazoperaia definitde utilizator pentru

nmulire*/MPI_Op_create( myProd, True, &myOp );

MPI_Reduce( a, answer, 100, ctype, myOp,root,comm );

/*n acest punct, raspunsul, care constn 100 numerecomplexe este n procesul root*/

Calculul prefixelorPentru calculul prefixului paralel ca operaie de reducere a datelor

distribuite peste un grup de procese, standardul MPI introduce funciaMPI_Scan. Operaia ntoarce n buffer-ul recvbufa procesului cu rangul

i, reducerea valorilor din buffer-ul sendbufa proceselor cu rangurile 0,, i (inclusiv vezi figura). Tipul operaiilor suportate, precum ilimitrile legate desendbuf i recvbufsunt cele ale MPI_Reduce.

A0 B0 C0

A1 B1 C1

A2 B2 C2

A0 B0 C0

A0+A1 B0+B1 C0+C1

A0+A1+A2 B0+B1+B2 C0+C1+C2

scanP0

P1

P2

P0

P1

P2


82/163

82

Apelul funciei este:MPI_Scan( sendbuf, recvbuf, count, datatype, op, comm )

[ IN sendbuf] - adresa buffer-ului de trimitere[ OUT recvbuf] - adresa buffer-ului de recepie[ IN count] - numarul de elemente din buffer-ul de trimitere[ IN datatype] - tipul datelor din buffer-ul de trimitere[ IN op] - operaia[ IN comm] - comunicator

Prototipul funciei este urmtorul:int MPI_Scan(void* sendbuf, void* recvbuf, int count,

MPI_Datatype datatype, MPI_Op op, MPI_Comm comm )

Operaia a fost definit ca fiind inclusive scan adic calcululprefixului se face inclusiv pentru procesul cu rangul i. O alternativ ar fidefinirea operaiei ntr-o manier exclusiv, cnd rezultatul pentrurangul i va include datele pn la rangul i-1. Ultima variant pare a fimai avantajoas deoarece o operaie de tipul inclusive scan poate firealizat dintr-o operaie de tip exclusive scan fr comunicaresuplimentar. Datorit apariiei unor complicaii (scrierea operaiilordefinite de utilizator) la scrierea operaiei de tip inclusive scan caoperaie de tip exclusive scan, acestea fiind lsate n grijaprogramatorului, s-a renunat la varianta exclusive scan.

Corectitudinea operaiilor colective

Un program scris corect n MPI trebuie s apeleze comunicrilecolective astfel nct s nu apar blocaje, indiferent dac comunicrile

sunt sincronizate sau nu. n urmtorul exemplu este artat un mod defolosire a operaiilor colective care poate duce la blocare.

Exemplu: Utilizare greit:

switch(rank) {case 0:

MPI_Bcast(buf1, count, type, 0, comm);MPI_Bcast(buf2, count, type, 1, comm);break;

case 1:MPI_Bcast(buf2, count, type, 1, comm);MPI_Bcast(buf1, count, type, 0, comm);

break;


83/163

83

}

Observaie:Se presupune c grupul de comunicare este {0,1}. Dou procese

execut broadcast n ordine invers. Dac operaiile sunt sincronizateapare blocaj. Operaiile colective trebuie executate n aceeai ordine detoi membrii grupului de comunicare.

Exemplu:Utilizare greit:

switch(rank) {case 0:

MPI_Bcast(buf1, count, type, 0, comm0);MPI_Bcast(buf2, count, type, 2, comm2);break;

case 1:MPI_Bcast(buf1, count, type, 1, comm1);MPI_Bcast(buf2, count, type, 0, comm0);break;

case 2:

MPI_Bcast(buf1, count, type, 2, comm2);MPI_Bcast(buf2, count, type, 1, comm1);break;

}

Observaii:-Presupunem c grupul de comunicare comm0 este {0,1}, comm1

este {1,2} i comm2 este {2,0}. Daca operaia broadcast estesincronizat, atunci apare o dependenciclic: broadcast n comm2se terminnumai dupbroadcast din comm0; broadcast n comm0se terminnumai dupbroadcast din comm1; i broadcast n comm1se termin numai dup broadcast din comm2. Astfel aplicaia seblocheaz.

-Operaiile colective trebuiesc executate astfel nct s nu apardependene ciclice.

Exemplu: Utilizare greit:switch(rank) {

case 0:MPI_Bcast(buf1, count, type, 0, comm);MPI_Send(buf2, count, type, 1, tag, comm);break;

case 1:MPI_Recv(buf2, count, type, 0, tag, comm,

status);MPI_Bcast(buf1, count, type, 0, comm);break;


84/163


85/163

85

Exemplu:Folosirea operaiilor de reducere predefinite

MPI_MAXLOC i MPI_MINLOC:

#include /* Rulare pentru 16 procese */struct {

double value;int rank;

} in, out;void main (int argc, char *argv[]){int rank;int root;MPI_Init(&argc, &argv);MPI_Comm_rank(MPI_COMM_WORLD,&rank);

in.value=rank+1;in.rank=rank;root=7;MPI_Reduce(&in,&out,1,MPI_DOUBLE_INT,MPI_MAXLOC,root,

MPI_COMM_WORLD);if(rank==root)

printf("PE:%d max=%lf la rangul %d\n", rank,out.value, out.rank);

MPI_Reduce(&in,&out,1,MPI_DOUBLE_INT,MPI_MINLOC,root,MPI_COMM_WORLD);

if(rank==root)printf("PE:%d min=%lf la rangul %d\n", rank,out.value, out.rank);

MPI_Finalize();}

O a doua execuie posibil

O primexecuie posibilProces


86/163

86

Exemplu:#include typedef struct {double real,imag;} complex;

void cprod(complex *in, complex *inout, int *len,MPI_Datatype *dptr){int i;complex c;for (i=0; i


87/163

87

dorit s se poat transmite date care nu sunt omogene, cum suntstructurile, sau care nu sunt continue n memorie, ca de exemplu anumiteelemente dintr-un vector.

Pentru rezolvarea acestor probleme, MPI pune la dispoziie doumecanisme: utilizatorul poate defini tipuri de date derivate, care pot fi utilizate n

Comunicrile cu MPI derived datatype; un proces poate mpacheta explicit datele necontinui ntr-un buffercontinuu i apoi sl trimit, iar procesul care primete datele poatedesface datele primite n buffer i sle stocheze n locaii necontinuepack/unpack.

Constructori pentru tipuri de date

Cel mai simplu constructor este MPI_TYPE_CONTIGUOUS carepermite multiplicarea unui tip de date n locaii continue.

Apelul funciei Contiguous:MPI_Type_contiguous (count, oldtype, newtype)

[IN count] - numrul de copii (ntreg pozitiv)[IN oldtype] - tipul de datiniial[OUT newtype] - tipul de datnou

Prototipul funciei este urmtorul:int MPI_Type_contiguous(int count, MPI_Datatype

oldtype,MPI_Datatype *newtype)

Observaie:

newtypereprezinttipul de date obinut prin concatenarea a countcopii ale oldtypeca n figura de mai jos:


88/163

88

Funcia MPI_TYPE_VECTOR este un constructor mai general carepermite multiplicarea unui tip de date n locaii care constau n blocuriaflate la distane egale (vezi figura urmtoare). Fiecare bloc este obinutprin concatenarea unui acelai numr de copii ale tipului de date oldtype.Spaiul dintre blocuri este multiplu de dimensiunea tipului de dateoldtype.

Apelul funciei Vector:MPI_Type_vector ( count, blocklength, stride, oldtype,

newtype)[IN count] -numrul de blocuri[IN blocklength] -numrul de elemente din fiecare bloc[IN stride] -spaiul dintre blocuri, msurat n numrul

de elemente (ntreg) fiecrui bloc[IN oldtype] - tipul de datvechi[OUT newtype] - tipul de datnou

Prototipul funciei este urmtorul:int MPI_Type_vector(int count, int blocklength, int

stride, MPI_Datatype oldtype, MPI_Datatype

*newtype)

oldt e

count =

newt e

oldt e

count = 3, blocklen th = 2,

newt e


89/163

89

Funcia MPI_TYPE_HVECTOR este identiccuMPI_TYPE_VECTOR, cu excepia faptului cpasul este dat n bytes inu n elemente (vezi figura urmtoare).

Apelul funciei Hvector:MPI_ Type_hvector ( count, blocklength, stride,

oldtype, newtype)[IN count] - numrul de blocuri[IN blocklength] - numrul de elemente din fiecare bloc[IN stride] - numrul de bytes dintre blocuri[IN oldtype] - tipul de datiniial[OUT newtype] - tipul de datnou

Prototipul funciei este urmtorul:int MPI_Type_hvector(int count, int blocklength, MPI_Aint

stride,MPI_Datatype oldtype, MPI_Datatype *newtype)

Exemplu:

struct Partstruct{int class; /* clasa particulei */double d[6]; /* coordonatele */char b[7]; /* informaii suplimentare*/

};

void SendParticles(MPI_Comm comm){struct Partstruct particle[1000];int dest, tag;MPI_Datatype Locationtype;

MPI_Type_create_hvector(1000, 3, sizeof(structPartstruct),MPI_DOUBLE, &Locationtype);

MPI_Type_commit(&Locationtype);MPI_Send(particle[0].d,1,Loationtype, dest, tag, comm);...

}

oldt e

count = 3, blocklen th = 2,

newt e


90/163

90

Funcia MPI_TYPE_INDEXED permite multiplicarea unui tip dedate ntr-o secvende blocuri (fiecare bloc este concatenat la tipul dedate oldtype), iar fiecare bloc poate conine un numr diferit de copii ipoate avea un deplasament diferit (vezi figura urmtoare). Toatedeplasamentele blocurilor sunt multipli ai dimensiunii tipului de dateoldtype.

Apelul funciei Indexed:MPI_ Type_indexed ( count, array_of_blocklengths,

array_of_displacements, oldtype,newtype)

[IN count] - numrul de blocuri; de asemenea inumrul de intrri narray_of_displacementsiarray_of_blocklengths

[IN array_of_blocklengths] - numrul de elemente din fiecare bloc[IN array_of_displacements] - deplasamentul pentru fiecare bloc,

msurat ca numr de elemente[IN oldtype] - tipul de d

Indrumar Laborator ALCP

Documents

Transcript of Indrumar Laborator ALCP