Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 20/03/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Somme prefisse su albero binario
Le n foglie hanno già il valore da sommare nella variabile xi
begin
P
for i = log n -1 to 0 do
for j = 2i to 2i+1-1 pardo
P X +…+x
Pj:
xj = x2j + x2j+1
X1+…+x8
1
1
2
P4 X1+x2
P1: sp1 = 0
for i = 0 to log n -1 do
for j = 2i to 2i+1-1 pardo
Pj:
sp2j = spj
sp2j+1 = spj + x2j
for i = n to 2n-1 pardo
Pi:
xi = xi + spi
end
P8 x1
X5+…+x8 P
3
4
X5+x6 P
6
P5 X3+x4
x2
x2
x3
x5
x6
X7+x8 P
7
x7
x8
P15
sp = 0
X1+…+x8
sp = X1+…+x4
sp = 0
X1+…+x4
sp = X1+…+x6
X1+x2
sp = 0
X1+x2
X3+x4
X5+x6
X7+x8
sp = X1+…+x7
x1
sp = 0
x1
X5+…+x8
x2
x3
x4
x5
x6
x7
x8
Tempo parallelo logaritmico
Algoritmi Paralleli e Distribuiti a.a.2008/09
2
Somme prefisse su mesh
Ogni processore ha il valore da sommare in xi,j
begin
for i = 0 to R-1 pardo
for j = 1 to C-1 do
Pi,j:
xi,j = xi,j + xi,j-1
P0,C-1: su0,C-1 = 0
for i = 1 to R-1 do
Pi,C-1:
sui,C-1 = xi-1,C-1 + sui-1,C-1
for i = 0 to R-1 pardo
for j = C-2 to 0 do
Pi,j:
sui,j = sui,j+1
for i = 0 to R-1 pardo
for j = 0 to C-1 pardo
Pi,j:
xi,j = xi,j + sui,j
end
Tempo parallelo R+C
Algoritmi Paralleli e Distribuiti a.a.2008/09
3
Somme prefisse con
Accellerated Cascading
Si adoperano k processori
Per semplicità assumiamo n multiplo di k: n = h·k
begin
for i = 0 to k-1 pardo
Pi:
bi = i * h
// inizio blocco i-esimo
for j = 1 to h -1 do
A[ bi + j ] = A[ bi + j ] + A[ bi + j-1 ]
B[ i ] = A[ bi + h-1 ]
// l’ultimo del blocco
PrefixSum(B, k)
for i = 1 to k-1 pardo
Pi:
for j = 0 to h -1 do
A[ bi + j ] = A[ bi + j ] + B[ i-1 ]
end
Tempo parallelo O(h + log k)
Algoritmi Paralleli e Distribuiti a.a.2008/09
4
Elemento combinatorio
Def: Un elemento combinatorio è un qualunque elemento di
circuito che abbia un numero costante di input e output e che
esegua una funzione ben precisa.
Esempi:
• Porte logiche
• Comparatore
• ecc…
not
and
min{x, y}
x
y
or
comp
max{x, y}
Più elementi combinatori possono essere collegati tra di loro
formando una rete combinatoria dove l'output di un
elemento può essere l'input di uno o più altri elementi.
Algoritmi Paralleli e Distribuiti a.a.2008/09
5
Rete combinatoria
Una rete combinatoria C può essere vista come un grafo diretto aciclico
GC avente un nodo per ciascun elemento combinatorio c e un arco diretto
(c',c") se l’output di c' è input di c".
La dimensione di una rete combinatoria è il numero di nodi del grafo e la
profondità è il diametro del grafo.
Il fan-in di un elemento c è il grado entrante del nodo c in GC e
corrisponde al numero di input dell’elemento.
Il fan-out di un elemento c è il grado uscente del nodo c in GC.
È da notare che non necessariamente il numero di output di un elemento
combinatorio è uguale al suo fan-out, infatti un elemento combinatorio
con un solo filo di output può “servire” un numero qualunque di altri
elementi.
Algoritmi Paralleli e Distribuiti a.a.2008/09
6
Teorema di Brent
Teorema (CREW): ogni algoritmo che lavora su
una rete combinatoria di profondità d e dimensione
n che sia a fan-in limitato, può essere simulato da un
algoritmo che lavora su una PRAM CREW con p
processori in O(n/p+d) tempo.
Teorema (EREW): ogni algoritmo che lavora su
una rete combinatoria di profondità d e dimensione
n che sia a fan-in e fan-out limitato, può essere
simulato da un algoritmo che lavora su una PRAM
EREW con p processori in O(n/p+d) tempo.
Algoritmi Paralleli e Distribuiti a.a.2008/09
7
Teorema di Brent - Esempio
Profondità: d = 5
Dimensione: n = 22
Processori: p = 3
Algoritmi Paralleli e Distribuiti a.a.2008/09
8