Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 12/05/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Le variabili
Per ogni nodo p:
Fram(p) nome del frammento a cui p appartiene.
Liv(p) valore del livello del frammento a cui p appartiene.
Per ogni arco (p, q):
Statop(q) accettato se è stato inserito nel MST.
Per ogni frammento f:
w(f) minimo fra i costi degli archi uscenti da f (è
sufficiente ad identificare univocamente l’arco perché
assumiamo costi distinti).
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Complessità di comunicazione
Teorema: l’algoritmo per la determinazione del MST in un
sistema distribuito richiede complessità di comunicazione
O(n log n + m).
Dim: ad ogni livello O(n) messaggi in totale sono inviati
lungo gli spigoli dell’albero. Ci sono inoltre O(m) messaggi
addizionali in fase di inizializzazione, necessari affinchè ogni
nodo possa conoscere quali sono gli identificativi dei propri
vicini.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Spigolo di costo minimo del frammento
Quando due frammenti si combinano (o quando uno viene assorbito in un
altro) bisogna che tutti i nodi del nuovo frammento aggiornino le loro
variabili e che l’intero frammento identifichi il proprio arco uscente di
costo minimo. Tutto avviene tramite una operazione di broadcast con eco
così suddivisa:
• si propagano le nuove informazioni a tutti i nodi;
• ciascun nodo v individua l’arco (v,u) di costo minimo tra quelli
uscenti dal frammento;
• tramite l’eco si trasmettono al nodo che identifica il frammento i
minimi parziali;
• il nodo identificatore individua il minimo assoluto (x,y).
Tale valore sarà poi ritrasmesso a tutti i nodi del frammento; in questo
modo, il nodo x potrà mandare una richiesta di connessione al frammento
ad esso adiacente.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
4
Complessità temporale
Lemma: Il livello di un frammento non eccede mai O(log n)
Dim: Per l > 0, un frammento di livello l si forma soltanto
quando due frammenti di livello l-1 si fondono, quindi un
frammento di livello l contiene almeno 2l nodi, ne consegue
l’asserto, dato che n  2l, per ogni l.
Come conseguenza del Lemma e del fatto che le operazioni
ad ogni livello richiedono tempo O(n) si ha:
Teorema: l’algoritmo per la determinazione del MST in un
sistema distribuito richiede complessità temporale O(n log n)
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
Algoritmo per il MST distribuito
begin
// inizialmente init = V
Piinit: inizializza tutte le variabili
trova l’arco (i,y) di costo minimo
poni statoi(y) = accettato
send ad y richiesta di connessione
repeat
Pi:
receive messaggio M dal mittente q
if M è una richiesta di connessione then
if liv(q) > liv(i) then non fare nulla
else if liv(q) < liv(i) then
assorbi fram(q) in fram(i)
send a q richiesta di ridefinizione R{liv(i), fram(i)}
else if q = y e liv(q) = liv(i) e w(fram(i))=w(fram(q)) then
combina fram(q) con fram(i)
send a q richiesta di ridefinizione R{liv(i)+1, min(q,i)}
else if M è una richiesta di ridefinizione then
aggiorna tutte le variabili relative a i con i valori ricevuti da R
send R a tutti gli appartenenti al vecchio frammento di i
trova lo arco (x,y) di costo minimo uscente dal nuovo frammento
if i = x then poni statoi(y) = accettato // solo il nodo x contatta y
send ad y richiesta di connessione
until rimane un solo frammento
end
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
Esempio left e right
h
Consideriamo l’albero in figura e il suo CDE,
considerandolo radicato nel nodo h
hehcbciadaigcfch
Su tale albero otteniamo i seguenti vettori:
e
f
c
b
g
i
a
d
h,e
e,h
h,c
c,b
b,c
c,i
i,a
a,d
d,a
a,i
i,g
g,i
i,c
c,f
f,c
c,h
1
-1
1
1
-1
1
1
1
-1
-1
1
-1
-1
1
-1
-1
S
1
0
1
2
1
2
3
4
3
2
3
2
1
2
1
0
left
1
0
1
1
0
1
1
1
0
0
1
0
0
1
0
0
right
1
0
0
1
0
0
0
1
1
0
1
1
0
1
1
1
CDE
Ribadiamo che i valori left e right associati all’arco (u,v) identificano
rispettivamente la prima e l’ultima visita del nodo v nel Cammino di Eulero.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
Occorrenza sinistra e destra
Per individuare la prima e l’ultima occorrenza di un nodo nel CDE di un albero
radicato, sfruttiamo il vettore delle somme prefisse S che serve per calcolare il
livello dei nodi. Per ogni arco (u,v) nel CDE calcoleremo due valori booleani, left
e right, che determineranno se, in corrispondenza di tale arco, si ha la prima e/o
l’ultima apparizione del nodo v. Se l’arco che precede e=(u,v) ha associato un
livello minore di quello di e, allora siamo in corrispondenza della prima
occorrenza di v:
left(e) = 1 sse S(e.pred) < S(e)
Se l’arco che segue e ha livello minore di e allora sarà l’ultima occorrenza di v:
right(e) = 1 sse S(e.next) < S(e)
Nota: left(u,v) = right(u,v) = 1 sse v è una foglia
È possibile definire, per ogni nodo, left(u) come l’indice nel CDE dell’unico arco
(u,v) con left(u,v)=1. Idem per right(v). Si assuma left(r)=0.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8