Algoritmi Paralleli e Distribuiti
a.a. 2008/09
Lezione del 05/05/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Cosa si deve fare nel parallelo
Ad ogni frammento si associa un identificativo:
• inizialmente i frammenti sono vertici isolati;
• l’identificativo del frammento coincide con l’etichetta del nodo che
è radice dell’albero che costituisce il frammento;
• ogni nodo capisce a quale frammento appartiene semplicemente
leggendo il nome della radice del suo albero.
Cosa si deve evitare nel parallelo:
• che il costo sia troppo elevato, quindi bisogna diminuire il più
possibile il numero dei processori usati, il numero di iterazioni
necessarie e l’altezza degli alberi che si gestiscono.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
2
Frammenti = Meganodi
Per generare i meganodi:
1. ogni nodo v seleziona un proprio vicino tramite una
funzione D:VV; si costruisce così una pseudo
foresta (V,F), dove F={(v, D(v)) | vV}.
2. ogni meganodo è identificato dalla radice dell’albero
che lo rappresenta ed ogni nodo di V conosce il nome
del meganodo a cui appartiene semplicemente
leggendo il nome dell’albero a cui appartiene.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
3
Come generare i meganodi
Per generare i meganodi:
1.
ogni nodo v seleziona il proprio vicino di numerazione minore. Ogni
ciclo nella pseudo foresta o è un loop o contiene due archi e in
ogni singolo albero il vertice di numerazione minima appartiene al
ciclo (e sarà usato come radice).
2.
tramite la tecnica del salto del puntatore, ogni albero della foresta è
ridotto ad una stella. In tal modo ogni meganodo è identificato dalla
radice della stella ed ogni nodo conosce il nome del meganodo a cui
appartiene semplicemente leggendo il nome della radice della
propria stella.
4
4
13
13
4
13
8
11
17
8
12
7
15
21
11
17
12
7
15
8
21
Algoritmi Paralleli e Distribuiti a.a. 2008/09
11
17
12
7
15
21
4
Grafo ridotto
Una volta che al passo k-esimo si sono individuati tutti i
meganodi del grafo su cui si sta operando, bisogna costruire il
nuovo grafo ridotto su cui si opererà al passo (k+1)-esimo. Il
nuovo grafo avrà nk+1 meganodi e tanti spigoli quanti sono
quelli che uniscono i meganodi, ovvero quegli spigoli di G
che uniscono vertici appartenenti a stelle differenti.
Per calcolare nk+1 bisogna numerare tutti i meganodi
utilizzando la tecnica delle somme prefisse.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
5
Strutture dati per MST
Input: il grafo G rappresentato come matrice di adiacenza pesata
W. W[i,j] = w(i,j) se (i,j)E altrimenti W[i,j] = .
Output: MST di G rappresentato tramite liste di adiacenza
Altre variabili:
nk: numero di nodi del grafo al passo k (n0 = n)
Wk: matrice di adiacenza del grafo al passo k (W0 = W)
mk(v): adiacente di v t.c. (u,mk(u)) è l’arco di costo minimo
incidente su u (nel grafo al passo k)
Algoritmi Paralleli e Distribuiti a.a. 2008/09
6
Algoritmo per MST
begin
k=0
while Wk contiene archi do
mk(u) = v t.c. min Wk(u,v)
Aggiungi (u,mk(u)) al MST
Esegui il salto del puntatore su mk(v)
Numera i meganodi
Costruisci Wk+1
k = k+1
end
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
Costo dell’algoritmo
Adoperiamo una PRAM con n2 processori, uno per ogni
elemento della matrice di adiacenza.
Al generico passo k, una componente connessa di n' > 1 nodi,
può originare al più n'/2 meganodi. Quindi dopo O(log n)
iterazioni del ciclo while l’algoritmo termina. Ciascuna
iterazione richiede tempo logaritmico:
a) La ricerca del minimo adiacente per ciascun nodo v richiede O(log n)
tempo su PRAM EREW, se invece si assume una PRAM ERCW
(con scrittura del minimo o priorità al processore di indice minimo) il
costo è O(1).
b) Il salto del puntatore per ridurre a stelle la pseudoforesta richiedere
tempo logaritmico su PRAM CREW.
c) La numerazione dei meganodi richiede tempo logaritmico con
somme prefisse su PRAM EREW.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
8
Costo dell’algoritmo
d) Si deve prestare attenzione nella generazione della matrice Wk+1 da
utilizzare al passo successivo: tra due meganodi si dovrà porre un
arco il cui peso è pari al minimo tra tutti gli archi che collegano i
nodi di un meganodo ai nodi dell’altro. Tale operazione si può
eseguire in O(log n) tempo su una PRAM EREW simulando una
scrittura concorrente. Si dovrà inoltre tenere traccia dell’arco del
grafo originale a cui tale costo si riferisce, al fine di poterlo
correttamente inserire nel MST.
L’algoritmo richiede quindi O(log2 n) tempo su una PRAM
CREW con n2 processori.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
9
Esempio
12
Grafo di partenza
rappresentato tramite
matrice W0
6
1
2
2
1
6
3
5
4
3
1
5
11
2
4
3
4
1
2
1
7
3
13
2
4
8
9
10
Passo 0:
meganodi iniziali = nodi isolati
Aggiungendo (u,m(u)) uV
11
1
2
6
4
13
3
8
9
5
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
12
10
10
Esempio
Dopo il salto del puntatore
rimangono 4 meganodi
11
1
2
4
3
(nella tabella sono riportati il costo
minimo di un arco tra due meganodi
e l’identificatore di tale arco)
8
9
7
5
2
1
La matrice di adiacenza W1
del grafo ridotto è:
6
13
12
10
3
4
1
2
3
4
-
2, (1,2)
4, (4,5)

