` di
Alma Mater Studiorum · Universita
Bologna
` DI SCIENZE MATEMATICHE, FISICHE E NATURALI
FACOLTA
Corso di Laurea Magistrale in Informatica
Algoritmi Avanzati
Jacopo Baldassarri
Anno Accademico 2011/2012
Indice
Introduzione
ii
0.1
Memoria Comune . . . . . . . . . . . . . . . . . . . . . . . . .
ii
0.2
Memoria Locale . . . . . . . . . . . . . . . . . . . . . . . . . .
iii
0.3
Master Theorem
iv
. . . . . . . . . . . . . . . . . . . . . . . . .
1 Algoritmi PRAM
1
1.1
Sommatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Somme Prefisse . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3
Ordinamento . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1.4
Elaborazione di Puntatori . . . . . . . . . . . . . . . . . . . .
8
1.5
Valutazione di Polinomi . . . . . . . . . . . . . . . . . . . . . 11
1.6
Punto Interno ad un Poligono . . . . . . . . . . . . . . . . . . 11
1.7
AND di valori . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8
La Tesi della Computazione Parallela . . . . . . . . . . . . . . 13
2 Algoritmi per Reti a Grado Limitato
2.1
2.2
15
Reti di interconnessione . . . . . . . . . . . . . . . . . . . . . 16
2.1.1
Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2
Shuffle . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3
Butterfly . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.4
Ipercubo . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Sommatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.1
Ipercubo . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2
Shuffle . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1
INDICE
2.2.3
i
Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3
Mergesort Bitonico . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4
Moltiplicazione di matrici . . . . . . . . . . . . . . . . . . . . 26
2.5
2.4.1
Mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.2
Ipercubo . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Trasformata di Fourier . . . . . . . . . . . . . . . . . . . . . . 31
Bibliografia
33
Introduzione
Parleremo di algoritmi paralleli che possono essere distindi in diverse
categoria, come spiegato in figura.
Figura 1: Algoritmi Paralleli
0.1
Memoria Comune
In questo tipo di architettura abbiamo dei problemi di accesso (concorrenza).
In presenza di processori sincroni abbiamo un ”ente globale” che coordina
tutti i processori, pu`o essere vista come una macchina di Von Neumann
parallela. Il modello PRAM `e un modello teorico perch`e al livello attuale
ii
INTRODUZIONE
iii
Figura 2: Memoria Comune
della tecnologia non `e realizzabile in concreto in modo efficiente. Ci serve
per capire se un problema `e inerentemente sequenziale e quindi non abbiamo grossi vantaggi in parallelo. In presenza del modello CONCORRENTE,
avremo bisogno di primitive di sincronizzazione per evitare l’inconsistenza
dei dati.
0.2
Memoria Locale
Nella memoria di un processore pu`o scrivere solo il suo processore, ma
possono leggere anche altri processori, con una organizzazione ad albero.
INTRODUZIONE
iv
Figura 3: Memoria Locale
Figura 4: Albero
0.3
Master Theorem
T (n) = aT (n/b) + cnβ
β≥0
In cui abbiamo che:
n `e la dimensione del problema
a `e il numero di chiamate ricorsive
b `e il numero di parti in cui si divide il problema
a≥1
b≥2
INTRODUZIONE
v
nβ rappresenta il tempo per dividere in sotto problemi e per poi ricom-
porlo
A questo punto confrontiamo α e β per capire la complessit`a del nostro
problema:
α=
Se abbiamo che:
α > β soluzione O(nα )
α = β soluzione O(nα log n)
β > α soluzione O(nβ )
log a
log b
Capitolo 1
Algoritmi PRAM
Vogliamo calcolare la sommatori di n numeri a1 , a2 , ..., an contenuti in un
vettore a[1...n]:
function SOMMATORIA (a[1. . .n], n): integer
var i, b: integer;
begin
b := a[1];
for i := 1 to n do
b := b + a[i];
return b;
end;
La computazione avviene nel modo seguete:
((...((a[1] + a[2]) + a[3]) + ...) + a[n − 1]) + a[n]
per`o sappiamo che per la propriet`a associativa della somma potrebbe anche
procedere in modo diverso, assumendo n pari:
(a[1] + a[2]) + (a[3] + a[4]) + ... + (a[n − 1] + a[n])
Se avessimo n/2 processori, potremmo eseguire simultaneamente ciascuna
somma a[i] + a[i + 1], per ogni i dispari, potrebbe essere eseguita in tempo
costante contemporaneamente alle altre. Iterando quindi il procedimento e
1
2
dimezzando sempre pi`
u la dimensione del problema, potremmo calcolare la
sommatoria in un tempo totale O(log n) che sarebbe un netto miglioramento
rispetto al tempo O(n) che `e necessario per calcolare la stessa somma della
funzione sopra citata.
Il modello pi`
u semplice di computazione parallela `e detto PRAM (”Parallel
Random Access Machine”) in cui abbiamo pi`
u processori sincroni, cio`e che
condividono lo stesso ciclo di clock e una memoria globale condivisa fra tutti
i processori. Il modello ha le seguenti caratteristiche principali:
Ogni processore esegue la stessa istruzione ma su dati diversi.
Possiamo far lavorare un sottoinsieme di processori mentre alcuni restano
inattivi.
Ogni processore attivo `e sincronizzato, l’istruzione successiva non pu`o
iniziare finch`e tutti non hanno concluso l’istruzione corrente.
La memoria `e utilizzata dai processori per scambiarsi dati in O(1)
tempo.
Utilizzeremo il seguente costrutto per esprimere l’esecuzione in parallelo di
istruzioni:
for all i where inf ≤ i ≤ sup do in parallel operazionei
si esegue contemporaneamente operazionei per ogni i compreso fra i due estremi inf e sup. Esistono diverse varianti del modello PRAM, in base alla
possibilit`a, da parte dei processori, di leggere/scrivere la memoria contemporaneamente:
EREW (”Exclusive Read Exclusive Write”) non `e consentito ne la
scrittura ne la lettura contemporanea.
CREW (”Concurrent Read Exclusive Write”) `e possibile leggere con-
temporaneamente ma non scrivere.
CRCW (”Concurrent Read Concurrent Write”) `e possibile sia leggere
che scrivere contemporaneamente.
1.1 Sommatoria
1.1
3
Sommatoria
Vogliamo quindi calcolare la sommatoria utilizzando un algoritmo parallelo; assumiamo per semplicit`a che la dimensione dell’input n sia una potenza
di 2 (`e comunque sempre possibile renderlo tale, aggiungendo degli 0 all’input) e che i numeri siano elencati an , an+1 , ..., a2n−1 . Possiamo immaginarci
che ogni numero ai sia memorizzato in una foglia di un albero binario completo di 2n − 1 nodi, indicizzati come uno heap, in cui la radice ha indice 1 e i
figli di un nodo i hanno rispettivamente indice 2i per il figlio sinistro e 2i + 1
per il figlio destro. Partendo dal penultimo livello a salire, considerando tutti
i nodi di uno stesso livello, possiamo calcolare in ai la somma dei suoi figli
a2i e a2i+1 che corrisponde alla sommatoria dei numeri che si trovano nelle
foglie del sotto albero radicato nel nodo i, per 1 ≤ i ≤ n − 1.Abbiamo quindi
la nostra funzione che diventa nel modo seguente:
Figura 1.1: Albero Sommatoria
1.1 Sommatoria
4
function SOMMATORIA (a[n..2n − 1], n): integer
begin
for k := logn − 1 downto 0 do
for all i where 2k ≤ i ≤ 2k+1 − 1 do in parallel
a[i] := a[2i] + a[2i + 1];
SOMMATORIA:=a[1]
end;
Possiamo vedere che il for esterno viene ripetuto O(log n) volte, mentre il for
all interno richiede tempo O(1), abbiamo quindi una complessit`a della funzione SOMMATORIA pari a O(log n) con un numero di processori utilizzati
pari a O(n). Possiamo a questo punto per`o notare che ogni algoritmo parallelo, impiega un ammontare di lavoro L, che rappresenta il tempo richiesto se
lo stesso algoritmo fosse eseguito in maniera sequenziale usando un singolo
processore, dato dal prodotto di P (numero di processori) per T (tempo).
Nel caso dell’algoritmo sopra, il nostro lavoro `e quindi O(n log n) che `e peggiore di quello del migliore algoritmo sequenziale che `e O(n). Dobbiamo
quindi modificare il nostro algoritmo parallelo in modo da avere un lavoro
pari almeno a O(n). Possiamo ridurre il numero di processori dividendo il
nostro input in O(n/ log n) parti di dimensione O(log n) elementi e facendo
sommare ad ogni processore in modo sequenziale i numeri di ogni parte. In
questo modo il nostro problema originario `e stato ridotto in tempo O(log n)
ed usando O(n/ log n) processori ad un problema pi`
u piccolo di dimensione
O(n/ log n). Al problema cos`ı modificato possiamo quindi applicare la funzione SOMMATORIA che a questo punto richiede O(log(n/ log n)) tempo
usando O(n/ log n) processori, ottenendo un lavoro ottimo pari a O(n). Gli
elementi da sommare sono indicati con an , an+1 , ..., a2n−1 . Viene eseguita
una prima fase dove ogni processore somma sequenzialmente gli elementi di
un gruppo di log n elementi. Poi viene fatta la sommatoria parallela degli
n/ log n elementi che contengono i risultati della prima fase. Si usa un vettore
a[1...2n − 1] dove gli elementi da sommare sono memorizzati in a[n...2n − 1]
1.2 Somme Prefisse
5
Figura 1.2: Sommatoria Ottima
ed il risultato in a[1]. Ottenendo cos`ı un lavoro ottimo pari a O(n).
procedure SOMMATORIA (a[n..2n − 1], n): integer
begin
for all j where 1 ≤ j ≤ n/ log n do in parallel begin
a[n/ log n + j − 1] := a[n + (j − 1) log n];
for i := 1 to log n − 1 do
a[n/ log n + j − 1] := a[n/ log n + j − 1] + a[n + (j − 1) log n + i];
end;
for k := log(n/ log n) − 1 downto 0 do
for all j where 2k ≤ j ≤ 2k+1 − 1do in parallel
a[j] := a[2j] + a[2j + 1];
end;
1.2
Somme Prefisse
Prendiamo ora in considerazione un problema simile al precedente della
sommatoria di n numeri. Dati n numeri interi a1 , a2 , ..., an calcolare tutte
Pi
per i = 1, 2, ..., n. Utilizzeremo come in
le somme parziali bi =
j=1 aj
precedenza un input che possiamo sempre considerare di dimensioni potenza
di due e che i numeri siano indicati con an , an+1 , ..., a2n−1 sempre memorizzati
nelle foglie di un albero binario completo di 2n − 1 nodi realizzato con un
vettore a[2n − 1]. Viene prima fatta una fase ascendente in cui si esegue la
stessa computazione della funzione SOMMATORIA, mettendo il risultato in
b1 . Poi viene fatta una fase discendente in cui si calcola il valore bi di ogni
1.2 Somme Prefisse
6
altro nodo nel seguente modo: il bi di un figlio destro `e uguale a quello del
padre, mentre il bi di un figlio sinistro `e uguale a quello del padre meno il
valore ai+1 del fratello per 2 ≤ i ≤ 2n − 1. Otterremo in questo modo che
il valore bi di un nodo sar`a sempre uguale alla somma degli aj dei nodi che
sono allo stesso livello di bi e che hanno come indice j minore o uguale ad i.
Quindi bn+1 = an + an+1 + ... + an+i come volevamo ottenere.
Figura 1.3: Albero Somme Prefisse
procedure SOMMEPREFISSE(a[n...2n − 1], b[n...2n − 1]): integer
begin
b[1] := SOM M AT ORIA(a[n...2n − 1], n);
for k := 1 to log n do
for all i where 2k ≤ i ≤ 2k+1 − 1 do in parallel
if odd(i)
then b[i] := b[(j − 1)/2]
else b[i] := b[i/2] − a[i + 1];
end;
Possiamo vedere che la complessit`a della procedura `e O(log n) e vengono utilizzati O(n) processori che possono per`o essere ridotti ad O(n/ log n) usando
il metodo visto in precedenza per la sommatoria, ottenendo cos`ı un lavoro
ottimo pari a O(n).
1.3 Ordinamento
1.3
7
Ordinamento
Veniamo quindi ad uno dei pi`
u classici dei problemi, il problema dell’ordinamento di n numeri distinti a1 , a2 , ..., an . Possiamo progettare un algoritmo
detto ”torneo” per risolvere il problema. Confrontiamo ogni numero ai con
tutti gli altri numeri e andiamo a contare quante volte esso risulta essere
”perdente” (minore o uguale ai incluso) oppure ”vincente” (maggiore). Il
numero di volte che l’elemento risulta essere perdente ci dice in che posizione
deve stare.
procedure TORNEO(a[1...n], n): integer
begin
for all i, j where 1 ≤ i, j ≤ n do in parallel
if a[i] ≤ a[j] then V [i, j] := 1 else v[i, j] := 0;
for all j where 1 ≤ j ≤ n do in parallel
P [j] := SOM M AT ORIA(j − esima colonna di V, n);
for all j where 1 ≤ j ≤ n do in parallel
a[P [j]] := a[j];
end;
La procedura ha complessit`a O(log n) utilizzando per`o n2 processori in un
modello CREW. Se volessimo utilizzare un modello EREW dovremmo evitare
che si verifichino conflitti in lettura sulla stessa cella di memoria, il generico
elemento a[i], per ciascun 1 ≤ i ≤ n, `e coinvolto in n istruzioni diverse di
confronto allo stesso momento dentro al primo for dove viene confrontato
con a[j], lo stesso tipo di problema ovviamente si verifica anche per a[j]
stesso. Possiamo risolvere il problema facendo n copie di ciascun a[i] ed n
copie di ciascun a[j] in tempo O(log n), in modo che gli n2 processori possano
accedere in lettura in tempo O(1) ad un unica coppia di valori a[i] e a[j].
Possiamo quindi vedere una procedura che risolve questo problema, effettua
n copie di un dato d mettendole negli n elementi di un vettore copia[1...n]:
1.4 Elaborazione di Puntatori
8
procedure REPLICA(copia[1...n], d, n):integer
begin
copia[1] := d;
for k := 0 to log n − 1 do
for all i where 1 ≤ i ≤ 2k do in parallel
copia[i + 2k ] := copia[i];
end;
La procedura REPLICA richiede tempo O(log n) ed O(n) processori. Possiamo quindi richiamarla in parallelo 2n volte ed effettuare n copie di ciascun
a[i] e di ciascun a[j] in tempo O(log n) usando O(n2 ) processori. Infine la procedura TORNEO pu`o essere eseguita con il modello EREW sempre in tempo
O(log n) ma usando solo O(n2 / log n) processori. Il lavoro della nuova versione della procedura TORNEO risulta pertanto essere O(n2 ) che `e comunque
peggiore del lavoro ottimo O(n log n) del miglior algoritmo sequenziale.
1.4
Elaborazione di Puntatori
Riconsideriamo il problema delle SOMMEPREFISSE dove gli n dati sono
memorizzati questa volta in una lista e l’ordine col quale calcolarne le somme
prefisse `e determinato da come tali dati sono tra loro concatenati nella lista
tramite i puntatori. Indichiamo con a[i] il valore della lista gestito dal processore i-esimo e con succ[i] il cursore all’elemento successivo della lista, dove
inizialmente succ[i] = 0 se e solo se a[i] `e l’ultimo valore della lista.
procedure SOMMEPREFISSE (a[1...n], b[1...n], succ[1...n], n):integer
begin
for all i where 1 ≤ i ≤ n do in parallel
b[i] := a[i];
for k := 1 to dlog ne do
for all i where 1 ≤ i ≤ n do in parallel
if succ[i] 6= 0 then begin
b[succ[i]] := b[i] + b[succ[i]];
1.4 Elaborazione di Puntatori
9
succ[i] := succ[succ[i]]
end
end
La tecnica utilizzata nel for all interno `e detta ”pointer jumping”. Si osservi
che non si verificano mai dei conflitti da parte di pi`
u processori per accedere
alla stessa locazione di memoria. Infatti per i 6= j abbiamo sempre che
succ[i] 6= succ[j] oppure succ[i] = succ[j] = 0 che viene mantenuto per tutta
l’esecuzione della procedura. Possiamo quindi usare un modello EREW e
la procedura richiede tempo O(log n) usando n processori. Il lavoro della
Figura 1.4: Salto Puntatori
procedura `e O(n log n) che non `e ottimo, ma questo pu`o essere abbassato
ad un lavoro ottimo di O(n) con un algoritmo piuttosto complicato che non
verr`a riportato qua.
Vediamo un altro esempio di utilizzo della tecnica del ”pointer jumping”
per calcolare il livello dei nodi di un albero binario realizzato con puntatori.
Combineremo tale tecnica con la tecnica del ”ciclo Euleriano”. Ricordiamo
che un ”ciclo Euleriano” di un grafo orientato G `e un ciclo che include ogni
arco una ed una sola volta e che G contiene un ciclo Euleriano se e solo se `e
connesso e per ciascun nodo il numero di archi entranti `e uguale al numero
di archi uscenti. Per calcolare la profondit`a di un albero binario B di n
nodi, si considera un ciclo Euleriano del grafo orientato B 0 ottenuto da B,
dove tale ciclo `e rappresentato con una lista mono direzionale di 3n elementi
sulla quale viene applicata la tecnica del salto dei puntatori. Ogni nodo u
1.4 Elaborazione di Puntatori
di B `e sostituito con tre elementi di una lista, che individuiamo con x, y, z
in modo che i risultanti 3n elementi siano gestiti ciascuno da uno ed un solo
processore.
l’elemento x del nodo u vale +1 e punta all’elemento x del figlio sinistro
di u, se esiste, oppure all’elemento y di u stesso, altrimenti;
l’elemento y del nodo u vale 0 e punta all’elemento x del figlio destro
di u, se esiste, oppure all’elemento z di u stesso, altrimenti;
l’elemento z del nodo u vale -1 e punta all’elemento y del padre di u,
se u `e un figlio sinistro, oppure all’elemento z del padre di u, se u `e un
figlio destro, oppure a 0, se u `e la radice.
La lista inizia con l’elemento x della radice e termina con l’elemento z della
radice. La lista pu`o essere costruita in tempo costante O(1), eseguendo la
procedura SOMMEPREFISSE su tale lista, `e facile vedere che l valore b di
ciascun elemento z rappresenta il livello del corrispondente nodo u. Quindi i
livelli dei nodi di B possono essere calcolati in tempo O(log n) usando O(n)
processori.
Figura 1.5: Ciclo Euleriano
10
1.5 Valutazione di Polinomi
1.5
11
Valutazione di Polinomi
Dato un polinomio nella forma p(x) = an−1 xn−1 +an−2 xn−2 +...+a1 x+a0
vogliamo valutarlo in un punto preciso q, cio`e vogliamo calcolare p(q) nel
modello EREW.
Procediamo calcolando inizialmente le potenze q 0 , ..., q n−2 , q n−1 di q, dato che
il generico q i = qq i−1 con 1 ≤ i ≤ n − 1, si considerano i prodotti prefissi b
del vettore x contenente un 1 seguito da n − 1 copie di q. Infine si calcolano
i prodotti ai q i per 0 ≤ i ≤ n − 1 nel vettore r in cui poi verr`a effettuata la
sommatoria.
function VALUTAPOLINOMIO (a[1...n], x[1...n], q):real
begin
COPIA (q, n, x);
x[1] := 1;
PRODOTTIPREFISSI(x, n);
for all j where 0 ≤ j ≤ n/ log n − 1 do in parallel
for i := 0 to log n − 1 do
r[n + j ∗ n/ log n + i] := a[j ∗ n/ log n + i] ∗ b[n + j ∗ n/ log n + i];
SOMMATORIA (r, n);
VALUTAPOLINOMIO := r[1];
end;
1.6
Punto Interno ad un Poligono
Dato un generico poligono vogliamo sapere se questo `e convesso oppure
no. Forniamo una rappresentazione del poligono elencando i suoi vertici in ordine orario/antiorario e specificando le coordinate di ogni vertice:
Vi = (xi , yi ). Consideriamo ora un generico punto del poligono e per vedere
se questo `e convesso, tracciamo la perpendicolare al punto e considerando
solo la parte superiore andiamo a contare le volte che la perpendicolare interseca i lati del poligono. Se la perpendicolare interseca i lati del poligono
un numero pari di volte allora il punto `e esterno al poligono e quindi esso
1.7 AND di valori
12
Figura 1.6: Poligoni
non `e convesso, altrimenti se la perpendicolare interseca i lati del poligono
un numero dispari di volte, il punto `e interno e il poligono `e convesso.
La procedura andr`a a considerare in parallelo tutti i lati del poligono e se
questi sono nella parte superiore alla perpendicolare, andr`a a vedere se intersecano la retta perpendicolare. Usiamo un vettore di n elementi, pari ai lati
del poligono, di valori booleani e se interseca la perpendicolare lo imposto
ad 1 altrimenti lo lascio a 0; una volta considerati tutti i lati vado a fare la
somma dei valori booleani del vettore per vedere se ho ottenuto un numero
di intersezioni pari oppure dispari.
1.7
AND di valori
Vogliamo calcolare l’AND di n valori booleani di un vettore.
Consideriamo un modello CRCW, assumendo che se pi`
u processori vogliono
scrivere la stessa locazione di memoria, uno solo riuscir`a effettivamente a
farlo.
procedure AND−CRCW (b[1...n]):boolean;
begin
x := true;
for all j where q ≤ j ≤ n do in parallel
if not b[j] then x := f alse;
1.8 La Tesi della Computazione Parallela
13
AND−CRCW:= x;
end;
Il primo processore che riuscir`a a scrivere effettivamente f alse nella locazione
di memoria x far`a in modo che la procedura restituisca appunto f alse dato
che basta che uno degli n valori sia f alse per fare si che tutto l’AND restituisca f alse.
Otteniamo cos`ı un tempo T = O(1), un numero di processori pari a P = O(n)
per un lavoro ottimo L = O(n), anche se allo stato attuale delle tecnologia
`e impossibile realizzare un modello che permette la scrittura in memoria in
tempo O(1).
1.8
La Tesi della Computazione Parallela
Abbiamo visto come l’introduzione di pi`
u processori che lavorano in parallelo possa abbassare radicalmente la complessit`a in tempo di alcuni problemi.
Una legittima aspirazione sarebbe quella di di risolvere in tempo polinomiale
con algoritmi paralleli problemi che sono intrattabili con algoritmi sequenziali.
La Tesi della Computazione Parallela asserisce che ogni problema risolvibile
in tempo polinomiale con un algoritmo parallelo pu`o essere risolto in spazio
polinomiale con un algoritmo sequenziale. Come si ignora se P=NP oppure
no, cos`ı neanche si conosce se P-SPAZIO=P, dove P-SPAZIO `e la classe dei
problemi intrinsecamente superpolinomiale. Abbiamo quindi questo problema, anche se `e opinione comune che P-SPAZIO contenga problemi di complessit`a intrinsecamente superpolinomiale e che quindi problemi intrattabili
sequenzialmente restino tali anche in parallelo.
La classe dei problemi che si ritiene trattabili `e detta NC e, come conseguenza
della Tesi della Computazione Parallela, si ha che NC coincide con la classe di
problemi P che sono risolubili con una quantit`a di memoria che `e O(logk n)
con k costante. I problemi che abbiamo visto nella parte precedente sono
tutti problemi in NC.
1.8 La Tesi della Computazione Parallela
Come si ignora se P=NP, cos`ı non si conosce se P=NC. Se si trovasse un algoritmo parallelo con complessit`a temporale polilogaritmica che utilizzi una
quantit`a di processori polinomiale per un solo problema Log-Spazio-completo
(un problema in P `e detto Log-Spazio-completo se ogni altro problema in P `e
riducibile ad esso con una trasformazione che richiede spazio polilogaritmico),
allora se ne potrebbero trovare per tutti i problemi in P e quindi risulterebbe
P=NC.
Figura 1.7: Relazioni di Contenimento di Problemi
14
Capitolo 2
Algoritmi per Reti a Grado
Limitato
Abbiamo appena visto il modello PRAM che per`o resta un modello teorico, data l’impossibilit`a di realizzazione con le tecnologie attuali. In pratica
perch`e un modello parallelo sincrono sia effettivamente realizzabile occorre
che la memoria no sia affatto globale e che i processori comunichino fra loro
soltanto attraverso una prefissata rete di interconnessione. Tale rete `e rappresentata con un grafo non orientato, i cui nodi corrispondono ai processori e
i cui archi sono le interconnessioni fra i processori. I processori possono cos`ı
comunicare in tempo O(1) se e solo se c’`e un arco che li collega. Dobbiamo
dire per`o che una rete affinch`e sia effettivamente costruibile non pu`o essere un
grafo completo! In pratica abbiamo che, detto g il grafo massimo di dei nodi,
cio`e il numero massimo di archi incidenti in un nodo, dobbiamo avere che g
sia ”piccolo”, possibilmente limitato da una costante. Dati due processori la
loro distanza `e rappresentata dal numero minimo di archi tra tutte le catene
che li uniscono, ed il diametro d della rete `e uguale alla distanza massima
tra tutte le coppie di processori. Vedremo di seguito alcune architetture di
reti, mesh, shuffle, butterfly ed ipercubi e analizzeremo poi alcuni problemi
utilizzando tali reti, mostrando come questi problemi possano essere risolti
in tempo ottimo come nel modello PRAM.
15
2.1 Reti di interconnessione
2.1
Reti di interconnessione
Considereremo quattro diverse architetture di reti di interconnessione che
sono la mash, la shuffle, la butterfly e l’ipercubo. Vediamole ora in dettaglio.
2.1.1
Mesh
Una mesh quadrata gli n processori, con n = p2 per p intero positivo,
√
√
sono organizzati in una matrice quadrata di dimensione n × n in cui un
√
generico processore Pi,j , con 1 ≤ i, j ≤ n, `e connesso con i processori Pi,j±1
e Pi±1,j . Il grado massimo di ogni nodo g `e 4 mentre il diametro d della mesh
√
`e pari a n. Esistono anche delle versioni alternative alla classica mesh: la
Figura 2.1: Mesh con n = 16 processori
mesh ciclica, dove sono connessi ta loro anche il primo e l’ultimo processore
di ogni riga/colonna e la mesh toroidale, in cui l’ultimo processore di ogni
riga/colonna `e connesso con il primo processore della riga/colonna successiva.
2.1.2
Shuffle
In una shuffle gli n processori, con n = 2p per p intero positivo, sono
numerati da 0 a 2p − 1 e vi sono due tipi di connessioni fra i processori. Le
connessioni di scambio non orientate sono tra i processori Pi e Pi+1 per ogni
16
2.1 Reti di interconnessione
i pari, mentre le connessioni di mescolamento orientate escono dal processore
Pi per o ≤ i ≤ n − 2 ed entrano nel processore Pj , dove j = 2i mod (n − 1),
con un ulteriore connessione da Pn−1 a se stesso.
Possiamo vedere come percorrendo le connessioni di mescolamento p = log n
volte a partire da Pi per 1 ≤ i ≤ n − 2 si ritorna al processore Pi stesso.
Usando anche le connessioni di scambio `e anche possibile raggiungere un
qualsiasi altro processore in O(log n) passi. Abbiamo qui un grado massimo
g pari a 3 ed un diametro d pari a O(log n).
Figura 2.2: Shuffle con n = 8 processori
2.1.3
Butterfly
In una butterfly di grado k, gli n processori, con n = (k +1)2k per k intero
positivo, sono disposti in k + 1 righe e 2k colonne, in cui il generico elemento
Pi,j , con 1 ≤ i ≤ k, 0 ≤ j ≤ 2k − 1, `e connesso con i processori Pi−1,j e Pi−1,m ,
dove m `e l’intero ottenuto complementando l’i-esimo bit pi`
u significativo della
rappresentazione binaria di j. Abbiamo in questo caso un grado massimo g
di ogni nodo pari a 4 ed un diametro d pari a O(k) = O(log n). Possiamo
anche notare che i processori della riga 0 (o della riga k) possono essere visti
come le foglie comuni a 2k alberi binari completi le cui radici sono i processori
della riga k (o della riga 0).
17
2.1 Reti di interconnessione
Figura 2.3: Butterfly con rango k = 3 e n = (k + 1)2k = 32 processori
2.1.4
Ipercubo
In un ipercubo di dimensione k (k intero positivo), abbiamo che gli n = 2k
processori sono numerati da 0 a 2k − 1 ed il generico processore Pi `e connesso
con tutti i processori Pj tali che le rappresentazioni binarie di i e j differiscono
per il valore di un singolo bit. Otteniamo qui un grado di ogni dono g ed un
diametro d pari entrambi a k = log n.
Figura 2.4: Ipercubo con dimensione k = 4 e n = 24 = 16 processori
18
2.2 Sommatoria
2.2
19
Sommatoria
Andiamo ora a vedere come risolvere il problema della sommatoria con
le varie reti di interconnessione sopracitate, vedremo prima la procedura
SOMMATORIA-IPERCUBO, la procedura SOMMATORIA-SHUFFLE ed
infine la procedura SOMMATORIA-MESH.
2.2.1
Ipercubo
Siano ao , a1 , ..., an−1 gli n numeri da sommare, con n = 2k e si consideri
un ipercubo di dimensione k, tale che il dato ai sia contenuto inizialmente nel
processore Pi , per 0 ≤ i ≤ n − 1. Consideriamo dapprima gli n/2 processori
con indici minori (con il bit pi`
u significativo a 0), i quali individuano un
ipercubo di dimensione k − 1, ed ognuno di essi somma in parallelo il suo
dato con quello contenuto nel corrispondente processore dell’altro ipercubo
di dimensione k − 1 formato dagli n/2 processori con indici maggiori (con il
bit pi`
u significativo ad 1). Il procedimento viene poi iterato considerando gli
n/4, n/8, ..., n/n processori con indici minori, che corrispondono ad ipercubi
di dimensione k − 2, k − 3, ..., 0, considerando cio`e gli indici con anche il
secondo, terzo,..., ultimo bit pi`
u significativo a 0. Dopo k = log n iterazione,
il risultato sar`a ottenuto nel processore P0 . Otteniamo la seguente procedura
che richiede tempo O(log n) utilizzando n processori.
procedure SOMMATORIA−IPERCUBO a[0...n − 1]);
begin
for i = log n downto 0 do begin
h := 2i
for all j where 0 ≤ j ≤ h − 1 do in parallel
begin b[j] ← a[j + h]; a[j] := a[j] + b[j]; end;
end;
end;
2.2 Sommatoria
Figura 2.5: Sommatoria eseguita su ipercubo con k = 4 e n = 2k = 16
processori
Il lavoro della procedura `e O(n log n) che pu`o comunque essere reso ottimo
considerando una sequenza di O(n log n) elementi da sommare.
2.2.2
Shuffle
Consideriamo ora sempre lo stesso problema prendendo una shuffle di
n = 2k processori, assumendo ancora che ai sia contenuto inizialmente nel
processore Pi , per 0 ≤ i ≤ n − 1. Consideriamo due procedure ausiliarie
SCAMBIA e MESCOLA. La procedura SCAMBIA(ai ) ha come effetto quello
di scambiare in tempo O(1) gli ai dei processori di indice pari con quelli dei
processori di indice dispari, mentre la procedura MESCOLA(ai ) ha l’effetto
di spostare in tempo O(1) gli ai tra i processori in accordo alle connessioni
di mescolamento.
La procedura risulta essere molto semplice e consiste in log n chiamate di
MESCOLA e SCAMBIA alternate, che utilizzano una sequenza di appoggio
b0 , b1 , ..., bn−1 . Otteniamo cos`ı un tempo di esecuzione O(log n) utilizzando
20
2.2 Sommatoria
n processori.
21
procedure SOMMATORIA−SHUFFLE(a[0...n − 1]);
begin
for i to log n do
for all j where o ≤ j ≤ n − 1 do in parallel
MESCOLA(a[j]);
b[j] := a[j];
SCAMBIA(b[j]);
a[j] := a[j] + b[j]
end
end;
Figura 2.6: Sommatoria eseguita su shuffle
2.2.3
Mesh
Risolviamo infine il problema della sommatoria usando una rete di interconnessione a mesh quadrata. Siano a1,1 , ..., a1,p , a2,1 , ..., a2,p , ..., ap,1 , ..., ap,p
gli n = p2 elementi da sommare, tali che ai,j sia contenuto inizialmente nel
√
processore Pi,j , per 1 ≤ i, j ≤ n. Partiamo sommando gli elementi dell’ultima riga agli elementi della penultima riga, poi andremo a sommare gli
elementi della penultima a quelli della terzultima riga, risalendo cos`ı fino alla
2.2 Sommatoria
22
prima riga, dove verranno poi sommati i risultati parziali da destra verso
sinistra, ottenendo cos`ı il risultato nel processore P1,1 .
procedure SOMMATORIA−MESH(a[1, 1], a[1, 2], ...a[p, p]);
begin
for i := p − 1 downto 1 do
for all i, j where 1 ≤ j ≤ p do in parallel
begin b[i, j] ← a[i + 1, j]; a[i, j] := a[i, j] + b[i, j] end;
for i := p − 1 downto 1 do
for all i, j where i = 1 do in parallel
begin b[i, j] ← a[i, j + 1]; a[i, j] := a[i, j] + b[i, j] end
end;
√
Il tempo della procedura cos`ı realizzata `e O( n utilizzando n processori,
√
ottenendo un lavoro pari a O(n n che possiamo rendere ottimo utilizzando
√
una sequenza di elementi da ordinare pari a O(n n.
Figura 2.7: Sommatoria eseguita su una mesh
2.3 Mergesort Bitonico
2.3
23
Mergesort Bitonico
Consideriamo ora un algoritmo per risolvere il problema della sommatoria, ideato da Batcher negli anni ’60.
Presa una sequenza a0 , a1 , ..., an−1 si dice unimodale se esiste un indice i,
0 ≤ i ≤ n − 1, tale che a0 ≤ a1 ≤ ... ≤ ai e ai ≥ ai+1 ≥ ... ≥ an−1 .Diremo
inoltre che una sequenza `e bitonica se questa `e unimodale oppure se `e ottenibile con una traslazione ciclica da una sequenza unimodale.
La sequenza 2, 6, 7, 8, 10, 3, 1, 0 `e unimodale e quindi anche bitonica. Consideriamo ora una propriet`a importante delle sequenza bitoniche.
Presa una sequenza bitonica A = a0 , a1 , ..., a2m−1 , allora le due sequenze:
AMIN = min{a0 , am }, min{a1 , am+1 }, ..., min{am−1 , a2m−1 }
AMAX = max{a0 , am }, max{a1 , am+1 }, ..., max{am−1 , a2m−1 }
sono esse stesse bitoniche.
Questa propriet`a ci suggerisce un algoritmo parallelo di tipo ”divide & impera” per ordinare una sequenza di n elementi con n potenza di 2. L’algoritmo
consiste, se n > 1, nel dividere A in AMIN e AMAX e riapplicare ricorsivamente la
procedura alle due sequenze bitoniche AMIN e AMAX . Le relazioni di ricorrenza
risultano pertanto:
T (n) = d,
per n = 1,
T (n) = T (n/2) + c,
per n > 1,
dove c e d sono due costanti, e quindi T (n) `e O(log n), usando O(n) processori. Una sequenza qualsiasi A di lunghezza n = 2i pu`o essere vista come n/2
sequenza bitoniche di lunghezza 2. Una volta che si `e ordinato in parallelo
queste n/2 sequenze bitoniche, in modo che siano alternate una sequenza
crescente ad una sequenza decrescente, si utilizza il fatto che la concatenazione di una sequenza crescente con una decrescente forma una sequenza
bitonica. In questo modo, si considerano n/4 sequenze bitoniche lunghe 4,
che vengono ordinate con l’algoritmo per le sequenze bitoniche, poi n/8 sequenze lunghe 8 e cos`ı via, finch`e si arriva ad ordinare una singola sequenza
2.3 Mergesort Bitonico
bitonica lunga n.
Osserviamo che la costruzione di sequenze bitoniche lunghe 2i+1 richiede l’ordinamento di sequenza bitoniche lunghe 2i , che costa O(log 2i ) = O(i) temP
po. Otteniamo quindi un tempo complessivo di O( ki=1 i), che cresce come
O(log2 n). Poich`e il numero massimo di confronti che vengono eseguiti contemporaneamente `e n/2, il numero di processori richiesto `e O(n), otteniamo
quindi un lavoro pari a O(n log2 n), che risulta essere decisamente migliore
dell’algoritmo TORNEO visto in precedenza.
Torna molto utile visualizzare lo screma di computazione dell’algoritmo,
come illustrato dalla figura 2.8 per n = 16. Le linee orizzontali rappre-
Figura 2.8: Computazione dell’ algoritmo Mergesort Bitonico
sentano i ”canali” sui quali transitano da sinistra verso destra gli elementi da
ordinare. Le frecce verticali rappresentano confronti tra coppie di elementi,
che entrano da sinistra ed escono da destra, in modo che l’elemento maggiore esca sul canale indicato dalla freccia ed il minore sul canale indicato
dal pallino. Vediamo che l’algoritmo ”mergesort bitonico” ha k iterazioni (4
nella figura 2.8) e che ogni iterazione i, per 1 ≤ i ≤ k, richiede proprio i passi
per ordinare n/2i sequenze bitoniche lunghe 2i .
Riportiamo la procedura dell’algoritmo mergesort bitonico eseguita su di un
ipercubo, dove j individua il ”passo” e l’indice i individua l”’iterazione”,
24
2.3 Mergesort Bitonico
25
come indicato anche nella figura 2.8. Useremo inoltre per comodit`a una
numerazione per l’indice i compresa fra 0 e k − 1 anzich`e fra 1 e k.
procedure BITONIC−MERGESORT−IPERCUBO (a0 , a1 , ..., an−1 );
begin
for i := 0 to k − 1 do
for j := i downto 0 do begin
d := 2j
for all h where 0 ≤ h ≤ n − 1 do in parallel begin
if h mod 2d < d then begin
th ← ah+d ;
if h mod 2i+2 < 2i+2 then begin
bh := max{ah , th };
ah := min{ah , th };
end else begin
bh := min{ah , th };
ah := max{ah , th };
end
end;
if h mod 2d ≥ d then
ah ← bh−d
end
end
end;
Possiamo vere come il costo del ”for all” della procedura resta costante, nella
variabile temporanea th viene copiato il dato del suo vicino a distanza d. Gli
elementi che vado a confrontare differiscono nel loro indice sempre per un solo bit. L”’if” finale fa lavorare i processori che non hanno lavorato, facendo
si che vadano a copiarsi il valore che devono memorizzare.
Vediamo di seguito nella figura 2.9 l’esecuzione dell’algoritmo su di un ipercubo di dimensione k = 3 per ordinare la sequenza di n = 8 elementi
5,6,3,13,7,10,9,2.
2.4 Moltiplicazione di matrici
Figura 2.9: Esecuzione ”Mergesort Bitonico” su ipercubo con n = 2k con
k = 3 elementi
2.4
Moltiplicazione di matrici
Riconsideriamo ora il problema della moltiplicazione di due matrici A =
[aij ] e B = [bij ] di dimensioni n×m, dove la matrice prodotto C = [cij ] = AB
P
`e tale che cij = nk=1 aik bkj , per 1 ≤ i, j ≤ n.
2.4.1
Mesh
Consideriamo una mesh ciclica di dimensioni n × n e si assuma che le due
matrici A e B siano memorizzate nell amesh in modo che il processore Pij
contenga inizialmente gli elementi aij e bij ed al termine della computazione
contenga cij . Abbiamo una prima fase preparatoria in cui gli elementi della
riga i-esima di A sono traslati ciclicamente a sinistra di i−1 posizioni, 1 ≤ i ≤
n, mentre gli elementi della colonna j-esima di B sono traslati ciclicamente
verso l’alto di j − 1 posizioni, 1 ≤ j ≤ n. Tali traslazioni hanno il compito di
fare in modo che nel processore Pij si incontri la coppia di elementi aik e bkj
26
2.4 Moltiplicazione di matrici
27
che servono per il calcolo dell’elemento risultato cij . Nella seconda fase, che
dura n iterazioni, sono eseguiti n2 prodotti per ciascuna iterazione, ed ogni
elemento di A e B `e coinvolto in un solo prodotto per iterazione.
procedure MOLTMATRICI−MESH(A, B, n);
begin
for p := 1 to n − 1 do
for all i, j where 1 ≤ i, j ≤ n do in parallel begin
if i > p then ai,j ← ai,j+1 ;
if j > p then bi,j ← bi+1,j
end;
for all i, j where 1 ≤ i, j ≤ n do in parallel ci,j := 0;
for q := 1 to n do
for all i, j where 1 ≤ i, j ≤ n do in parallel begin
ci,j := ai,j ∗ bi,j + ci,j ;
ai,j ← ai,j+1 ;
bi,j ← bi+1,j
end
end;
La procedura richiede O(n) tempo ed n2 processori per moltiplicare due matrici n × n, otteniamo quindi un lavoro pari a O(n3 ) che risulta essere lo
stesso dell’usuale algoritmo sequenziale.
Vediamo ora nella figura 2.10, l’esecuzione dell’algoritmo di moltiplicazione
di matrici su una mesh ciclica 3 x 3. Vediamo come nella seconda e nella
terza immagine viene fotografata la situazione della mesh all’uscita dal primo ”for” sequenziale, per i valori di p uguali a 1 e 2; nella terza e quarta
immagine invece vediamo la configurazione della matrice nella seconda fase,
all’uscita dal secondo ”for” sequenziale, per i valori di q uguali a 1 e 2 (3 non
`e mostrato).
2.4 Moltiplicazione di matrici
Figura 2.10: Moltiplicazione matrici su mesh ciclica 3 x 3
2.4.2
Ipercubo
Vediamo ora sempre la procedura di moltiplicazione su matrici eseguita
su di un ipercubo di n3 processori, e si assuma che n = 2h . Avremo quindi che
gli indici dei processori dell’ipercubo hanno valori compreso tra 0 e 23h − 1, e
la loro rappresentazione in binario consta di 3h bit, che possono essere visti
come formati da 3 blocchi di h bit, possiamo cos`ı vedere ogni blocco come la
rappresentazioni di 3 diversi indici del processore, che a questo punto possiamo individuare univocamente con una terna di indici (k, i, j).
28
2.4 Moltiplicazione di matrici
29
Ciascun processore Pm ha cinque variabili locali Am , Bm , Cm , Dm ed Em , assumiamo che le due matrici abbiano indici di riga e colonna compresi tra 0
e n − 1 anzich`e 1 ed n e che siano memorizzate nell’ipercubo in modo che il
processore Pm = P2h i+j = P0,i,j contenga inizialmente gli elementi aij e bij
nelle variabili Am e Bm , ed al termine della computazione contenga cij nella
variabile Cm , per 0 ≤ i, j ≤ n − 1.
Abbiamo 3 fasi di esecuzione; nella prima fase i dati vengono distribuiti in
tempo O(log n) a tutti i processori dell’ipercubo per mezzo di tre cicli ”for”
effettuati su tutti i bit di ciascuno dei tre ”blocchi”. Gli elementi aij e bij sono
distribuiti a tutti gli Am e Bm dei processori Pm = P22h k+2h j+j = Pk,i,j tali che
0 ≤ k ≤ n − 1. Allo stesso modo aik `e distribuito a tutti gli Am dei processori
Pm = P22h k+2h i+j = Pk,i,j tali che 0 ≤ j ≤ n − 1, mentre bkj `e distribuito a
tutti i Bm dei Pm = P22h k+2h i+j = Pk,i,j tali che 0 ≤ i ≤ n − 1. In questo modo ciascuno degli n3 processori contiene una una coppia distinta di elementi
della matrici A e B da moltiplicare e per l’esattezza Pm = P22h k+2h i+j = Pk,i,j
contiene aik e bkj . Nella seconda fase poi, sono effettuati in tempo O(1) tutti i prodotti. Infine nella terza fase sono sommati i prodotti sui processori
Pk,i,j tali che 0 ≤ k ≤ n − 1, ottenendo i risultati cij in tempo O(log n) nei
processori P0,i,j .
Nella procedura seguente useremo due funzioni ausiliarie, BIT(m, p), che
restituisce il (p + 1)-esimo bit meno significativo della rappresentazione binaria di m, per p ≥ 0, e la funzione COMPLEMENTA(m, p), che restituisce
l’intero ottenuto complementando il (p + 1)-esimo bit meno significativo della rappresentazione binaria di m. Sia m = 5, che in binario `e 101, allora
BIT(5,0)=1, BIT(5,1)=0 e BIT(5,3)=0, invece COMPLEMENTA(5,0)=4,
COMPLEMENTA(5,1)=7.
procedure MOLTMATRICI−IPERCUBO(A, B, n);
begin
for p := 3h − 1 downto 2h do
for all m where BIT(m, p) = 1 do in parallel
begin
2.4 Moltiplicazione di matrici
30
Dm :=COMPLEMENTA(m, p);
Am ← ADm ;
Bm ← BDm
end;
for p := h − 1 downto 0 do
for all m where BIT(m, p) 6= BIT(m, 2h + p) do in parallel
begin
Dm :=COMPLEMENTA(m, p);
Am ← ADm
end;
for p := 2h − 1 downto h do
for all m where BIT(m, p) 6= BIT(m, h + p) do in parallel
begin
Dm :=COMPLEMENTA(m, p);
Bm ← BDm
end;
for all m where 0 ≤ m ≤ 23h − 1 do in parallel
Cm := Am ∗ Bm ;
for p := 2h to 3h − 1 do
for all m where 0 ≤ m ≤ 23h − 1 do in parallel
begin
Em :=COMPLEMENTA(m, p);
Dm ← CEm ;
Cm := Cm + Dm ;
end;
end;
La procedura ha tempo pari a O(log n), utilizzando n3 processori, otteniamo
quindi un lavoro O(n3 log n).
Vediamo ora l’esecuzione della procedura su di un ipercubo di 23 = 8 processori per la moltiplciazione delle seguenti matrici 2 x 2.
#
"
#"
# "
9 10
1 2
−5 −6
=
13 14
3 4
7
8
2.5 Trasformata di Fourier
31
L’esecuzione per il calcolo `e illustrata nella figura 2.11.
Inserire qui figura moltiplicazione matrici ipercubo.
2.5
Trasformata di Fourier
Vediamo ora un algoritmo per il calcolo della trasformata discrate di
Fourier di un vettore reale a = (a0 , a1 , ..., an ), tale trasformata `e data dal
vettore complesso b = (b0 , b1 , ..., bn−1 ) tale che:
bh =
n−1
X
ak (ω h )k ,
per 0 ≤ h ≤ n − 1
k=0
dove ω `e la radice primitiva n-esima dell’unit`a. Consideriamo di prendere
n potenza di 2 e vediamo l’algoritmo sequenziale ”divite & impera”, dove il
problema `e stato diviso in due sottoproblemi, come mostrato nella figura 2.12,
che includono rispettivamente gli elementi di posto pari e di posto dispari:
X
a (x) =
X
n/2−1
n/2−1
P
k
a2k x ,
d
a (x) =
a2k+1 xk ,
k=0
k=0
cos`ı che
a(x) = aP (x) + aD (x)
Vediamo di seguito lo pseudocodice per l’algoritmo FFT in sequenziale:
Figura 2.11: Partizionamento dei dati per FFT
2.5 Trasformata di Fourier
32
procedure FFT(a:polinomio−reale; n:integer; var b:polinomio−complesso);
var aP , aD :polinomio−reale; bP , bD :polinomio−complesso;
begin
if n = 1 then b0 := a0
else begin
dividi il vettore a aP = (a0 , a2 , ..., an−2 ) e aD = (a1 , a3 , ..., an−1 );
FFT(aP , n div 2, bP ); FFT(aD , n div 2, bD );
ricava b ricombinando bP e bD
end
end;
Osserviamo inoltre la ricombinazione dei risultati per l’algoritmo sequenziale,
come illustrato nella figura 2.13 di seguito:
Figura 2.12: Ricombinazione per il calcolo di b1 con FFT
Bibliografia
[1] Alan Bertossi ”Algoritmi e Strutture Dati ”, UTET Libreria.
33
© Copyright 2024 ExpyDoc
