ALGORITMUL FLOYD-WARSHALL

PREZENTAREA ALGORITMULUI PARALEL IMPLEMENTAT ÎN C FOLOSIND MPI

2

INTRODUCERE

Algoritmul Floyd-Warshall este folosit în diverse domenii des întalnite, de la controlul avioanelor de pe un anumit aeroport până la jocuri informatice, rolul principal fiind acela de găsire a drumului de cost minim între un obiect principal și o tintă anume.

Fie G=(V, E) un graf orientat, unde V are n elemente (n noduri) și E are m elemente (m muchii) memorat prin matricea ponderilor. Se cere ca pentru două noduri x,y citite să se determine lungimea minimă a drumului de la nodul x la nodul y. Prin lungimea unui drum înțelegem suma costurilor arcelor care îl alcatuiesc.

3

PAȘII ALGORITMULUI• Se genereaza matricea costurilor

10

1

2

3 4

52

31

8

1 2 3 4 5

0 2 ∞ ∞ ∞

∞ 0 3 ∞ ∞

∞ ∞ 0 1 8

10

∞ ∞ 0 ∞

5 ∞ ∞ ∞ 0

• Se încearcă pentru oricare pereche de noduri i,j să se obțină drumuri mai scurte prin noduri intermediare k. Acest lucru se determină comparând “lungimea” lanțului a[i,j] cu lungimea lanțului care trece prin k( k luând valori de la 1 la n) și dacă: a[i,j] > a[i,k]+a[k,j] atunci se atribuie: a[i,j]:= a[i,k]+a[k,j]

5

4

PSEUDOCOD SECVENȚIAL

Input: n → numărul de arce;

a[0..n-1, 0..n-1] → matricea de cost;

Output: Matricea a conținând cel mai scurt drum dintre două noduri.

for k ← 0 to n-1 for k ← 0 to n-1 for j ← 0 to n-1

temp = a[i][k] + a[k][j] if temp < a[i][j] then

a[i][j] ← temp endfor endforendfor

5

PSEUDOCOD SECVENȚIAL

Pseudocodul anterior poate fi ușor de modificat pentru a salva și drumurile efective. Reconstituirea drumurilor se face în mod recursiv.

for k ← 0 to n-1 for k ← 0 to n-1 for j ← 0 to n-1

temp = a[i][k] + a[k][j] if temp < a[i][j] then

a[i][j] ← temppath[i][j] ← k

endfor endforendfor

6

COMPLEXITATEA ALGORITMULUI SECVENȚIAL

• numărul maxim de iterații → N• fiecare iterație → pentru N noduri• pentru fiecare nod → N-1 noduri intermediare

Algoritmul are complexitatea de calcul în timp: O(N3)

7

ALGORITMUL PARALEL

În implementarea paralelă a algoritmului Floyd-Warshall vom avea de luat în considerare găsirea unor soluții pentru:

• Partiționarea algoritmului

• Comunicarea dintre procese

• Maparea pe coloane sau pe rânduri

• Deadlocks

PARTIȚIONARE

• Algoritmul secvențial execută aceeași operație de n3 ori• În algoritmul paralel aplicăm domain decomposition și împărțim

matricea a în cele n2 elementele ale sale.• Fiecare element va avea asociat câte un task

Task-uri

a[i,j ] este obținut din procesul corespunzător lui i,j ( i * n +j)

ex: a[2,3] obținut în urma procesului 2*5 + 3 = 13

9

PARTIȚIONARE

• Algoritmul secvențial execută aceeași operație de n3 ori.• În algoritmul paralel fiecare din cele n2 elementele ale

matricei a va avea asociat câte un task. Vom aplica domain decomposition.

a) Prelucrăm a[2, 3] b) Pentru k = 1, accesăm a[1, 3] si a[2, 1]

c) a[k, x] trimite valoarea sa catre a[x, y]

d) a[x, k] trimite valoarea sa catre a[y, x]

10

COMUNICAREA DINTRE PROCESE

• Prelucrarea elementului a[i, j] necesită valorile elementelor a[i, k] si a[k, j].

• Astfel la o iterație k:• fiecare element din rândul k transmite valoarea sa elementelor din

coloana în care se află;• fiecare element din coloana k transmite valoarea sa elementelor

