Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 17/04/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Inserire una sequenza “breve”
in un vettore ordinato
Siano X=(x1, x2, …, xn) un vettore ordinato e Y=(y1, …, ym)
una sequenza di valori qualunque tale che m=O(ns) con
0≤s≤1. Utilizziamo un numero di processori pari ad N=n/m
= (n1-s). È possibile inserire ciascun valore yi nella sequenza
X
determinando
rango(yi:X)
in
tempo
O(m log2(n+2) / log2(N+1))
Quando m << n (ovvero se s  0) si ha N=O(n) e tempo O(1).
Quando m=O(n) (s  1) si ha N=O(1) e tempo O(n log n).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Algoritmo di fusione
tramite rango
Input: A=(a1, a2, …, an), B=(b1, b2, …, bm), ordinati in modo
crescente (m≤n).
Output: C=(c1, c2, …, cn+m), ordinato in modo crescente.
Idea: si partiziona il vettore B in (m / log m) blocchi consecutivi di
log(m) elementi ciascuno B0, B1, … e si crea il vettore Y costituito
dall’insieme degli elementi massimi dei blocchi.
Si calcola rango(Y:A)=(r1, r2, …, rm) e si divide A in blocchi
consecutivi A0=(a1, …, ar1), A1=(ar1+1, …, ar2), …
Poiché A0 e B0 contengono elementi minori di tutti gli altri
elementi di A e B, fondendo A0 e B0 tramite rango si ottiene la
sequenza ordinata dei primi elementi di C. Iterando il ragionamento
su tutte le coppie Ai e Bi si ottiene l’intero vettore C ordinato.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Dettaglio del partizionamento
begin
P0: r [ 0 ] = 0
r [ m / log m ] = n
for i = 1 to m/log m -1 pardo
Pi:
r [ i ] = rango(B[ i * log m -1] : A)
for i = 0 to m/log m -1 pardo
Pi:
Bi = (B[ i * log m ], …, B[ (i+1) * log m -1])
Ai = (A[ r [ i ] ], …, A[ r [i+1] -1])
end
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
Esempio di applicazione
dell’algoritmo di fusione
A = [ 4, 6, 7, 10, 12, 15, 18, 20 ]
B = [ 3, 9, 16, 17 ]
log m
log m
rango(9:A) = 3
rango(17:A) non serve
r = [ 0, 3, 8 ]
B0 = [ 3, 9 ]
B1 = [ 16, 17 ]
A0 = [ 4, 6, 7 ]
A1 = [ 10, 12, 15, 18, 20 ]
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
Complessità dell’algoritmo di fusione
Per completare la fusione di A e B (cioè per calcolare la posizione di
ciascun valore nel vettore finale) si dovranno fondere tutte le coppie di
sottovettori (Ai, Bi). Utilizzando l’inserimento di una seq. breve in un
vettore ordinato ciò si può fare in O(log m) tempo con |Ai| processori.
Quindi con n processori tutte le coppie possono essere fuse
contemporaneamente in tempo logaritmico.
Bisogna inoltre tener conto di quanti elementi ci sono in tutti gli Aj e Bj
(j<i) per posizionare gli elementi di Ai e Bi nel vettore risultante C:
• il valore r[i] (indice di inizio di Ai) da il contributo totale degli Aj;
• i * log m è il contributo di tutti i Bj.
Il tempo totale richiesto è O(log n) con n processori su PRAM CREW.
Esistono anche algoritmi che riducono la complessità temporale a
O(log log n) portando quindi il costo totale a O(n log log n).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
Idea dell’algoritmo di Cole
Si è visto che il tempo parallelo dell’algoritmo di ordinamento tramite
fusione è condizionato da un fattore log n dovuto all’altezza dell’albero
binario, quindi per migliorare un tale algoritmo bisogna incidere sul
computo della operazione di fusione. Questo computo, a tutt’oggi, pur
richiedendo tempi paralleli molto limitati, non riesce ad essere ridotto ad
una costante, impedendo così la ottimalità dell’algoritmo di ordinamento.
L’idea di Cole per risolvere questo problema è consistita nel rinunciare al
calcolo delle K fusioni ad ogni livello, ma di accontentarsi solo del calcolo
di alcuni valori a campione dei K vettori fusione. Questi valori campione,
di numero costante, richiedono tempo parallelo O(1) per essere calcolati.
Il calcolo di nuovi campioni ad ogni livello permette di arrivare al vettore
fusione alla radice, garantendo un tempo parallelo logaritmico per l’intero
algoritmo di ordinamento.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7