Il calcolo su un numero sempre pi`u basso di righe della Cyclic Reduction rende l’algoritmo poco adatto ad una parallelizzazione di tipo data-parallel; per questo motivo `e stata studiata una variante, chiamata Parallel Cyclic Reduction, pi`u adatta a questa forma di parallelismo, che cerca di mitigare il problema.
In questa versione si cerca di superare i problemi della Cyclic Reduction vista prima aumentando il numero di operazioni nella fase di trasformazione, per sfruttare al meglio i processori; ovviamente il lavoro aggiuntivo non `e completamente perso, e permette di ridurre significativamente la fase di riso- luzione, eseguita in un solo passo e senza dipendenze funzionali tra le righe. Vediamo meglio l’algoritmo:
Fase di Trasformazione
In questo caso si applicano ancora le formule in 6.3, ma per tutte le righe, ad ogni passo, e questa volta per q passi. L’attivazione su tutte le righe porta la dipendenza funzionale su i ± 2l−1 alla generazione di indici di riga
negativi o non esistenti. Per tutti questi casi utilizziamo una riga fittizia, come riportato in 6.5
ai bi ci ki
= 0 1 0 0 i < 0 e i > N (6.5) In questo modo tutti i nodi utilizzati eseguono la stessa quantit`a di lavoro, mantenendo quindi il carico tra essi bilanciato. Purtroppo aumenta notevol- mente anche la quantit`a di dipendenze logiche e quindi di dati trasferiti, in quanto il calcolo su ogni riga ne richiede due del passo precedente.
Fase di Risoluzione
La caratteristica importante di questa versione di cyclic reduction `e che ci permette di calcolare le soluzioni senza una procedura iterativa di riempi- mento.
Infatti l’equazione 6.4 rimane valida per calcolare le soluzioni, ma l’appli- cazione di un ulteriore passo di trasformazione ci ha portato ad avere tutte le dipendenze della forma xi−2l−1 ad una riga i < 0 e quelle xi+2l−1 ad una
riga i > N . Perci`o i due termini additivi della 6.4 si annullano e la soluzione pu`o essere calcolata semplicemente con la 6.6.
xi =
kiq−1
bq−1i (6.6)
Questo ci porta ad una fase di risoluzione senza dipendenze logiche ed eseguibile, in parallelo, su tutte le righe in un solo passo.
Parallelizzazione dell’algoritmo
I passi di questa versione dell’algoritmo sono illustrati graficamente in figura 6.2. Questa versione presenta molte caratteristiche interessanti nell’ottica di una versione data-parallel, ma anche per quella sequenziale.
Innanzitutto questa versione sfrutta in modo migliore i processori, in quanto tutti lavorano ad ogni passo, ed in questo modo riusciamo a diminui- re i passi totali. Purtroppo, come possiamo vedere anche nella figura 6.2, la quantit`a di dati scambiati aumenta considerevolmente; in un ambiente pa- rallelo a scambio di messaggi questa caratteristica potrebbe limitare in modo consistente le prestazioni dell’algoritmo, in quanto non possiamo sovrapporre il calcolo alle comunicazioni. In una architettura a memoria condivisa, inve- ce, possiamo sperare in un comportamento migliore, in quanto non abbiamo bisogno di copiare i dati delle dipendenze logiche ma possiamo accedervi direttamente.
La Parallel Cyclic Reduction presenta anche caratteristiche interessanti per quanto riguarda l’occupazione di memoria. Infatti, la versione originale richiede, nella fase di risoluzione, i valori di tutti gli step di trasformazio- ne; su matrici grandi la quantit`a di memoria richiesta potrebbe non essere non trascurabile, soprattutto per esecuzioni interamente sequenziali, in cui allochiamo tutto nella memoria del singolo nodo. In quest’ottica questo se- condo algoritmo pu`o essere ottimizzato, durante la fase di trasformazione, per mantenere solo i dati a partire dal penultimo ultimo step non ancora completamente terminato. Nella versione sequenziale questo si traduce nel dover mantenere solo due copie della matrice: una per lo step precedente, una per quello attuale.
Per questo motivo questo algoritmo, pur richiedendo pi`u tempo a cau- sa dei maggiori calcoli eseguiti, pu`o essere utilizzato anche per versioni se- quenziali pure o in farm, per i dispositivi con poca memoria come PDA e SmartPhone.
Riportiamo perci`o due differenti versioni di questo algoritmo, paralleliz- zato tramite farm (listato 6.2) e tramite data-parallel (listato 6.3).
typedef s t r u c t { double a , b , c , k ; } row ;
parmod T r i d i a g o n a l S o l v e r ( input stream row System [N] output stream double S o l u t i o n [N ] ) {
topology none Pv ; input section { guard1 : on , , System { d i s t r i b u t i o n System on demand to Pv ; } } while ( true ) v i r t u a l p r o c e s s o r s { e l a b o r a z i o n e ( in guard1 out S o l u t i o n ) { VP { F P a r a C y c l i c R e d u c t i o n ( in A out S o l u t i o n ) ; } } } output section { c o l l e c t s S o l u t i o n from ANY Pv ; } }
Listato 6.2: Modulo per Parallel Cyclic Reduction parallelizzata tramite farm. L’unica differenza rispetto alla 6.1 `e la proc invocata
p11 p 2 1 p 3 1 p 4 1 p 5 1 p 6 1 p 7 1 p1 p2 p3 p4 p5 p6 p7 p0 p8 p12 p 2 2 p 3 2 p 4 2 p 5 2 p 6 2 p 7 2 p13 p 2 3 p 3 3 p 4 3 p 5 3 p 6 3 p 7 3 x1 x1 x2 x3 x4 x5 x6 x2 x3 x4 x5 x6 x7 x7
Figura 6.2: Rappresentazione grafica dei passi dell’algoritmo Parallel Cyclic Reduction e delle dipendenze tra i dati (stencil).
typedef s t r u c t { double a , b , c , k ; } row ;
parmod T r i d i a g o n a l S o l v e r ( input stream row System [N] output stream double S o l u t i o n [N ] ) {
topology array [ i :N] Pv ; a t t r i b u t e row M[N ] [ LOG 2 N ] ; a t t r i b u t e row empty ;
stream long o u t m a t r i x ;
i n i t { empty . a =0; empty . b=1; empty . c =0; emprty . k =0; } do input section { guard1 : on , , System { d i s t r i b u t i o n System [ ∗ i 0 ] s c a t t e r to M[ i 0 ] [ 0 ] ; } } while ( true ) v i r t u a l p r o c e s s o r s { e l a b o r a z i o n e ( in guard1 out o u t m a t r i x ) { VP i = 1 . .N { f o r ( l =0; l <LOG 2 N−1; l ++){ // T r a n s f o r m a t i o n l e f t = i − pow ( 2 , l −1) ; r i g h t = i + pow ( 2 , l −1) ; i f ( l e f t < 0 && r i g h t < N)
FTrasform ( in M[ i ] [ l − 1 ] , empty ,M[ r i g h t ] [ l −1] out M[ i ] [ l ] ) ;
e l s e i f ( s x >= 0 && dx => N)
FTrasform ( in Mat [ i ] [ l − 1 ] , Mat [ l e f t ] [ l − 1 ] , empty out Mat [ i ] [ l ] ) ;
e l s e i f ( l e f t < 0 && dx => N)
FTrasform ( in Mat [ i ] [ l − 1 ] , empty , empty out Mat [ i ] [ l ] ) ; e l s e
FTrasform ( in Mat [ i ] [ l − 1 ] , Mat [ l e f t ] [ l − 1 ] , Mat [ r i g h t ] [ l −1] out Mat [ i ] [ l ] ) ;
}
// S o l v i n g
F S o l v e ( in Mat [ i ] [ LOG 2 N−1] out o u t m a t r i x ) ; }
}
output section {
c o l l e c t s o u t m a t r i x from ALL Pv [ i ] { double elem ; double r i s [N ] ;
AST FOR EACH( elem ) { r i s [ i ]= elem ; } a s s i s t o u t ( r e s u l t , r i s ) ;
}<>; } }
Listato 6.3: Modulo per Parallel Cyclic Reduction parallelizzata tramite data-parallel con stencil
La versione farm `e identica a quella vista precedentemente, se non per la proc invocata. Il data-parallel invece merita qualche cenno ulteriore. Un lettore attento avr`a notato che lo stencil della computazione `e di tipo va- riabile: `e definito staticamente, ma cambia ad ogni passo. Purtroppo, come possiamo vedere nel codice, la presenza di casi speciali (quelli che utilizza- no la riga vuota vista in 6.5) e di uno stencil calcolato in modo complesso (i ± 2l−1) richiedono un lavoro notevole da parte del compilatore per rico-
noscere lo stencil come variabile e non dinamico. Questo `e importante, in quanto nel primo caso il compilatore potrebbe conoscere l’entit`a delle comu- nicazioni ad ogni passo, ottenere un modello dei costi e ragionare su differenti ottimizzazioni che, nel secondo caso, non potrebbe fare.