Algoritmi paraleli şi distribuiţi

V1

Proba I
1. Cum se numeşte toplogia de comunicare definită mai jos?
• Mulţimea nodurilor V este organizată sub forma unui tablou unidimensional de dimensiune n, prin intermediul unei
funcţii de indexare I : V → L = 0, 1, ..., n − 1.
• Dacă se notează cu Vi = I −1 (i), nodul Vi este conectat cu nodurile Vi−1 şi Vi+1 .
2. Ce lipseşte din taxonomia lui Flynn, ı̂n enumerarea următoare?
• SISD Single Instructuction / Single Data stream (o singură instrucţiune / un singur flux de date);
• MISD Multiple Instructuctions / Single Data stream (mai multe instrucţiuni / un singur flux de date);
3. Un registru de memorie este caracterizat prin:
• valoarea care poate fi memorată ı̂n registru;
• operaţiile care pot fi efectuate asupra conţinutului registrului
• valoarea aflată ı̂n registru după fiecare operaţie.
• ???
4. Care sunt modelele arhitecturale de calcul distribuit?
5. În funcţie de accesul concurent permis, maşinile PRAM pot fi de tipul
• EREW (Exclusive-Read,Exclusive-Write),
• ???
6. O arhitectură sistolică este
• compusă din celule computaţionale de acelasi tip sau ???,
• interconectate regulat prin conexiuni locale.
7. Care este definiţia eficienţei unui algoritm paralel?
8. Algoritmul de mai jos realizează o comunicare pe hipercub. Cum se numes, te această comunicare?
• Notat, ii:
– H este un hipercub cu d dimensiuni.
– M este un mesaj.
– i este identificatorul unităt, ii de procesare situate ı̂n nodul i al hipercubului H.
• Premise:
– Init, ial, mesajul M este memorat de unitatea de procesare plasate ı̂n nodul 0 al hipercubului H.

C OMUNICARE PE H IPERCUB (H, d, i, M)

1 masca ← 2d − 1 /* init, ializeaza cu 1 toti bitii mastii */
2 for k ← d − 1 downto 0
3 do masca ← masca XOR 2k ; /* seteaza pe 0 al k-lea bit al mastii */
4 if (i AND masca) = 0
5 then /* daca ultimii k biti sunt 0 */
6 if (i AND 2k ) = 0
7 then destinatie ← i XOR 2k ;
8 trimite M la destinatie;
9 else sursa ← i XOR 2k ;
10 primeste M de la sursa.

1
 9. Algoritmul de mai jos ar trebui să realizeaze o difuzie ”tot, i la unu” pe un arbore. Ce lipseşte?

• Premise:
– Iniţial, unitatea de procesare pi deţine mesajul Mi , care urmează a fi transmis spre rădăcină.

cod pi = frunza
DIFUZIE TOTI LA UNU PE ARBORE(T, pi , Mi )
1 trimite Mi catre parinte;
2 termina executia.

cod pi = nod interior

DIFUZIE TOTI LA UNU PE ARBORE(T, pi , Mi )
1 asteapta primirea valorilor Mi0 , Mi1 , . . . , Mik−1 de la f ii;
2 dupa primire, calculeaza Mi ← f (Mi , Mi0 , Mi1 , . . . , Mik−1 );
3 termina executia.

cod pr
DIFUZIE TOTI LA UNU PE ARBORE(T, pr , Mr )
1 asteapta primirea valorilor Mr0 , Mr1 , . . . , Mrk−1 de la f ii;
2 dupa primire, calculeaza Mr ← f (Mr , Mr0 , Mr1 , . . . , Mrk−1 );
3 termina executia.

10. Algoritmul paralel de comprimare este incomplet. Ce lipseşte?

• Notat, ii:
– A[0..2n − 1] este un tablou de dimensiune 2n = 2m+1 .
• Premise:
– Datele de intrare sunt memorate ı̂n tabloul A[0..2n − 1], ı̂n locat, iile A[n], A[n + 1], . . . , A[2n − 1].

