Accelerazione dell'algoritmo multifactor dimensionality reduction

Il rapido sviluppo di nuovi marcatori genetici e la possibilità di avere a disposizione metodiche di genotipizzazione rapide e poco costose, ci pone nella possibilità di affrontare la sfida della ricerca dei geni responsabili di malattie complesse. Uno degli strumenti di analisi, proposti per svelare le interazioni non lineari tra gene-gene e gene-ambiente, caratteristiche delle malattie complesse, è l'algorimo Multifactor Dimensionality Reduction(MDR) che elabora un modello, atto a facilitare la previsione dell'insorgere della malattia. Tuttavia, i lunghi tempi di elaborazione dell'algoritmo ne limitano l'applicazione in campo medico/genetico. L'obiettivo di questo lavoro è l'individuazione e la realizzazione di sistemi capaci di abbattere i tempi di computazione di MDR, al fine di renderlo uno strumento utile all'identificazione delle componenti genetiche delle malattie complesse. Attraverso la metodologia co-design, è possibile progettare una serie di sistemi, caratterizzati da componenti hardware e software, implementabili su Field Programmable Gate Array (FPGA), per conseguire soluzioni che implementano l'algoritmo MDR, con diverse caratteristiche prestazionali e di costi. L'analisi mira ad identificare i punti critici architetturali di ogni sistema, al fine di indirizzare l'esplorazione nello spazio delle soluzioni, nella direzione che permetta di trovare architetture sempre migliori. Attraverso questo percorso si vuole individuare il sistema ottimale, che garantisca il miglior compromesso tra prestazioni e costi. Questo lavoro analizza l'algoritmo MDR per individuarne le funzioni critiche, le dipendenze dei dati e le dipendenze funzionali. E' stato creato un modello ad-hoc in grado di simulare il tempo di esecuzione dell'algoritmo, in relazione al tipo di partizionamento hardware e software, allo speed-up tra il modulo hardware e la sua implementazione in software e la velocità di trasferimento dei dati tra diverse partizioni. Simulando il modello è possibile identificare quale sia la migliore partizione in relazione ai vincoli del sistema, con l'obiettivo di creare una prima versione di acceleratore hardware, che implementa le funzioni critiche dal software all'hardware, utilizzando il linguaggio VHDL. La prima architettura analizzata, è stata sviluppata impiegando come dispositivo una FPGA XC5VFX70T di Xilinx, ed è composta da un processore hardcore (PowerPC440), connesso ad un singolo acceleratore hardware collegato al bus Processor Local Bus (PLB). Questa architettura, che ha ottenuto uno speed-up di circa 60x, rispetto alla soluzione software, è il punto di partenza dell'esplorazione nello spazio di progettazione, per la ricerca di una soluzione con il migliore compromesso in termini di prestazioni e costi. L'esplorazione ha portato alla creazione e alla successiva valutazione di vari sistemi. La prima soluzione realizzata è caratterizzata dall'inserimento di ulteriori acceleratori hardware, all'interno dell'architettura di partenza, ottenendo uno speed-up massimo di circa 115x, rispetto alla soluzione software. Sostituendo il processore PowerPC con un softcore (MicroBlaze), è stato possibile implementare il sistema sulla FPGA XC5VLX110T di Xilinx, priva del processore hardcore, e analizzare la scalabilità degli acceleratori hardware, collegati al MicroBlaze tramite un bus punto a punto chiamato Fast Simplex Link (FSL). La soluzione composta con tre moduli hardware connessi, ha ottenuto il migliore risultato con uno speed-up pari a circa 74x, rispetto alla soluzione software. Aumentando il numero di processori in relazione al numero di acceleratori collegati ad ognuno, è risultato che un'architettura composta, da due MicroBlaze collegati ognuno a tre moduli hardware, ottiene uno speed-up di circa 146x, rispetto alla soluzione software. Tale soluzione risulta essere la più performante, con uno speed-up di circa 2,36x, rispetto alle prestazioni ottenute dall'architettura di partenza. I principali contributi innovativi di questo lavoro sono: 1) l'individuazione delle caratteristiche principali e più ricorrenti che caratterizzano l'algoritmo MDR, 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 creato 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 architetture sono state realizzate considerando diversi tipi di FPGA, processori, 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 architetture migliori in relazione ai costi e alle prestazioni.