Nella figura 5.12 sono riportati tutti i tempi di esecuzione, espressi in numero di cicli di clock, di tutte le architetture realizzate su dispositivi FPGA. Tali soluzioni sono state testate impiegando il dataset composto da 20 attributi relativi a 400 pazienti differenti (per maggiori dettagli sull’im-
piego di tale dataset fare riferimento alla sottosezione 5.1.2). 0 1.000.000 2.000.000 3.000.000 4.000.000 5.000.000 6.000.000 7.000.000 1,00 2,00 3,00 4,00 5,00 6,00 Numer o c ic li d i c lo ck Numero mdr_block
Soluzione con PPC e bus PLB su XC5VFX70T (di partenza) Soluzione con PPC e bus PLB su XC5VFX70T Soluzione con MB e bus PLB su XC5VFX70T Soluzione con MB e bus PLB su XC5VLX110T Soluzione con MB e bus FSL su XC5VLX110T Soluzione con 2 MB e bus FSL su XC5VLX110T Soluzione con 3 MB e bus FSL su XC5VLX110T
Figura 5.12: Tempi di esecuzione di tutte le soluzioni analizzate su dispositivo XC5VFX70T e XC5VLX110T
L’architettura di partenza (soluzione descritta nella sottosezione 5.1 e iden- tificata nella figura 5.12 da un rombo di color giallo), sviluppate sul disposi- tivo di Xilinx FPGA XC5VFX70T, è costituita da un singolo acceleratore hardware connesso tramite PLB al processore PPC. L’algoritmo di divisio- ne impiegato per l’implementazione del componente divisore, all’interno dell’acceleratore hardware, è HighRadix.
Modificando l’algoritmo per la realizzazione del divisore da HighRadix a Radix-2, le prestazioni del sistema non sono variate (Lo speed-up è pa- ri a 1,00x rispetto alla soluzione di partenza). Inserendo, in questa nuova architettura, ulteriori moduli mdr_block, sviluppate sul dispositivo FPGA XC5VFX70T, costituita da un singolo acceleratore connesso tramite PLB al processore PPC (soluzioni descritte nella sottosezione 5.2.1 e identificate nella
CAPITOLO 5. RISULTATI SPERIMENTALI 108
figura 5.12 da quadrati di color rosso), si nota come variano le prestazioni del sistema in relazione al numero di acceleratori hardware connessi. Lo speed-up che si ottiene inserendo due moduli è di 1,60x, con tre moduli è pari a 1,85x mentre con quattro acceleratore le prestazioni diminuiscono e lo speed-up finale risulta essere di 1,76x.
Analizzando le varie soluzioni si può notare come tutte le architetture, sviluppate sul dispositivo FPGA XC5VFX70T, con un singolo processore MB, connesso a 1-3 acceleratori hardware tramite bus PLB (soluzioni descrit- te nella sottosezione 5.2.2 e identificate nella figura 5.12 da triangoli di color verde), ottengano tempi di esecuzione superiori rispetto alla soluzione di partenza. In particolare la soluzione con un acceleratore connesso al processore MB, ottiene uno speed-up di 0,49x rispetto alla soluzione di partenza, mentre le architetture con due moduli ottengono entrambe uno speed-up di 0,77x.
Anche le soluzioni, sviluppate sul dispositivo FPGA XC5VLX110T, com- poste da un solo processore MB e connesso a 1-6 moduli mdr_block, tramite canale PLB (soluzioni descritte nella sottosezione 5.3.1 e identificate nella figura 5.12 da cerchi di color giallo), hanno risultati peggiori rispetto alla soluzione di partenza. Lo speed-up con un singolo modulo, connesso al processore MB, rispetto alla soluzione di partenza, è di 0,49x, mentre con due acce- leratori le prestazioni aumentano a 0,77x. Aggiungendo un ulteriore mo- dulo ai due già presenti, si aumentano leggermente le prestazioni a 0,78x mentre con quattro moduli lo speed-up diminuisce e risulta essere pari a 0,74x. Con cinque acceleratori la prestazione dell’architettura è di 0,70x in- fine con sei è pari a 0,64x. Si nota che il comportamento di questa architet- tura su FPGA XC5VLX110T, per le soluzioni con un numero di acceleratori hardware inferiore a quattro, risulta essere lo stesso che si ottiene con la medesima architettura implementata su FPGA XC5VFX70T.
Sostituendo il canale di comunicazione e impiegando il bus FSL al- l’interno dell’ architettura, sviluppate sul dispositivo FPGA XC5VLX110T
composta da un unico processore MB e connesso a 1-6 acceleratori hard- ware (soluzioni descritte nella sottosezione 5.3.2 e identificate nella figura 5.12 da X di color blu), si ottengono risultati differenti rispetto all’utilizzo del bus PLB. Con soluzioni caratterizzate da un numero di moduli mdr_block in- feriore a quattro, si ottengono prestazioni superiori rispetto all’architettura con PLB. Aumentando i moduli hardware, il PLB risulta essere più efficien- te rispetto al bus FSL. Sostituendo il bus di comunicazione le prestazioni in relazione alla soluzione di partenza sono: con un solo acceleratore hard- ware lo speed-up del sistema è di 0,61x, con due moduli è di 0,97x, con tre lo speed-up raggiunge il valore di 1,19x ottenendo il miglior risultato delle architetture analizzate con singolo processore. Aumentando il nume- ro di moduli hardware le prestazioni diminuiscono: con quattro moduli lo speed-up è pari a 0,65x, con cinque moduli è di 0,64x ed infine con sei le prestazioni sono del 0,63x.
Aggiungendo un ulteriore processore MB a quello già presente nell’ar- chitettura, e inserendo un numero di acceleratori hardware che varia da 2 a 6 (soluzioni descritte nella sottosezione 5.3.3 e identificate nella figura 5.12 da cerchi di color verde), le prestazioni aumentano rispetto alla soluzione di partenza. Lo speed-up che si ottiene, inserendo un modulo mdr_block per ogni processore, è pari a 1,22x, nella soluzione composta da tre accelerato- ri (due connessi ad un primo processore mentre un terzo modulo connesso ad un secondo processore) lo speed-up è di 1,72x, mentre inserendo quattro moduli (due acceleratori collegati ad ogni processore) le prestazioni sono di 1,93x. Per la soluzione composta da cinque moduli (tre connessi ad un primo processore mentre due modulo connessi ad un secondo processore) lo speed-up aumenta arrivando a 2,04x rispetto alla soluzione di partenza, infine per l’architettura composta da sei acceleratori hardware (tre accele- ratori collegati ad ogni processore) si ottiene il migliore speed-up pari a 2,36x.
CAPITOLO 5. RISULTATI SPERIMENTALI 110
L’architettura composta da tre processori MB ogniuno connesso a un acceleratore hardware attraverso il bus punto a punto FSL (soluzione iden- tificata nella figura 5.12 da un cerchio di color blu), ha ottenuto uno speed-up 1,79x, rispetto alla soluzione di partenza.
Conclusioni
Questo lavoro di tesi esamina l’algoritmo Multifactor Dimensionality
Reduction (MDR), impiegato nell’ambito della bioinformatica per preveni-
re l’insorgere delle malattie complesse o multifattoriali. L’obiettivo propo- sto è la diminuzione, attraverso tecnologie di co-design, dei lunghi tempi di esecuzione dell’algoritmo, quando devono essere prese in considerazione considerevoli quantità di dati. L’onerosa computazione limita gravemen- te l’utilizzo di MDR in ambito medico/genetico, risulta quindi necessario identificare soluzioni in grado di velocizzarne l’esecuzione.
La prima parte del lavoro introduce la problematica relativa all’iden- tificazione della componente genetica delle malattie complesse e l’impor- tanza di strumenti capaci di determinare il grado di suscettibilità al can- cro, all’infarto o al morbo di Alzheimer (malattie classificate come com- plesse). Aumentare le prestazioni dell’algoritmo MDR equivale a render- lo uno strumento: efficace, nell’identificazione delle interazioni non linea- ri tra gene-gene e gene-ambiente che influenzano la suscettibilità alle ma- lattie complesse; efficiente, rendendolo veloce nell’eseguire analisi di gran- di quantità di dati, contribuendo così all’identificazione delle componenti genetiche delle malattie multifattoriali.
La seconda parte del lavoro si concentra sulla ricerca, nell’ambito tec-
CAPITOLO 6. CONCLUSIONI 112
nologico, di dispositivi e di tecniche in grado di accelerare applicazioni di uno, due o addirittura tre ordini di grandezza. I dispositivi impiegati sono le Field Programmable Gate Array (FPGA) (la cui funzionalità è program- mabile via software), consentono di realizzare prototipi in modo rapido e di emulare i dispositivi realizzati come insieme di logica generica, risultando un utile strumento per effettuare Design Of Experiments (DOE).
La terza parte del lavoro analizza l’algoritmo MDR, a partire da una sua prima implementazione software [42], con l’obiettivo di identificarne le ca- ratteristiche principali, in modo da determinare le funzioni più critiche e computazionalmente più onerose (raggruppate nel blocco principale), can- didabili a essere implementate in moduli hardware. Tenendo in considera- zione, sia l’individuazione dei blocchi principali, sia le dipendenze dati e la quantità di dati trasmessi con le restanti procedure, è stato possibile realiz- zare un modello capace di implementare il comportamento, dell’algoritmo MDR, in relazione al tipo di partizionamento hardware/software scelto e stimare i tempi di esecuzione dell’algoritmo [95]. Il risultato di tale simula- zione è l’indivuduazione delle funzioni da implementare in hardware, che in questo caso risultano essere quelle facenti parte del blocco principale e quelle che condividono con il blocco principale le principali dipendenze di dato.
Successivamente all’analisi di prestazione, si passa ad analizzare come la scelta del partizionamento influenzi i costi e se tale scelta soddisfi o meno i vincoli di sistema. Per un’analisi accurata, sono state considerate diverse FPGA prodotte da Xilinx; per la classe di appartenenza (Virtex-5 VFX e VLX), per le dimensione in termini di slices, per la presenza o meno di processori integrati e per i costi. In relazione alle analisi di prestazione e di costi svolte in questo progetto, è stata realizzata ed implementata una prima versione di acceleratore hardware, mdr_block, su dispositivo FPGA XC5VFX70T [87].
A partire dall’analisi e dalla valutazione di questo primo sistema, è stato possibile realizzare un insieme di architetture, in grado di implementare l’algoritmo MDR, garantendo prestazioni e costi differenti, per popolare il
design space con varie soluzini.
Nella prima soluzione, viene sostituito l’algoritmo HighRadix a favore di Radix-2, per l’implementazione del divisore all’interno dell’accelerato- re hardware. In tal modo è possibile inserire, all’interno del dispositivo di partenza, un numero superiore a due di moduli mdr_block, cosa che con HighRadix non è fattibile, poiché la sua implementazione richiede risorse superiori a quelle fornite dalla FPGA XC5VFX70T.
Sostituendo l’algoritmo per l’implementazione del divisore, è stato pos- sibile inserire, all’interno dell’architettura di partenza composta da un uni- co acceleratore hardware collegato al processore PowerPC (PPC) attraver- so il bus Processor Local Bus (PLB), fino a quattro acceleratori, in modo da verificare come all’aumentare dei moduli hardware, aumentino le presta- zioni del sistema. L’architettura con tre acceleratori ha ottenuto le migliori prestazioni con uno speed-up di 1,85x rispetto alla soluzione di partenza.
Nella seconda soluzione, viene sostituito il processore PPC a favore del MicroBlaze (MB), in modo da poter creare architetture anche sui dispositivi che non integrano il processore hardcore. Confrontando i risultati di que- sta architettura, implementata sulla FPGA XC5VFX70T, con la medesima architettura, implementata sulla FPGA XC5VLX110T, si sono ottenuti gli stessi risultati, confermando che cambiando classe di FPGA da VFX a VLX, il comportamento di uno stesso sistema non varia.
Nella terza soluzione, viene sostituito il bus di comunicazione PLB, a favore del bus Fast Simplex Link (FSL). L’andamento delle prestazioni del sistema in funzione al numero di acceleratori, varia rispetto a quello in- dividuato con l’impiego del bus PLB. La soluzione con tre moduli risulta essere quella con il più alto speed-up, rispetto alla soluzione di partenza,
CAPITOLO 6. CONCLUSIONI 114
pari a 1,19x.
Nella quarta soluzione, vengono inseriti due processori MB, ognuno collegato a tre acceleratori hardware, ottenendo una prestazione pari a 2,36x, rispetto alla soluzione di partenza.
Come ultima soluzione, viene inserito un terzo processore MB ai due già presenti, collegando a ognuno un solo acceleratore hardware. Il risulta- to di tale architettura è uno speed-up di 1,79x.
I risultati di tali sistemi, sviluppati a partire dall’architettura di parten- za, sono stati confrontati con i risultati ottenuti impiegando altri sistemi creati con diverse tecnologie [87] (vedi figura 6.1). Una prima soluzione, modifica il codice, che descrive l’algoritmo MDR, per renderlo un’applica- zione multi-core, ottenendo uno speed-up di 14,7x, usando un processore a 32 core, rispetto alla soluzione completamente sequenziale. Una secon- da soluzione, utilizza i dispositivi General-Purpose computing on Gra-
phics Processing Units (GPGPU), ottenendo un aumento di velocità di
71,2x, mentre l’implementazione di partenza su FPGA, valutata in questa tesi per la realizzazione di migliori soluzioni, aumenta la velocità di 60,9x. Analizzando queste tre soluzioni, il sistema che impiega la GPGPU con- segue le migliori prestazioni, grazie all’enorme parallelismo dell’algoritmo MDR che permette di sfruttare appieno le potenzialità di questa tecnologia. Anche la soluzione multi-core, ottenuta con un ridotto sforzo, fornisce un buon speed-up. Il risultato con FPGA, relativo all’architettura di partenza, è al di sotto delle aspettative, motivo per cui si è deciso di esplorare nuove soluzioni per trovare architetture che ne aumentassero le prestazioni.
Analizzando, le migliori soluzioni implementate su Field Programma- ble Gate Array (FPGA), ottenute da questo lavoro, si può notare che, in- serendo tre acceleratori hardware all’interno dell’architettura di partenza, previa modifica dell’algoritmo divisore, si ottiene uno speed-up di circa 115x rispetto alla soluzione software. La soluzione che prevede tre modu-
0 20 40 60 80 100 120 140 160 1 2 3 4 5 6 7 14,7 71,2 60,9 61,96 114,77 73,82 146,27 111,08 Speed -up Soluzioni
dataset grande (1.000x1.600) dataset ridotto (20x400) Soluzioni 1. Multi-Core 2. GPGPU 3. FPGA (XC5VFX70T)
1 processore PPC gestisce 1 acceleratore hardware tramite PLB (soluzione di partenza)
4. FPGA (XC5VFX70T)
1 processore PPC gestisce 3 acceleratori hardware tramite bus PLB
5. FPGA (XC5VLX110T)
1 processore MB gestisce 3 acceleratore hardware tramite FSL
6. FPGA (XC5VLX110T)
2 processori MB gestiscono ognuno 3 acceleratori hardware tramite FSL
7. FPGA (XC5VLX110T)
3 processori MB gestiscono ognuno 1 acceleratore hardware tramite FSL
Figura 6.1: Speed-up relativo alle soluzioni sviluppate con diverse tecnologie (multi-core, GPGPU,
FPGA). Lo speed-up è confrontato con le prestazioni ottenute dalla soluzione sviluppata interamente
in software
li hardware connessi al MicroBlaze (MB) tramite Fast Simplex Link (FSL), ottiene uno speed-up di circa 74x; la soluzione composta da due processori softcore connessi ognuno a tre moduli hardware tramite FSL, ottiene pre- stazioni di circa 146x; la soluzione con tre processori ognuno collegato ad un acceleratore hardware tramite FSL, ottiene uno speed-up di circa 111x. Ogni architettura creata, garantisce un differente compromesso tra presta- zioni e costi, collocandosi all’interno dello spazio di soluzioni in posizioni differenti. Sarà cura del progettista valutare quale soluzione è la migliore in relazione ai vincoli di progetto.
6.1 Contributi innovativi
I principali contributi innovativi di questo lavoro sono:
1. l’individuazione delle caratteristiche principali e più ricorrenti che ca- ratterizzano l’algoritmo Multifactor Dimensionality Reduction (MDR),
CAPITOLO 6. CONCLUSIONI 116
la valutazione delle dipendenze dato e di funzione e la quantità di dati trasferiti tra le varie funzioni;
2. l’analisi e l’ottimizzazione di una prima versione di acceleratore crea- to ad-hoc su FPGA dell’algoritmo MDR;
3. la realizzazione di architetture con differenti configurazioni in modo da popolare il design space, con varie e possibili soluzioni; le archi- tetture sono state realizzate considerando diversi tipi di FPGA, pro- cessori, numero di processori, bus di collegamento, numero e tipo di acceleratori hardware dell’algoritmo;
4. l’esplorazione del design space per identificare quali sono le architet- ture migliori in relazione ai costi o alle prestazioni.