C OMPRIM I TERATIV(A, ⊕)
1 for all j : 2k ≤ j ≤ 2k+1 − 1
2 do in parallel
3 A[ j] ← A[2 j] ⊕ A[2 j + 1];

11. Fie S = [a0 , a1 , . . . , an−1 ] o secventă bitonă,

• S1 = [min{a0 , a n2 }, min{a1 , a n2 +1 }, . . . min{a 2n −1 , an−1 }] şi

• S2 = [max{a0 , a n2 }, max{a1 , a n2 +1 }, . . . max{a n2 −1 , an−1 }]
• Secvenţele S1 si S2 au proprietăţile următoare:
– ???
– ???

12. Ce lipses, te ı̂n procedura de aliniere init, ială din algoritmul lui Cannon?
A LINIERE I NITIALA(M1 , M2 , n, q, pi, j )
1 for k ← 1 to i
2 do trimite M1 catre pi, j 1
3 for k ← 1 to j
4 do primeste M2 de la pi⊕1, j

13. Înlocuiţi ??? cu expresia care corespunde pasului de eliminare din prima fază a algoritmului parelel pentru rezolvarea
sistemelor de ecuaţii liniare prin metoda lui Gauss:

• Se consideră un sistem format din n unităţi de procesare, p0 , p1 , . . . , pn−1 .

• Fiecare unitate de procesare pi , i ∈ {0, 1, . . . , n − 1}, dispune, ı̂n memoria locală, de coeficient, ii ecuatiei a-i-a (linia i
a tabloului A plus B[i]).
A[0, j]
• În prima fază, unitatea de procesare p0 execută pasul de imparţirea cu A[0, 0]: A[0, j] = A[0,0] , j = 0, . . . , n − 1. Apoi
trimite A[0, j], j = 0, 1, . . . , n − 1 celorlalte unităţi de procesare, după care, fiecare unitate de procesare pi , i = 1 . . . , n −
1 execută pasul de eliminare: A[i, j] = ???

2
 14. Înlocuiţi ??? pentru ca algoritmul de colorare a muchiilor unui arbore să fie complet. Culorile utilizate se notează cu a
0,1,...,∆ − 1.
(a) Se transformă arborele T = (V, E) ı̂ntr-un arbore cu rădăcină
(b) Pentru fiecare vârf v se determină părintele s, i fii.
(c) Pentru fiecare vârf v se colorează muchiile (v, f iui (v)) cu culoarea i ≥ 1.
(d) Pentru fiecare vârf v se calculează valoarea f (v) = ???; valoarea f (v), se atribuie muchiei (părinte(v), v).

15. Algoritmul de mai jos determină liderul ı̂ntr-un sistem distribuit cu topologia de comunicare reprezentată printr-un graf
oarecare. Care este metoda utilizată?
• Notat, ii:
– idi reprezintă identificatorul unităt, ii de procesare pi .
– Ri memorează mesajele recepţionate de unitatea de procesare pi ı̂ntr-o rundă.
– max idi memorează cel mai mare identificator cunoscut de pi ..
– statuti memorează starea finală a unităt, ii de procesare pi (lider sau non lider).
• Premise:
– Init, ial lider = necunoscut s, i max idi = idi .

A LGORITM A LEGERE L IDER(G, d, pi , max idi , statuti )

1 for runda ← 1 to d − 1
2 do for each (m) in Ri
3 do if max idi < m
4 then max idi ← m
5 trimite max idi vecinilor
6 if max idi = idi
7 then statuti ← lider
8 else statuti ← non − lider

16. Excluderea mutuala realizată cu regiştri binari test&set este cu flamânzire (lockout) ?

Baza = 2p

Proba II
1. Topologia inel : definiţie (1p), exemplu (1p).

2. Algoritmul lui Cannon pentru ı̂nmulţirea matricelor pătratice: pseudocod comentat (3p), exemplu de execuţie (2p), com-
plexitate (1p).

Baza = 2p