Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 17/03/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Trasportabilità degli algoritmi
Dati due differenti modelli di computazione M e M’, si dice
che un algoritmo A progettato per la computazione C sul
modello M è trasportabile sul modello M’ se l’algoritmo A’
che computa C sul modello M’ è ottenibile da A tramite
l’applicazione di un insieme finito di regole fisse.
Il broadcast su PRAM è un primo esempio di trasportabilità
di un algoritmo:
se su una PRAM CR tutti i processori vogliono leggere la
stessa informazione, pagando un tempo O(log n) per il
broadcast si può trasportare l’algoritmo su una PRAM ER.
Vediamo come affrontare la trasportabilità della scrittura
concorrente da PRAM CW a PRAM EW.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Simulazione della scrittura concorrente:
stessa informazione
Sia dato un algoritmo per PRAM CW con scrittura concorrente di valori identici.
L’operazione compiuta da tutti i processori di scrivere nella stessa locazione R viene
simulata su PRAM EW dal solo processore P0, dopo aver controllato che tutti i valori ai
scritti dai rispettivi Pi siano uguali*. Questo controllo si effettua usando un vettore A con
tutti i valori da scrivere e un vettore di booleani utilizzato per riportare le eventuali diversità
nei valori di A:
for j = 0 to n pardo
Pj:
A[ i ] = ai; B[ i ] = true
for i = 1 to log n do
for j = 0 to (n/2i -1) pardo
Pj:
if A[ j ]  A[ j+ n/2i ] or not B[ j ] or not B[ j+ n/2i ] then
B[ j ] = false
P0: if B[ 0 ] then R = A[ 0 ]
Il tempo parallelo richiesto è O(log n)
* Questo controllo su PRAM CW è effettuato a livello hardware
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Simulazione della scrittura concorrente:
funzione dei valori
La simulazione di PRAM CW con scrittura del massimo valore (o della
somma o di qualsiasi altra funzione commutativa f dei valori) viene
eseguita su PRAM EW semplicemente utilizzando la tecnica della metà
per il computo di f su un vettore A:
for j = 0 to n pardo
Pj:
A[ i ] = ai
for i = 1 to log n do
for j = 0 to (n/2i -1) pardo
Pj:
A[ j ] = f ( A[ j ], A[ j+ n/2i ] )
P0: R = A[ 0 ]
Con lo stesso schema si può simulare anche la scrittura concorrente basata
su priorità (ad esempio in funzione dell’indice del processore che vuole
scrivere).
In entrambi i casi la simulazione richiede tempo parallelo logaritmico.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
Simulazione della lettura concorrente
(caso generale)
Problema: N processori P1, P2, …, Pn vogliono leggere il contenuto di K celle di
memoria (in generale K<N e non tutti i processori vogliono leggere dalla stessa
locazione di memoria) su una P-RAM di tipo EREW.
Algoritmo:
Passo 1: si costruisca M, vettore di coppie del tipo (Pi, Lj), ciascuna indicante che
il processore i-esimo vuole leggere la j-esima locazione di memoria (i=0…N-1,
j=1…K). Questo vettore viene ordinato in modo stabile, rispetto ai valori Lj (la
stabilità garantisce l’ordinamento delle coppie).
Passo 2: si raggruppino i processori rispetto alla comune locazione di memoria a
cui vogliono accedere, si individuino gli inizializzatori di ogni blocco e si conti il
numero di elementi in ogni blocco.
Passo 3: il primo processore di ogni blocco legge la locazione corrispondente e poi
attiva un’operazione di broadcast sul blocco.
Passo 4: tutti i processori, in parallelo leggono l’informazione richiesta.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
PASSI 1 e 2
Passo 1:
for i = 0 to n-1 pardo
Pi:
M[ i ] = (i, Lj)
// coppie (proc, loc)
sort(M, loc);
Passo 2:
P0: iniz[ 0 ] = true; B[ 0 ] = 1
for i = 1 to n-1 pardo
Pi:
if M[ i ].loc  M[ i-1 ].loc then
iniz[ i ] = true; B[ i ] = 1
else
iniz[ i ] = false; B[ i ] = 0
PrefixSum(B, n)
Proc
0
1
2
3
4
5
Loc
8
3
3
9
8
3
Proc
1
2
5
0
4
3
Loc
3
3
3
8
8
9
iniz
T
F
F
T
F
T
B
1
0
0
1
0
1
B
1
1
1
2
2
3
Il vettore B è utilizzato per identificare il blocco di appartenenza di ogni processore
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
PASSO 3
Invece di eseguire K broadcast differenti (uno per blocco) si esegue un
unico broadcast multiplo che tiene conto della separazione in blocchi
Passo 3: // Broadcast multiplo
for i = 0 to n-1 pardo
Pi:
if iniz[ i ] then
D[ i ] = contenuto di M[ i ].loc
iniz T
F
D x
B 1
for j = 0 to log n -1 do
D x
for i = 0 to n-1 pardo
Pi:
if iniz[ i ] and i+2j<n and B[ i ] = B[ i+2j ] then
D[ i+2j ] = D[ i ]
D x
iniz[ i+2j ] = true
D x
Algoritmi Paralleli e Distribuiti a.a. 2008/09
F
T
F
y
1
1
x
T
z
2
2
3
y
y
z
x
x
y
y
z
x
x
y
y
z
7
PASSO 4
Passo 4:
for i = 0 to n-1 pardo
Pi:
// chi aveva richiesto l’i-esimo dato
R[ M[ i ].proc ] = D[ i ]
// nel registro del proc i-esimo
// si carica il dato voluto
Ri = R[ i ]
Proc
1
2
5
0
4
3
Loc
3
3
3
8
8
9
D
x
x
x
y
y
z
R
y
x
x
z
y
x
Al termine ogni processore i avrà nel suo registro R il dato contenuto alla
locazione Lj inizialmente specificata.
Tempo Parallelo:
Passo 1: Tsort
Passi 2, 3: logaritmico
Passo 4: costante
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8
Simulazione della scrittura concorrente
(caso generale)
Problema: N processori P1, P2, …, Pn vogliono scrivere i valori a1, a2, …, an
rispettivamente, in K diverse celle di memoria di una P-RAM di tipo EREW. In
generale K<N e si vuole simulare la concorrenza con priorità (scrive il processore
di indice minore).
Algoritmo:
Idea analoga a quello visto per il caso generale di lettura concorrente
Passo 1: si costruisca M, vettore di coppie del tipo (Pi, Lj), ciascuna indicante che
il processore i-esimo vuole scrivere nella j-esima locazione di memoria (i=0…N1, j=1…K) il dato memorizzato nel vettore D (i-esima locazione). Questo vettore
viene ordinato in modo stabile, rispetto ai valori di Lj.
Passo 2: si raggruppino i processori rispetto alla comune locazione di memoria a
cui vogliono accedere e si individuino gli inizializzatori di ogni blocco.
Passo 3: in ogni blocco, il processore di indice minore (il primo del blocco) scrive
la sua informazione nella locazione di memoria caratterizzante il blocco.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
9
Esempio di scrittura concorrente
Passo 1:
analogo
Passo 2:
P0: iniz[ 0 ] = true
for i = 1 to n-1 pardo
Pi:
if M[ i ].loc  M[ i-1 ].loc then iniz[ i ] = true
else iniz[ i ] = false
Proc
0
1
2
3
4
5
Loc
8
3
3
9
8
3
D
x
y
z
a
b
c
Proc
1
2
5
0
4
3
Loc
3
3
3
8
8
9
iniz
T
F
F
T
F
T
Passo 3:
for i = 0 to n-1 pardo
Pi:
if iniz[ i ] then
scrivi D[ M[ i ].proc ] in M[ i ].loc
D
x
y
z
P0
Memoria
a
b
c
P5
P3
y
0
1
2
3
x
4
5
6
7
8
Algoritmi Paralleli e Distribuiti a.a. 2008/09
a
9
10
Somme prefisse
Sequenziale
PrefixSum(A, n)
begin
for i = 1 to n-1 do
A[ i ] = A[ i ] + A[ i-1 ]
end
2
5
1
3
2
6
0
1
2
7
8
11 13 19 19 20
Tempo O(n)
Algoritmi Paralleli e Distribuiti a.a. 2008/09
11
Somme prefisse su P-RAM
P-RAM EREW con n processori
PrefixSum(A, n)
begin
for i = 0 to log n -1 do
for j = 0 to n-1 -2i pardo
Pj:
A[ j+2i ] = A[ j ] + A[ j+2i ]
end
Tempo Parallelo O(log n)
2
5
2
2
1
5
7
3
1
6
7
3
4
6
2
5
8
11 11 12 11
9
5
4
2
7
8
0
1
7
2
1
6
6
8
0
6
2
2
2
8
8
11 13 19 19 20
7
Algoritmi Paralleli e Distribuiti a.a. 2008/09
11
12