Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 19/05/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Algoritmo Ear Decomposition
Input: G privo di ponti rappresentato come sequenza di archi
begin
T = spanning tree di G
calcola TDE; radica T in qualunque nodo; calcola level(v) vT
for each  e=(u,v)  T pardo
Pe:
calcola lca(u,v)
label(e) = <level(lca(u,v)), e>
for each  e  T pardo
Pe:
label(e) = min{ label(e') : e'T  e  ciclo indotto da e' in T }
ordina gli archi rispetto a label(e)
end
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Calcolo di label(e)  eT
Dopo aver calcolato label(e)  e  T si definisca:
f(v) = min{label(v,u) : (v,u)  T}  vT
È possibile verificare che per ogni arco e=(v, p(v))T il valore label(e)
sarà il minimo valore f(u) tra i nodi u appartenenti al sottoalbero Tv
radicato in v.
Il calcolo del minimo nel sottoalbero si può realizzare, tramite la tecnica
del salto del puntatore, in tempo O(log n) su una PRAM CRCW (con
scrittura del valore minimo) con n processori. L’assegnamento di f(v) v
richiede O(1) e m processori sullo stesso modello.
Il costo è quindi O((n+m) log n) su PRAM CRCW o, simulando la
scrittura concorrente, O((n+m) log2 n) su PRAM CREW.
Più avanti si introdurrà l’operazione di Rake tramite la quale è possibile
effettuare la ricerca del minimo (e varie altre operazioni) nel sottoalbero
in modo più efficiente.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Analisi
1.
La costrizione dello ST (dando costo 1 a tutti gli archi)
costa O(n2 log2 n) su PRAM CREW.
2. Il calcolo del TDE, il radicamento dell’albero e il calcolo del livello
per ogni nodo richiedono un costo O(n log n) su PRAM EREW.
3. Il calcolo del lca con la tecnica del TDE richiede un costo pari a
O(n log n) su PRAM EREW. (*)
4. Il calcolo di label(e)  eT si è visto che costa O((n+m) log2n) su
PRAM CREW.
5. L’ordinamento richiede O(n log n) su PRAM EREW.
La complessità totale dell’algoritmo è pari a quella del calcolo dello ST:
O(n2 log2 n) su PRAM CREW
(*) Abbiamo visto esplicitamente come calcolare il lca di una singola coppia di nodi in tempo log n con n processori su
PRAM EREW. Precalcolando opportune strutture dati per trovare il minimo in ogni intervallo di un vettore (Range
Minimum Query) ogni processore può calcolare il lca di una coppia di nodi in tempo costante su PRAM CREW.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
Operazione di rake
Dato un albero binario T, radicato in r, con la proprietà 0/2 ed
una foglia u in T tale che p(u)  r l’operazione Rake(u)
trasforma T in T' eliminando u e p(u) e unendo il fratello di u
al padre del padre.
n
n
p
f
u
f
V' = V \ {u, p}
E' = E \ {(u, p), (f,p), (p,n)}{(f,n)}
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
Se T non è 0/2
Si possono aggiungere tanti nodi quanti ne servono per
garantire la proprietà 0/2. Ciò richiede tempo costante con
O(n) processori e incremento di occupazione di memoria
lineare.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
L’operazione di Contrazione
Tramite ripetute applicazioni del rake vogliamo ridurre
l’albero iniziale T in un albero di tre nodi: la radice e due
foglie (quella più a sinistra e quella più a destra in T).
Problema: bisogna evitare il rake concorrente di foglie con lo
stesso padre o con padri adiacenti per evitare risultati
inconsistenti:
u
u'
u'
u
Algoritmi Paralleli e Distribuiti a.a. 2008/09
u'
u
7
Soluzione
1. Evitare il rake concorrente di foglie con lo stesso padre:
Dopo averle numerate da sinistra a destra, si esegue il rake in
parallelo su foglie a numerazione alterna.
6
u
u'
7
2. Evitare il rake concorrente di foglie con padri adiacenti:
Fra le foglie a numerazione alterna selezionate, si eliminano prima
quelle che sono figli sinistri e in seguito quelle che sono figli destri.
u'
6
u
8
7
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8
Esempio
Passo 2.1 rake su q ed l
Input:
Albero
risultante
r
g
f
a
i
l
q
a
h
c
z
n
m
o
s
e
d
e
d
r
p
f
Passo 1 calcola A
2
3
4
5
o
s
6
p
n
b
b
Passo 2.2 rake su t ed p
a
7
i
t
r
Albero
risultante e
t
m
z
d
1
g
g
f
s
o
i
n
b
8
A q s t f l o p n
1
Passo 2.3 aggiorna A
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
3
4
A s f o n
9
Esempio
Passo 2.1 rake su o
Albero
risultante
r
e
d
a
Passo 2.1 rake su nulla
Passo 2.2 rake su f
r
i
f
n
b
a
i
s
n
Albero
risultante
b
1
Passo 2.3 aggiorna A
Passo 2.2 rake su s
Albero
risultante
a
A n
r
e
Passo 2.1 rake su n
i
f
n
r
b
a
1
Passo 2.3 aggiorna A
2
A f n
b
Albero
risultante
Passo 2.2 rake su nulla
Passo 2.3 aggiorna A = 
Algoritmi Paralleli e Distribuiti a.a. 2008/09
10