Algoritmi Paralleli e Distribuiti a.a. 2008/09 Lezione del 05/05/2009 Prof. ssa ROSSELLA PETRESCHI a...

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


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.


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


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.


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)


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


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.


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


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)


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 è:


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


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.


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.


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.


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



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


Esempio


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

Algoritmi Paralleli e Distribuiti a.a. 2008/09 Lezione del 05/05/2009 Prof. ssa ROSSELLA PETRESCHI a...

Documents

Transcript of Algoritmi Paralleli e Distribuiti a.a. 2008/09 Lezione del 05/05/2009 Prof. ssa ROSSELLA PETRESCHI a...