Uno degli aspetti che consideriamo fondamentali in questo tipo di applicazio- ni `e la tolleranza a guasti e disconnessioni, che in un ambiente di esecuzione
normale sono da considerarsi eccezioni (ed essere trattate come tali), mentre in ambienti pervasivi diventano situazioni comuni. Il nostro proposito `e di utilizzare il lavoro svolto in [20]; questo ci permette di inserire tecniche effi- cienti di tolleranza a guasti, attraverso l’uso di meccanismi di checkpointing e rollback-recovery, in applicazioni composte da grafi di forme di parallelismo note: esattamente la struttura di applicazione ASSISTANT.
Per quanto riguarda i manager, invece, questi richiedono un trattamento particolare, in quanto esterni alla struttura parallela dell’applicazione; a dif- ferenza delle altre parti di un modulo, questi devono essere sempre presenti durante l’intera computazione, anche in caso di fallimenti. Proponiamo per- ci`o tecniche di replicazione, probabilmente di tipo Active, dove ogni copia esegue esattamente le stesse operazioni.
Le tecniche di tolleranza ai guasti tramite checkpointing si possono anche applicare per realizzare in modo efficiente le modalit`a di riconfigurazione di cui abbiamo parlato nella sezione sull’adattivit`a. Infatti il primo requisito per le tecniche di checkpointing su applicazioni parallele `e quello di trovare dei punti durante l’esecuzione in cui lo stato dell’intera applicazione (vista come insieme di processi) sia “consistente”.
Questo requisito `e fondamentale anche per la modifica del comportamento dell’applicazione. I reconfiguration point di ASSIST, utilizzati per modificare il grado di parallelismo dei moduli paralleli, sono esattamente punti in cui lo stato dell’intero modulo `e consistente. Il checkpoint stesso pu`o essere utiliz- zato anche durante una riconfigurazione, per trasferire sui processi appena avviati la parte di stato interno di cui hanno bisogno.
L’utilizzo di tecniche di checkpointing si rivela quindi una ottima solu- zione per risolvere contemporaneamente i problemi di adattivit`a e di fault tolerance.
5.7
Conclusioni
In questo capitolo abbiamo proposto una prima introduzione alle caratteristi- che di ASSISTANT. Abbiamo preso spunto dai lavori presentati nel capitolo 3 per estendere il modello di ASSIST, in modo da poter realizzare anche appli- cazioni adattive e context-aware, capaci quindi di essere eseguite in ambienti pervasivi ed in pervasive grid.
Abbiamo discusso una la modellazione a tre strati, che rappresenta tre differenti aspetti di una applicazione ASSISTANT e ci guida nella sua defi- nizione.
Abbiamo mostrato la tecnica da noi proposta per gestire in modo coe- rente sia l’adattivit`a che la context awareness, tramite la definizione di pi`u versioni di una stessa entit`a (nel nostro caso il modulo) dell’applicazione, con un approccio che riprende le idee dei modelli come Odyssey e Aura, per applicarle ad una strutturazione a moduli derivata da ASSIST.
A questo punto pensiamo di aver posto le basi per presentare in modo definitivo la sintassi di ASSISTANT, applicata ad un esempio pi`u complesso di applicazione adattiva e context aware che vedremo nel prossimo capitolo.
Un esempio completo
Presentiamo ora un esempio completo di applicazione ASSISTANT, studiato nell’ambito del progetto In.Sy.Eme come test-bed per una applicazione di gestione delle emergenze.
Questo esempio `e stato trattato, con diverse sfaccettature, in [21, 22]. Lo riprendiamo, per dare al lettore un’idea pi`u chiara della reale utilit`a delle riconfigurazioni considerate in ASSISTANT, e dello studio richiesto per lo sviluppo di una applicazione pervasiva per tale modello.
In una applicazione di gestione di inondazioni fluviali la parte di previ- sione (eseguita costantemente e non solo in situazioni critiche) utilizza dei modelli di idrodinamica per prevedere il livello dei fiumi e, nel caso di strari- pamenti, le probabili zone interessate dagli allagamenti. Questi modelli fan- no largo uso di sistemi lineari per risolvere equazioni differenziali parziali[72]. Le matrici dei sistemi da risolvere normalmente non sono generali, ma piut- tosto sparse e con caratteristiche peculiari che permettono una risoluzione efficiente: ci troviamo spesso a lavorare con sistemi lineari tridiagonali.
Esistono diversi algoritmi per la risoluzione di sistemi lineari tridiagonali, ognuno con caratteristiche differenti. In questa ottica, uno studio dei va- ri algoritmi porterebbe gi`a alla definizione di pi`u operation, con algoritmi diversi, da scegliere in base all’ambiente di esecuzione. Nel nostro caso ci siamo focalizzati su un unico algoritmo di tipo diretto. Tra questi, alcuni esempi importanti sono la twisted factorization e la cyclic reduction[40]. Ab- biamo scelto il secondo perch´e facilmente generalizzabile a sistemi “a banda” o “tridiagonali a blocchi”.
Successivamente nel capitolo presenteremo l’algoritmo base nella sezio- ne 6.1, ed una versione specifica studiata per una migliore parallelizzazione (sezione 6.2). Di queste forniremo, come al solito, una implementazione in ASSIST; passiamo poi a descrivere l’ambiente e le infrastrutture su cui l’ap- plicazione verr`a eseguita nella sezione 6.3. Continuiamo presentando in modo
completo l’esempio di applicazione studiato dal gruppo (sezione 6.4), le con- siderazioni su quale versioni dei moduli eseguire sulle varie piattaforme (6.5) e, per finire, le riconfigurazioni proposte per il modulo principale nella sezione 6.6.
6.1
Cyclic Reduction
Una matrice tridiagonale `e della forma 6.1, che permette una rappresentazio- ne compatta dell’intero sistema utilizzando quattro elementi per ogni riga, come riportato in 6.2, con a1 = cn = 0 e i ki che rappresentano il vettore dei
termini noti. A = b1 c1 0 · · · 0 a2 b2 c2 . .. ... 0 . .. ... ... ... ... .. . . .. ... ... ... ... ... .. . . .. ... ... ... 0 .. . . .. ... ... cn−1 0 · · · 0 an bn (6.1) S = a1 b1 c1 k1 .. . ... ... ... an bn cn kn (6.2)
L’algoritmo di cyclic reduction originale, ideato da Golub e Hockney, nasce per la risoluzione dell’equazione di Poisson tramite il calcolo di un insieme di sistemi tridiagonali [54]. L’algoritmo prevede di avere un numero di righe nel- la forma 2q− 1, ma studi successivi[71] ne hanno dimostrato l’applicabilit`a
anche per matrici pi`u generali. Nel nostro caso, per semplicit`a, riportia- mo l’algoritmo originale. Per una trattazione pi`u approfondita della cyclic reduction consigliamo [53].
L’idea base dell’algoritmo `e di applicare una trasformazione per eliminare le incognite con indice dispari. In questo modo ci troviamo con un sistema di dimensione dimezzata. Applicando la trasformazione iterativamente, si riesce ad ottenere un sistema con una singola incognita dalla soluzione ovvia. A questo punto, mediante una procedura di riempimento, si ottengono, sempre in modo iterativo, i valori per tutte le altre incognite.
L’algoritmo `e quindi naturalmente suddiviso in due parti: trasformazione e risoluzione.
Fase di Trasformazione
Questa fase si suddivide in q − 1 passi con q = log2(N + 1), e ad ogni passo trasforma un numero sempre minore di righe. Le righe interessate dalla trasformazione al passo l sono quelle con indice divisibile da 2l, ovvero le i tali che i mod 2l = 0.
Ad ogni passo la trasformazione necessita dei dati del precedente, e mo- difica i valori come riportato in 6.3.
ali = αial−1i−2l−1 c l i = γicl−1i+2l−1 bli = bl−1i + αicl−1i−2l−1+ γi kli = k l−1 i + αiki−2l−1l−1+ γikl−1i+2l−1 dove αi = − al−1i bl−1i−2l−1 γi = − cl−1i bl−1i+2l−1 (6.3) Fase di Risoluzione
Questa fase, che produce i valori del vettore X delle soluzioni, `e suddivisa in q passi (uno in pi`u della precedente), ed utilizza i dati prodotti da tutti gli step di trasformazione per calcolare la soluzione.
Ad ogni passo l = q, q − 1, ..., 1 vengono calcolate le soluzioni per le righe i tali che i mod 2l−1 = 0, se non gi`a calcolate precedentemente, secondo la formula in 6.4. xi = kil−1− al−1 i xi−2l−1− cl−1xi+2l−1 bl−1i xi = 0, per i < 0 e i > N (6.4) Parallelizzazione dell’algoritmo
I passi dell’algoritmo sono illustrati graficamente in figura 6.1.
La struttura di questo algoritmo suggerisce una parallelizzazione di tipo data-parallel con stencil, ma in un’ottica parallela i processori rimarrebbero inutilizzati per gran parte del tempo durante entrambe le fasi (ad ogni passo si lavora con la met`a delle righe del passo precedente). Questa versione, infatti, `e stata pensata per minimizzare il numero di operazioni nell’ottica di una esecuzione sequenziale. Dal punto di vista prestazionale questo algoritmo si comporta quindi molto meglio con parallelizzazioni di tipo farm.
Per questo motivo presentiamo, nel listato 6.1, la sola versione farm. Durante i test abbiamo anche sviluppato una versione data-parallel, che si
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 ; do 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 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.1: Modulo Cyclic Reduction parallelizzata tramite farm
p21 p 4 1 p 6 1 p1 p2 p3 p4 p5 p6 p7 p42 x1 x2 x3 x4 x5 x6 x2 x6 x7 x4 x1 x3 x5 x7 x0 x8
Figura 6.1: Rappresentazione grafica dei passi dell’algoritmo Cyclic Reduction e delle dipendenze tra i dati (stencil).
`e per`o rivelata molto meno performante dei quella farm; evitiamo perci`o di riportarla.