2 2, (1,2)
-


3 4, (4,5)

-
5, (7,11)

5, (7,11)
-
1
4

Algoritmi Paralleli e Distribuiti a.a. 2008/09
11
Esempio
Passo 1:
4 meganodi isolati, aggiungendo (u,m(u)) u in W1
1
2
1
3
Dopo il salto del puntatore
rimane 1 solo meganodo
2
3
4
4
La matrice di adiacenza è vuota quindi al passo 2 l’algoritmo
12
termina.
6
1
3
2
Il MST risultante è:
5
2
1
1
3
1
2
5
11
2
4
3
1
7
13
2
4
8
Algoritmi Paralleli e Distribuiti a.a. 2008/09
9
10
12
Cosa si deve fare nel distribuito
Ad ogni frammento si associa un identificativo:
• inizialmente i frammenti sono a livello 0 e sono costituiti da un solo
nodo il cui identificativo coincide con quello del frammento;
• l’identificativo di un frammento è dato dal nodo di identificativo
maggiore fra i due estremi dello spigolo “portante” dello spanning
tree proprio del frammento.
Uniamo i frammenti in due modi:
• per combinazione di frammenti allo stesso livello k con lo stesso
spigolo di costo minimo. In tal caso si crea un nuovo frammento di
livello k+1;
• per assorbimento di un frammento di livello minore con uno di
livello maggiore.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
13
Cosa si deve evitare nel distribuito
Che i frammenti non coordinino le loro azioni:
• ogni nodo deve riconoscere a quale frammento appartiene e questa
informazione la deve ricevere in modo coordinato;
• fra tutti gli spigoli uscenti dal frammento, va trovato lo spigolo di
costo minimo relativo al frammento stesso;
Che l’unione dei frammenti non implichi un numero di
messaggi da trasmettere troppo elevato:
• evitare l’unione di frammenti grandi con vertici isolati: questo
potrebbe portare a trasmettere un numero quadratico di messaggi.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
14
Unione di frammenti
Consideriamo un frammento a livello l  0, fl, e sia l' il livello
del frammento al quale fl è connesso tramite il suo spigolo
uscente di costo minimo, el.
Allora si ha:
• combinazione di frammenti quando l=l' ed el = el'. Qui si crea un
nuovo frammento di livello l+1 il cui spigolo portante è lo spigolo
che ha unito i due frammenti a livello l;
• assorbimento di un frammento quando ll'. Il frammento di livello
minore è assorbito da quello di livello maggiore che si trasforma in
nuovo frammento mantenendo stesso livello e stesso spigolo
portante;
• nessuna operazione in tutti gli altri casi.
Algoritmi Paralleli e Distribuiti a.a. 2008/09
15
Esempio
10
c
16
15
m
9
l
7
8
a
f
17
1
2
g
3
11
6
i
5
4
12
b
d
18
e
14
h
13
Inizialmente ogni nodo è un
frammento di livello 0
Identificazione dell’arco
uscente di peso minimo
Combinazione
a
b
1
c
1
b
a
a
b
liv 1
d
2
d
e
2
c
c
f
3
3
f
d
g
4
e
e
liv 1
h
e
i
5
g
l
6
g
m
7
g
9
f
f
liv 1
e
f
liv 1
Assorbimento
g
m
Algoritmi Paralleli e Distribuiti a.a. 2008/09
16
Esempio
Identificazione dell’arco
uscente di peso minimo
a
b
c
d
16
g
14
c
e
f
m
h
5
5
e
i
g
h
l
6
g
g
Combinazione (niente)
g
Assorbimento
h
Identificazione dell’arco
uscente di peso minimo
a
e
i
b
c
d
16
g
h
14
i
c
e
f
m
14
l
e
d
f
m
g
h
e
d
liv 2
Assorbimento (niente)
m
liv 1
l
c
Combinazione
f
l
i
Algoritmi Paralleli e Distribuiti a.a. 2008/09
7
17
Esempio
Identificazione dell’arco
uscente di peso minimo
a
b
c
16
Combinazione
Assorbimento (niente)
b
c
d
liv 2
g
h
i
l
a
a
m
e
d
16
c
f
f
m
g
h
e
l
i
Algoritmi Paralleli e Distribuiti a.a. 2008/09
18