Algoritmi Paralleli e Distribuitia.a. 2008/09

Lezione del 31/03/2009

Prof.ssa ROSSELLA PETRESCHI

a cura del Dott. SAVERIO CAMINITI

Circuito di fusione

Il circuito di fusione fonde due sequenze ordinate costruite sullo stesso alfabeto sfruttando il fatto che, date due sequenze ordinate entrambe crescenti (o decrescenti) x e y, la sequenza che si ottiene concatenando x con z=“y rovesciata” è bitonica (l’inversione della stringa y si realizza semplicemente variando le connessioni).

La profondità del circuito è logaritmica e il numero di comparatori ad ogni passo è n/2.

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

0

0

0

1

0

0

1

1

0

0

0

0

1

0

1

1

0

0

0

0

1

0

1

1

0

0

0

0

0

1

1

1

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

Circuito di ordinamentoIn figura è riportato un circuito di ordinamento che realizza l’ordinamento connettendo iterativamente diversi circuiti di fusione (la base di questa costruzione sta nel fatto che ogni sequenza di due elementi è bitonica).

Poiché concateniamo un numero logaritmico di circuiti di fusione, otteniamo una profondità del circuito O(log2 n).

0

0

0

1

0

0

1

1

0

0

0

0

1

0

1

1

0

0

0

0

1

0

1

1

0

0

0

0

0

1

1

1

0

0

1

0

0

0

1

1

0

1

0

0

0

1

0

1

1

0

0

0

0

1

1

0

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

Applicando il teorema di Brent

Il circuito di ordinamento, O, è un circuito combinatorico di profondità d = O(log2 n), di dimensione pari al numero di comparatori c = O(n log2 n), fan in e fan out limitati. Per il Teorema di Brent, l’algoritmo di ordinamento che lavora su O può essere simulato da una algoritmo che lavora su una PRAM EREW con N processori in tempo O(c / p + d), ovvero O((n log2 n) / p + log2 n).

Quando p = O(n) si ha che la complessità temporale dell'ordinamento su una PRAM EREW è O(log2 n) e il costo O(n log2 n).

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

Algoritmo pari/dispari

L’idea base è quella di far lavorare prima tutti i processori di indice pari e poi quelli di indice dispari per evitare letture e scritture concorrenti nei confronti.

for s = 1 to n/2 dofor i = 0 to i < n-1 step 2 pardo

Pi: if x[i] > x[i+1] then swap(x[i], x[i+1])

for i = 1 to i < n-1 step 2 pardo

Pi: if x[i] > x[i+1] then swap(x[i], x[i+1])

Richiede tempo O(n) su una PRAM EREW con O(n) processori.

Il costo complessivo è O(n2).

0 1 2 3 4 5 6

s=1 pari 8 5 9 2 4 3 6

s=1 dispari 5 8 2 9 3 4 6

s=2 pari 5 2 8 3 9 4 6

s=2 dispari 2 5 3 8 4 9 6

s=3 pari 2 3 5 4 8 6 9

s=3 dispari 2 3 4 5 6 8 9

Fine 2 3 4 5 6 8 9

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

Algoritmo pari/disparicon p < n processori

Ogni processore Pi gestisce un blocco Si composto di b = n/p elementi.

for i = 0 to p-1 pardo

Pi: ordina Si in modo sequenzialefor s = 0 to p/2 do

for i = 0 to i < p-1 step 2 pardo

Pi: Si' = Merge(Si, Si+1)

Si = Si' [0, b-1]

Si+1 = Si' [b, 2b-1]for i = 1 to i < p-1 step 2 pardo

Pi: Si' = Merge(Si, Si+1)

Si = Si' [0, b-1]

Si+1 = Si' [b, 2b-1]

I tempo richiesto è Tp = O(n/p log (n/p)) + p/2 O(n/p). Quando abbiamo

p = O(log n) il tempo Tp diventa O(n): in tal caso il costo totale è O(n log n).

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

Ordinamento su PRAM CRCW

Sfruttiamo la scrittura concorrente per ottenere un semplice algoritmo di ordinamento. Assumiamo una PRAM CRCW con scrittura concorrente della somma dei valori scritti.

for i = 0 to n-1 pardo

for j = 0 to n-1 pardo

Pi,j: if (x[ i ] > x[ j ]) or

(x[ i ] = x[ j ] and i > j) then

c[ i ] = 1

for i = 0 to n-1 pardo

Pi,1:x[ c[ i ] ] = x[ i ]

Con n2 processori il tempo richiesto è O(1),

Il costo totale è quindi O(n2).

xfin

0 3

1 5

2 5

3 7

4 8

xiniz

0 7

1 5

2 3

3 8

4 5

C

0 3

1 1

2 0

3 4

4 2

Risultati dei confronti effettuati

i j 0 1 2 3 4

0 F V V F V

1 F F V F F

2 F F F F F

3 V V V F V

4 F V V F F