Algoritmi paraleli și distribuiți - lucrări laborator

Inmultirea a doua matrici.

Presupunem a si b de tip Mn*n .

Declaram a, b si c de tip double si c=a*b.

Algoritmul secvential de inmultire a doua matrici este:

1. for [ i = 0 to n-1 ]

2. for [j = 0 to n-1 ]

3. { c[i, j] = 0.0 ;

4. for [k = 0 to n-1]

5. c[i,j] = c[i, j] + a[i, k] * b[k, j];

6. }

Definitie: doua operatii se pot executa in paralel daca sunt independente.

Fie ,, o " o operatie.

RS(o) este multimea variabilelor utilizate in o si nemodificate de o.

WS(o) este multimea variabilelor modificate de o (si eventual utilizate).

Doua operatii o1 si o2 sunt independente daca:

a) WS(o1) ? WS(o2) = ?

b) RS(o1) ? RS(o2) = ?

Ex.

Instructiunea o : x = y + x + z

RS(o) = {y , z}

WS(o) = {x}

Obs. Variabilele utilizate sunt cele care apar in partea dreapta a atribuirii.

Revenind la exemplul de mai sus, cel cu inmultirea matricelor, observam ca pentru linia 5 de cod avem:

RS(5) = {a[i, k] , b[k, j]} iar WS(5) = {c[i, j]}

Notatie: ,, co ,, pentru a simula executia paralela. co - proces

co [k=0 to n-1]

c[i, j] = c[i, j] + a[i, k]*b[k, j]

oc

Insa se poate observa ca operatiile de la randul 5 nu sunt independente deoarece:

WS(5, i0) ? WS(5, j0) = {c[i, j]}

Atunci operatiile care pot fi paralelizate sunt:

co [ i = 0 to n-1 ] (se vor calcula in paralel liniile matricii c)

for [j = 0 to n-1 ]

{ c[i, j] = 0.0 ;

for [k = 0 to n-1]

c[i,j] = c[i, j] + a[i, k] * b[k, j];

}

Adica: procesul 0 va calcula linia 0, ... procesul i va calcula linai i ,...procesul n-1 va calcula linia n-1.

Sau presupunem ca avem n2 procese care fiecare calculeaza un element al matricii c.

co [ i = 0 to n-1 , j = 0 to n-1 ]

{ c[i, j] = 0.0 ;

for [k = 0 to n-1]

c[i,j] = c[i, j] + a[i, k] * b[k, j];

}

Algoritmi paraleli si distribuiti - lucrari laborator