Date post: | 01-May-2015 |
Category: |
Documents |
Upload: | celia-marras |
View: | 218 times |
Download: | 0 times |
Algoritmi Paralleli e Distribuitia.a. 2008/09
Lezione del 22/05/2009
Prof.ssa ROSSELLA PETRESCHI
a cura del Dott. SAVERIO CAMINITI
Algoritmi Paralleli e Distribuiti a.a. 2008/09 2
Algoritmo per la Contrazione
Input: T albero binario 0/2 radicato in r
Output: T ridotto di 3 nodi
1. Numerare le foglie da sinistra a destra esclusi gli estremi e memorizzarle in un vettore A
2. while T ha più di 3 nodi do
1. Applica il rake in parallelo alle foglie in Adispari che sono figli sinistri
2. Applica il rake in parallelo alle foglie in Adispari che sono figli destri
3. A = Apari
Algoritmi Paralleli e Distribuiti a.a. 2008/09 3
Implementazione
Per realizzare il Passo 1:
• Calcola la numerazione inorder di T tramite il TDE (è possibile perché l’albero è 0/2);
• Individua le foglie (tutti i nodi v t.c. left[v]=right[v]=1);
• Numera le foglie (escludendo quella più a sx e quella più a dx) tramite somme prefisse.
Per realizzare il passo 2:
• Per i rake lavorano in parallelo i processori di indice dispari;
• Per discriminare le foglie che sono figli sinistri (destri) basta notare che la loro numerazione inorder nell’albero originale è minore (maggiore) di quella del padre;
• Per aggiornare A lavorano solo i processori di indice pari ed assegnano A[i/2] = A[i].
Algoritmi Paralleli e Distribuiti a.a. 2008/09 4
Analisi
Il passo 1 richiede costo O(n log n) sia per il TDE che per le somme prefisse.
Ciascuna iterazione del passo 2 richiede tempo costante. Ad ogni iterazione il vettore A dimezza, quindi in O(log n) iterazioni l’algoritmo termina.
Il costo complessivo è quindi O(n log n) su PRAM EREW con n processori.
Algoritmi Paralleli e Distribuiti a.a. 2008/09 5
Albero delle espressioni
Data un’espressione aritmetica, si associ alle foglie di un albero binario 0/2 le costanti dell’espressione e ai nodi interni le operazioni binarie.
Se l’albero delle espressioni è bilanciato, con costo O(n log n) si eseguono in parallelo le operazioni richieste da ogni nodo, livello per livello, fino a generare il risultato alla radice (esempio a sx). Se l’albero non è bilanciato il tempo parallelo richiesto può anche essere lineare (esempio a dx).
a b
+
c d
+
e f
g h
+
+
((a + b) (c d)) + ((e f) + (g + h))
g h
f
+e
d
+c
b
+a
a (b + (c (d + (e (f + (g h))))))
Algoritmi Paralleli e Distribuiti a.a. 2008/09 6
Valutare una espressione
Se l’albero non è bilanciato, per mantenere il tempo parallelo logaritmico, ci si accontenta che ogni nodo faccia solo un computo parziale prima di essere considerato completamente visitato.
Il computo parziale al nodo v è dato da avX+bv con av e bv costanti e X indeterminata che rappresenta il valore non noto della sottoespressione al nodo v. Ogni nodo è caratterizzato dalla etichetta (av,bv), inizialmente pari a (1,0).
Algoritmi Paralleli e Distribuiti a.a. 2008/09 7
Invariante
Si consideri il nodo u interno all’albero delle espressioni. Ad u è associato l’operatore {+, } e l’etichetta (au,bu), ai figli di u, v e w, sono associate le etichette (av,bv), (aw,bw), rispettivamente. Il valore della sottoespressione calcolata in u è dato da:
val(u) = (av val(v) + bv) (aw val(w) + bw)
Si noti che au e bu non appaiono nel calcolo di val(u) ma saranno presenti nel calcolo di val(p(u)).
Algoritmi Paralleli e Distribuiti a.a. 2008/09 8
Algoritmo per valutare un’espressione
Input: T albero delle espressioni tale che ogni nodo v conosce il padre p(v) e il fratello fr(v)
Output: val(T) = val(T'), T' risultato della contrazione
Passo 1: si assegna l’etichetta (1,0) a tutti i nodi di T
Passo 2: si applichi l’algoritmo di contrazione con l’aggiunta della condizione che ogni singola operazione di rake preservi l’invariante
Passo 3: su T' di radice r con operatore e foglie u e v contenenti le costanti cu e cv, rispettivamente, si calcoli:
val(T') = (au cu + bu) (av cv + bv) = val(T)
I passi 1 e 3 richiedono tempo parallelo costante. Quindi il tempo totale dipende dal passo 2.
Algoritmi Paralleli e Distribuiti a.a. 2008/09 9
Come l’operazione di rake preserva l’invariante
L’operazione di rake applicata ad una foglia u con fratello w, elimina u e p(u). Al fine di mantenere la validità dell’invariante, il contributo di u e p(u) al computo totale (ovvero au, ap(u), bu, bp(u)) deve essere conglobato in w (ovvero in aw e bw).
Poiché val(p(u)) = (aucu+bu) p(u) (awX+bw), il contributo di p(u) al computo di val(p(p(u))) è dato da:
ap(u)val(p(u)) + bp(u) = ap(u) ((aucu+bu) p(u) (awX+bw)) + bp(u)
da cui si possono calcolare i nuovi valori per w:
Quindi il passo 2 resta dominato dal costo computazionale del rake.
cuw
w(aw',bw')
(aw,bw)
(ap(u),bp(u))
(au,bu)p(u) = + p(u) =
a'w = ap(u) aw ap(u) (aucu+bu) aw
b'w = ap(u) (aucu+bu+bw) + bp(u) ap(u) (aucu+bu) bw + bp(u)
Algoritmi Paralleli e Distribuiti a.a. 2008/09 10
Esempio di calcolo d’espressione
Input: albero che corrisponde all’espressione
inizialmente (av, bv) = (1,0) per ogni nodo
2
+ 3
+
+ 2
7 +
+
3 +
4 5
5 2 1 1
((2+(3(4+5)))3)+(((5+2)2)+(7(1+1))) = 115
Algoritmi Paralleli e Distribuiti a.a. 2008/09 11
Esempio di calcolo d’espressione
Si numerano le foglie e si esegue il rake su quelle di numerazione dispari, prima quelle che sono figli sinistri e poi quelle che sono figli destri.
2
+ 3
+
+ 2
7 +
+
3 +
4 5
5 2 1 11
2 3
4
5 6
7 8
9
2
+ 3
+
2
7
+
+
4 5
2 1
2 3
4
6 7 8(1,5) (1,1)
(3,0) (2,10)2
+ 3
+
2
7
+
4 12
4 6
8 (1,1)(3,15)
Algoritmi Paralleli e Distribuiti a.a. 2008/09 12
Esempio di calcolo d’espressione
(2,10)2
+ 3
+
2
7
+
4 11
2 3
4 (1,1)(3,15)
2
+ 3
+
7
4
1
1
24 (1,1)
(3,15)
(1,14)
2 3
+
7
11 2
(1,1)
(1,14)
(1,27) 2
+
7
12
(1,1)
(1,14)(3,81)
2
+
7
11 (1,1)
(1,14)(3,81)2
+
1(7,21)(3,81)
(3 2 + 81) + (7 1 + 21) = 115