Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 27/03/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Dimostrazione del teorema di Brent
Modelli di calcolo:
• Rete combinatoria C di profondità d e dimensione n = i=1..d ni con ni numero
di elementi al livello i.
• PRAM-EW con p processori p0, p1, …, pp-1.
• L’input del circuito combinatorio si considera disponibile nella memoria
condivisa.
• Il fan-in limitato evita che la memoria condivisa non sia sufficiente a
memorizzare i risultati intermedi del calcolo.
Idea della dimostrazione:
Ogni processore simula un componente del primo livello della rete e fornisce
l’output che può essere immagazzinato nella memoria condivisa. Si ripete
l’operazione per un numero di volte pari alla profondità del circuito utilizzando
l’output di ogni livello come input del livello successivo. Nel caso in cui p sia
minore del massimo numero di elementi combinatori presenti in uno stesso livello,
si dovrà effettuare un numero di passi seriali proporzionale al rapporto tra il
numero di elementi del livello i e p.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Modelli CREW ed EREW nel
Teorema di Brent
Quindi la complessità tiene conto della profondità del circuito e dei passi
seriali necessari a simulare un livello.
Tp = i=1..d ni / p  i=1..d (ni / p +1) = n / p + d
Abbiamo detto che il processore che simula l’elemento combinatorio
fornisce l’output che può essere immagazzinato nella memoria condivisa.
Se più processori richiedono in input quello stesso valore si deve accettare
che la P-RAM sia a lettura concorrente. Se si accetta l’ipotesi che anche il
il fan-out sia limitato, si può considerare che in tempo costante l’output
del circuito combinatorio sia direttamente copiato nell’input dei circuiti
che lo richiedono. Questa limitazione permetterebbe la simulazione su una
P-RAM a lettura esclusiva.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Trasportabilità fra P-RAM con
diverso numero di processori
Teorema (p' < p): ogni algoritmo A che lavora in tempo
parallelo O(t) su una PRAM con p processori può essere
simulato da un algoritmo A' che lavora su una PRAM con p'
processori (p' < p) in tempo O(t p / p').
Dimostrazione: durante ognuno dei t passi dell’esecuzione di
A, i p processori lavorano parallelamente in tempo O(1).
Durante ogni passo della esecuzione di A', ciascuno dei p'<p
processori eseguirà un blocco seriale di p/p' operazioni in
tempo O(p/p'). Pertanto il tempo parallelo relativo alla
esecuzione di A' sarà O(tp/p').
Il costo dei due algoritmi A e A' rimane pari a O(tp).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
Numero di processori limitato (1)
Vogliamo sommare n numeri avendo a disposizione p processori (p<n).
Abbiamo già visto la tecnica dell’Accellerated Cascading per sommare
con O(n/log n) processori ottenendo un costo ottimo. In questo caso p è
fisso e vogliamo mantenere la tecnica della prima metà come nella
somma con n processori.
P1 P2 P3 P4
con n processori
begin
for i = 1 to log n do
for j = 0 to n/2i -1 pardo
Pj:
A[ j ] = A[ j ] + A[ j+n/2i ]
return A[ 0 ]
end
4
2
7
4
5
8
10 12
1
6
3
8
15 20
35
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
Numero di processori limitato (2)
p=2
con p < n processori
begin
for i = 1 to log n do
for s = 0 to (n/2i) / p -1 do
for j = 0 to min(n/2i, p) -1 pardo
if (j+s*p < n/2i) then
Pj:
A[ j+s*p ] = A[ j+s*p ] + A[ j+s*p +n/2i ]
return A[ 0 ]
end
4
i=1
P1 P2
2
7
4
1
6
3
8
2
10
4
1
6
3
8
8
10 12
s=0
5
s=1
i=2
5
s=0
i=3
15 20
s=0
35
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
Come ordinare nel Parallelo
Per questo problema non utilizzeremo il modello PRAM, ma un modello
semplificato costruito appositamente. Utilizziamo il comparatore, ossia
un circuito di confronto con due ingressi e due uscite il cui valore è la
coppia di valori in input ordinati in modo ascendente.
x
min(x,y)
y
max(x,y)
I circuiti formati da comparatori, se opportunamente combinati,
costituiscono un'architettura in grado di ordinare n valori di input.
9
5
2
2
5
9
7
5
5
2
2
5
7
7
7
7
9
Algoritmi Paralleli e Distribuiti a.a. 2008/09
9
7
Insertion Sort
Due architetture per implementare l'insertion sort (tra 8 valori in input):
Questa macchina utilizza una
versione seriale dell'algoritmo di
complessità O(n2) (indicata dalla
profondità del circuito, ossia il
numero di porte che vengono
attraversate in tempi differenti).
È
possibile
ottenere
una
complessità O(n) ottimizzando lo
scheduling dei comparatori e
parallelizzando l'algoritmo.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8
Sulla monotonicità
Se un circuito di ordinamento trasforma la sequenza di input
a = (a1, a2, …, an) nella sequenza di output b = (b1, b2, …, bn),
allora per ogni funzione monotona crescente f, il circuito
trasforma la sequenza di input f(a) = (f(a1), f(a2), …, f(an))
nella sequenza di output f(b)=(f(b1), f(b2), …, f(bn)).
Tale proprietà è facilmente verificata da un singolo
comparatore e per induzione la si può provare per un intero
circuito di ordinamento.
x
min(x,y)
f(x)
min(f(x), f(y))) = f(min(x,y))
y
max(x,y)
f(y)
max(f(x), f(y))) = f(max(x,y))
Algoritmi Paralleli e Distribuiti a.a. 2008/09
9
Principio 0/1
Teorema (principio 0/1): se un circuito combinatorio di ordinamento lavora
correttamente per qualunque input costruito sull'alfabeto {0,1} allora lavora
correttamente per qualunque input costruito su di un qualsiasi alfabeto finito A.
Dim: supponiamo per assurdo che il circuito ordini tutte le sequenze costruite
sull'alfabeto {0,1} correttamente, ma che esista una sequenza di input di numeri
arbitrari a = (a1, a2, …, an) contenente elementi ai e aj tali che ai < aj mentre il
circuito pone aj prima di ai nella sequenza di output. Definiamo una funzione f
monotona crescente come:
f(x) = 0 se x  ai
f(x) = 1 se x > ai
dal lemma precedente segue che il circuito sistema f(aj) prima di f(ai) nella
sequenza di output quando f(a) è l'input. Ma poiché f(aj) = 1 mentre f(ai) = 0,
neghiamo l'ipotesi giungendo ad un assurdo.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
10
Sequenze bitoniche
Una Sequenza Bitonica è una sequenza che può essere divisa in due sottosequenze
monotone, una crescente e l'altra decrescente o viceversa.
Sono bitoniche le due sequenze:
m(S) = (min{s1,sn+1}, min{s2,sn+2}, …, min{sn,s2n})
M(S) = (max{s1,sn+1}, max{s2,sn+2}, …, max{sn,s2n})
ottenute dalla sequenza bitonica S = s1, s2, …, s2n
Sfruttando la definizione di m(S) ed M(S) e le relative proprietà si può ottenere una
definizione ricorsiva per le sequenze bitoniche che ci permette di realizzare un primo
algoritmo di ordinamento che opera ricorsivamente secondo lo schema:
S=13896554
S1 = m(S) = 1 3 5 4
S2 = M(S) = 6 5 8 9
S3 = m(S1) = 1 3 S4 = M(S1) = 5 4
S5 = m(S2) = 6 5 S6 = M(S2) = 8 9
1
3
4
5
5
6
8
9
Complessità O(log(n)).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
11
Sequenze pulite
Una sequenza binaria si dice pulita se è composta interamente da 0 o da 1.
Se S è bitonica almeno una delle due sottosequenze bitoniche m(S) e M(S)
è pulita (diretta conseguenza del fatto che la cardinalità di {0,1} è due).
In figura è presentato un circuito di ordinamento, di profondità
logaritmica, per sequenze 0/1 bitoniche (ad ogni passo rendiamo pulita
metà della sequenza).
0
0
1
1
1
0
0
0
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
12