Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 07/04/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Verso un ordinamento ottimo
Gli algoritmi paralleli di ordinamento visti fino ad ora
raggiungono, nei casi migliori, un costo O(n log2 n) su PRAM
CREW.
Nel 1988 R. Cole presentò sul SIAM Journal Computing la
prima versione del pipelined-merge sort (poi conosciuto come
algoritmo di Cole) che richiede un tempo parallelo O(log n)
su una PRAM. Da allora varianti e raffinamenti
dell’algoritmo si sono susseguiti in letteratura fino a
raggiungere un costo ottimo su PRAM EREW.
Nel seguito presentiamo l’idea alla base di questo algoritmo e
una serie di concetti e/o algoritmi necessari per la sua
realizzazione. Il dettaglio dell’algoritmo è lasciato come
tesina di approfondimento.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Ricerca di un elemento
in un vettore ordinato
Variabili:
• N: numero dei processori
• y: elemento da cercare
• X = (x1, x2, …, xn), tale che x1  x2 …  xn: vettore in cui cercare y
• l ed r (inizializzati a 0 ed n rispettivamente): estremi del vettore su cui si lavora;
• q0,…qN+1 (relative a ciascun processore + 2 aggiuntive): indice degli elementi da
analizzare;
• c0,…cN+1 (inizializzate a 0, cN+1 inizializzata ad 1): identificatori del sottovettore su
cui iterare.
Input: X, y
Output: i t.c. xi  y  xi+1
• Passo 1: dividi iterativamente il vettore in sottovettori più o meno bilanciati finché
il numero di elementi nel sottovettore identificato non è  N e controlla se X[qi]=y;
• Passo 2: controlla se nel sottovettore di dimensione  N è presente l’elemento
cercato.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Algoritmo Ricerca Binaria
P1:c0 = 0; cN+1 = 1
for j = 1 to N pardo
Pj:
while (r-l) > N do
if j = 1 then q0 = l; qN+1 = r
qj = l +  j (r-l) / (N+1) 
if y = X[ qj ] then return qj
else if y > X[ qj ] then cj = 0 else cj = 1
if cj < cj+1 then l = qj; r = qj+1
if j = 1 and c0 < c1 then r = q1
if j  r-l then
if y = X[ l+j ] then return l+j
else if y > X[ l+j ] then cj = 0 else cj = 1
if cj < cj+1 then return l+j
if j = 1 and c0 < c1 then return l
Algoritmi Paralleli e Distribuiti a.a. 2008/09
Passo 1
Passo 2
4
Esempio
l
0
r
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = 14
N=2
y = 37
x - -22 -3 4 10 12 15 27 32 35 42 55 56 61 70 
q0
q1
q2
0
c
l
4
1
6
7
8
9
10
11
x 10 12 15 27 32 35 42 55
q0 q1
0
c
q2
1
2
q3
3
0 0 1 1
r
5
2
q3
Passo 2
l
7
8
9
10
11
x 27 32 35 42 55
0
3
0 0 0 1
r
c
Algoritmi Paralleli e Distribuiti a.a. 2008/09
1
2
3
0 0 1 1
return 9
5
Complessità dell’algoritmo
Ciascuna iterazione del Passo 1 richiede tempo O(1). Analizziamo
il numero di iterazioni esplicitando la dimensione si del sottovettore
nell’iterazione i-esima:
s0 = n+2
si+1 = si / (N+1) = s0 / (N+1)i
Quindi il numero totale di iterazioni è:
logN+1(n+2) = log2(n+2) / log2(N+1)
Il Passo 2 richiede tempo costante, quindi il tempo complessivo
richiesto dall’algoritmo è O(log2(n+2) / log2(N+1)). Il modello di
PRAM è CREW perché tutti gli N processori accedono
contemporaneamente alle variabili y, l, r e c.
Si noti che, quando N = O(1), il costo complessivo dell’algoritmo è
O(log n): pari all’ottimo nel sequenziale. Quando N = O(n) il
tempo diventa costante.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
Il concetto di rango
Dati X = (x1, x2, …, xt), Y = (y1, y2, …, ys) e z, con z, xi e yj
nello stesso insieme U, definiamo:
1. rango(z:X) = numero di elementi in X  z
Es: X = (-3,8,-2,5), z = 1, rango(z:X) = 2
2. rango(Y:X) = (r1, r2, … rs) con ri = rango(yi:X)
Es: X = (15,-3,12,1,-5), Y = (3,-13,-2), rango(Y:X) = (3,0,2)
Si noti inoltre che vale la relazione*:
rango(x:AB) = rango(x:A) + rango(x:B)
*Nota: per semplicità assumiamo che i valori siano tutti distinti.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
Fondere tramite rango
Il problema di fondere due vettori ordinati A e B in un unico
vettore C si può risolvere calcolando il rango degli elementi di A
rispetto a B e di quelli di B rispetto ad A: rango(x:AB) è
esattamente la posizione in cui l’elemento x si trova nel vettore C.
L’algoritmo di Ricerca Binaria può essere utilizzato per calcolare il
rango di un elemento in un vettore, ed in particolare il rango di
ogni elemento di A in B e viceversa. Con tali informazioni
possiamo calcolare C.
Esempio: A=(-2, -1, 8) B=(3,6) AB=(-2, -1, 8, 3, 6)
rango(A:B)=(0, 0, 2) rango(B:A)=(2,2)
rango=(1, 2, 5, 3, 4) C=(-2, -1, 3, 6, 8)
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8