Date post: | 01-May-2015 |
Category: |
Documents |
Upload: | cleto-boni |
View: | 222 times |
Download: | 3 times |
Algoritmi Paralleli e Distribuitia.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
Algoritmi Paralleli e Distribuiti a.a. 2008/09 3
Frammenti = Meganodi
Per generare i meganodi:
1. ogni nodo v seleziona un proprio vicino tramite una funzione D:VV; si costruisce così una pseudo foresta (V,F), dove F={(v, D(v)) | vV}.
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 4
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
13
8 12
11 17 7 15 21
4
13
8 12
11 17 7 15 21
4
13
8 12
11 17 7 15 21
Algoritmi Paralleli e Distribuiti a.a. 2008/09 5
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 6
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 7
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 8
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 9
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.
Esempio
Grafo di partenza
rappresentato tramite
matrice W0
Passo 0:
meganodi iniziali = nodi isolati
Aggiungendo (u,m(u)) uV
Algoritmi Paralleli e Distribuiti a.a. 2008/09 10
23
1 4
11
12
7 13
6
5
8 9 10
1
2 3 45
6
1
1
1
2
2 2
3
34
4
1
4
2
3
11
6 8 9
5
13
7 12
10
Esempio
Dopo il salto del puntatorerimangono 4 meganodi
La matrice di adiacenza W1
del grafo ridotto è:(nella tabella sono riportati il costominimo di un arco tra due meganodie l’identificatore di tale arco)
Algoritmi Paralleli e Distribuiti a.a. 2008/09 11
1
4
2
3
11
6 8 9
5
13
7 12
10
1 2 3 4
1 2 3 4
1 - 2, (1,2) 4, (4,5)
2 2, (1,2) -
3 4, (4,5) - 5, (7,11)
4 5, (7,11) -
Esempio
Passo 1:
4 meganodi isolati, aggiungendo (u,m(u)) u in W1
Dopo il salto del puntatorerimane 1 solo meganodo
La matrice di adiacenza è vuota quindi al passo 2 l’algoritmo termina.
Il MST risultante è:
Algoritmi Paralleli e Distribuiti a.a. 2008/09 12
1
2 3
4
1
2 3
4
23
1 4
11
12
7 13
6
5
8 9 10
1
2
5
1
1
1
2
2 2
3
34
Algoritmi Paralleli e Distribuiti a.a. 2008/09 13
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 14
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 15
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 ll'. 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 16
Esempio
m l
f g
e h
i
c
d
a
b
1
2 3 4 5
6
78
9
10
11
12
1314
1516
17
18
a
b
1
b
a
2
c
d
2
d
c
3
e
f
3
f
e
4
g
e
5
h
g
6
i
g
7
l
g
9
m
f
Identificazione dell’arco uscente di peso minimo
Inizialmente ogni nodo è un frammento di livello 0
a b c d e fCombinazione
e f
Assorbimentog m
liv 1 liv 1 liv 1
liv 1
1
Algoritmi Paralleli e Distribuiti a.a. 2008/09 17
Identificazione dell’arco uscente di peso minimo
14
EsempioIdentificazione dell’arco uscente di peso minimo a b c d e fg m
16
c
14
e
5
h
Combinazione (niente)
Assorbimentoe fg m
h i l
e fg m
i l
ha b c d
16
c e
14
d
Combinazione
Assorbimento (niente)
e
f
g
m
il
h
c d
liv 1
liv 2
5
h
g
6
i
g
7
l
g
Algoritmi Paralleli e Distribuiti a.a. 2008/09 18
Esempio
Identificazione dell’arco uscente di peso minimo
a b
16
c
Combinazione
Assorbimento (niente)
e
f
g
m
il
h
c d
16
a
b a e
f
g
m
il
h
c d
liv 2