Algoritmi Paralleli e Distribuitia.a. 2008/09

Lezione del 06/03/2009

Prof.ssa ROSSELLA PETRESCHI a cura del Dott. SAVERIO CAMINITI

Algoritmi Paralleli e Distribuiti a.a. 2008/09 2

Interconnessione tramite Reti

La comunicazione tra processori avviene passando attraverso opportuni canali direttamente dalla memoria locale di un processore a quella di uno o più processori adiacenti.

Esempi di reti di interconnessione:• Vettore• Matrice (mesh)• Albero binario completo• Ipercubo• etc

Algoritmi Paralleli e Distribuiti a.a. 2008/09 3

Broadcast su rete a Vettore

Si adoperano N processori

Input su P0

Broadcast(x)begin

P0: a0 = xfor i = 1 to N-1 do

Pi: ai = ai-1

end

Tempo parallelo N

x x

0 1 2 N-1

Algoritmi Paralleli e Distribuiti a.a. 2008/09 4

Broadcast su mesh

Si adoperano RxC processoriInput su P0,0

Broadcast(x)beginP0,0: a0,0 = x

for j = 1 to C-1 do

P0,j: a0,j = a0,j-1

for i = 1 to R-1 dofor j = 0 to C-1 pardo

Pi,j: ai,j = ai-1,j

end

Tempo parallelo C+R

x x

x x

x x

x

x

x

x

0 1 2 C-1

0

1

2

R-1

Algoritmi Paralleli e Distribuiti a.a. 2008/09 5

Con n foglie e 2n-1 processori

Input alla radice

Broadcast(x)

begin

P1: a1 = x

for i = 0 to log n -1 dofor j = 2i to 2i+1-1 pardo

Pj: a2j = aj

a2j+1 = aj

end

Tempo parallelo logaritmico

Broadcast su albero binario

a2

a4 a5

a3

a6 a7

a1

Algoritmi Paralleli e Distribuiti a.a. 2008/09 6

Si adoperano n=2d processoriInput su P0

Broadcast(x)begin

P0: a0 = xfor i = 0 to d-1 do

for j = 0 to 2i-1 pardo

Pj: aj+2i = aj

end

Tempo parallelo d = log n

Broadcast su ipercubo

x x

x x

x x

x x

x x

x x

x x

x

000

001

101

111110

010

100

011

Algoritmi Paralleli e Distribuiti a.a. 2008/09 7

Somma su P-RAM EREW

Si adoperano n processoriPer semplicità assumiamo n potenza di 2

Somma(A)begin

for i = 1 to log n dofor j = 0 to n/2i -1 pardo

Pj: A[ j ] = A[ j ] + A[ j+n/2i ]return A[ 0 ]

end

Tempo parallelo logaritmico

Questa tecnica è detta della prima metà

4 2 7 4 1 6 3 8

5 8 10 12

15 20

35

Algoritmi Paralleli e Distribuiti a.a. 2008/09 8

Somma su mesh

Si adoperano RxC processoriCiascun processore ha un proprio valore nella variabile a

Somma_Mesh()begin

for i = 1 to R-1 dofor j = 0 to C-1 pardo

Pi,j: ai,j = ai,j + ai-1,j

for j = 1 to C-1 do

PR-1,j: aR-1,j = aR-1,j + aR-1,j-1

return aR-1, C-1

end

Tempo parallelo R+C

a a

a

a

Algoritmi Paralleli e Distribuiti a.a. 2008/09 9

Somma su albero binario (1)

Con n foglie e 2n-1 processoriInput alle foglie output alla radice

Numerazione dalla radice alle foglieSomma(x)begin

for i = n to 2n-1 pardoPi: ai = read() /* input alle foglie */

for i = log n -1 to 0 dofor j = 2i to 2i+1-1 pardo

Pj: aj = a2j + a2j+1

return a1

end

Tempo parallelo logaritmico

X1+…+x4

X1+x2 X3+x4

X5+…+x8

X5+x6 X7+x8

X1+…+x8

x1 x2 x2 x3 x5 x6 x7 x8

P2

P1

P4

P8

P5 P6 P7

P3

P15

Algoritmi Paralleli e Distribuiti a.a. 2008/09 10

X1+…+x4

X1+x2 X3+x4

X5+…+x8

X5+x6 X7+x8

X1+…+x8

x1 x2 x2 x3 x5 x6 x7 x8

P13

P15

P9

P1

P10 P11 P12

P14

P8

Somma su albero binario (2)

Con n foglie e 2n-1 processoriInput alle foglie output alla radice

Numerazione dalle foglie alla radiceSomma(x)begin

for i = 1 to n pardoPi: ai = read() /* input alle foglie */

for i = log n -1 to 0 dofor j = 2i to 2i+1-1 pardo

P2n-j: a2n-j = a2n-2j + a2n-(2j+1)

return a1

end

Tempo parallelo logaritmico

Algoritmi Paralleli e Distribuiti a.a. 2008/09 11

Si adoperano n=2d processoriCiascun processore ha un proprio valore nella variabile a

Somma_Ipercubo()begin

for i = d-1 to 0 dofor j = 0 to 2i-1 pardo

Pj: aj = aj + aj+2i

return a0

end

Tempo parallelo d = log n

Somma su ipercubo

a2 a3

a0 a1

a6 a7

a4 a5