din rândul în care se află;• Putem actualiza toate elementele din a simultan în aceeași iterație k,

fiindcă actualizarea lui a[i, j] nu depinde de actualizarea elementelor a[i, k] si a[k, j]:• a[i, k] := min(a[i, k], a[i, k] + a[k, k])• a[k, j] := min(a[k, j], a[k, k] + a[k, j])

11

MAPAREA PE COLOANE SAU PE RÂNDURI

Mapare pe randuri Mapare pe coloane

Indiferent de varianta aleasă, broadcast-ul dintre două procese va dura:ceil(log p) * (λ + n/β)

Maparea pe rânduri este mai ușoară și mai eficientă!

DeadlockDeadlock: atunci când un proces așteaptă după o condiție care nu va fi niciodată adevărată. Exemplu de situații:

• 2 procese: amândouă primesc înainte să trimită;• Send tag-ul nu este acelasi cu receive tag ;

float a, b, c;int mpiRank; // Rang-ul procesului MPIMPI_Status status;...if (mpiRank == 0) {

MPI_Recv(&b, 1, MPI_FLOAT, 1, 0, MPI_COMM_WORLD, &status);MPI_Send(&a, 1, MPI_FLOAT, 1, 0, MPI_COMM_WORLD);

}else if (mpiRank == 1) {

MPI_Recv(&a, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD, &status);MPI_Send(&b, 1, MPI_FLOAT, 0, 0, MPI_COMM_WORLD);

}

13

IMPLEMENTAREA PARALELĂ

void( compute_shortest_paths( int id, int p, dtype **a, int n){ int i,j,k;int offset; /*local index of broadcast row*/int root; /*process controlling row to be bcast*/int *tmp; /*holds the broadcast row*/

tmp =(dtype*) malloc (n*sizeof(dtype));for (k = 0; k < n; k++){ root = BLOCK_OWNER(k,p,n); if (root == id) {

offset = k* BLOK_LOW(id,p,n);for(j = 0; j < n; j++)tmp[j] = a[offset][j];

} MPI_BCAST(tmp, n, MPI_TYPE, root, MPI_COMM_WORLD); for( i = 0; i < BLOCK_SIZE(id, p, n); i++) for (j = 0; j < n; j++) a[i][j]=MIN(a[i][j],a[i][k]+tmp[j]);}

•

14

ANALIZAREA PERFORMANȚEI

• Cele două loop-uri interne: Θ(n2 / p)

• Broadcast către p procesoare: Θ(n log p)

• Loop-ul exterior: Θ(n)

• Complexitate finală: Θ(n * (n log p + n2 / p)) =Θ(n3 / p + n2 log p)

15

ANALIZAREA TIMPULUI DE EXECUȚIE(1)

)/4(log/ npnnpnn

Iterations of outer loopIterations of middle loop

Cell update time

Iterations of outer loop

Messages per broadcastMessage-passing time

Iterations of inner loop

16

ANALIZAREA PERFORMANTEI

Timpul total de execuție este estimativ, deoarece se ignoră faptul că pot fi suprapuneri între procesare și comunicare:

Send Așteaptă Procesează

P0

P1

P2

P3

17

ANALIZAREA PERFORMANTEI

• Se observă în figura anterioară că spre exemplu procesul 1 nu poate să își updateze porțiunea lui de matrice până când nu primește rândul 0 de la procesul 0.

• Din acest motiv, după fiecare iterație, fiecare proces așteaptă aceeași durată de timp: ceil(log p) * λ

18

ANALIZAREA TIMPULUI DE EXECUȚIE(2)

Iterations of outer loopIterations of middle loop

Cell update time

Iterations of outer loop

Messages per broadcastMessage-passing time

Iterations of inner loop

/4loglog/ nppnnpnn Message transmission

19

Performanța prezisă vs. performanța actuală

Timpul de executie (sec)

Procesul Prezis Actual

1 25.54 25.54

2 13.02 13.89

3 9.01 9.60

4 6.89 7.29

5 5.86 5.99

6 5.01 5.16

7 4.40 4.50

8 3.94 3.98

ANALIZAREA PERFORMANȚEI

BIBLIOGRAFIE• Cormen, Thomas H., Leiserson, Charles E., Rivest

, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. Section 26.2, "The Floyd–Warshall algorithm", pp. 558–565;

20