A framework for the aided design of high-performance Genome analysis applications on heterogeneous architectures

Technological innovation and the declining cost of Next Generation Sequencing (NGS) have driven an explosion in the quantity of genomic research. However, analyzing the massive amount of sequencing data generated from this research has revealed a great computational challenge. The rate of data generation in genomics is outpacing the rate at which it can be processed, and demand more computational power than what current processors can deliver. Indeed, Central Processing Unit (CPU) performance is not following the same trend as it is becoming extremely difficult to integrate more transistors on a chip. Consequently, as we reach the end of Moore’s Law predictions, we need new architectural solutions to satisfy the continuously growing performance demand of High-Performance Computing (HPC) applications like genomic algorithms. In this context, hardware, namely Graphics Processing Units (GPUs) and Field Programmable Gate Arrays (FPGAs), incarnate an effective solution to offload compute-intensive tasks from the CPU. However, in order to fully exploit the computing power of GPUs and FPGAs, applications must be developed from the ground up, specifically targeting these architectures. Moreover, the process of developing highly performing heterogeneous applications still requires both domain-specific knowledge and expertise to leverage the architecture effectively. For this reason, the focus of this dissertation is a \textit{framework} for the development of genomic applications exploiting high-performance computing with heterogeneous hardware architectures. Indeed, the objective of this work is to both provide a customizable, fully hardware-accelerated genomic pipeline and help the end user when developing genomic applications. The key aspect of this work is to focus on flexibility; therefore, the integrated pipeline provides multiple implementations for each pipeline stage that are compatible with a wide range of GPUs and FPGAs. Furthermore, knowing the rapid change in the scope of algorithms, genomic pipelines need to be frequently updated. Because of this, the framework enables and provides guidance for users to implement their own applications on GPU. For these reasons, this dissertation explores the crucial issues and peculiar characteristics of the different architectures employed in the framework. It begins with a Chapter providing an overview of genome assembly and heterogeneous architectures. Then, the dissertation dives into the framework description, providing an in-depth analysis of every accelerated step of the genome assembly pipeline. For each step, the dissertation includes design methodologies, design innovations, literature overview, and performance analysis. Finally, this dissertation depicts how the framework can be exploited for developing highly performance GPU algorithms that can be exploited in the genome-assembly pipeline, providing various performance analyses and examples to prove its effectiveness.

L'innovazione tecnologica e il calo dei costi della Next Generation Sequencing (NGS) hanno guidato un'esplosione nella quantità di ricerche genomiche. Tuttavia, l'analisi dell'enorme quantità di dati di sequenziamento generati da questa ricerca ha anche rivelato una sfida computazionale. La velocità di generazione di dati genomici sta superando la velocità con cui essi possono essere elaborati, richiedendo una potenza computazionale piú elevata di quella che gli attuali processori possono fornire. Le prestazioni delle Unitá Centrali di Elaborazione (CPU) non riescono a seguire lo stesso ritmo di evoluzione, in quanto negli ultimi anni é diventato estremamente difficile integrare transistor di dimensione sempre piú piccola all'interno di un chip. Di conseguenza, mentre raggiungiamo la fine delle previsioni della Legge di Moore, abbiamo bisogno di nuove soluzioni per soddisfare la crescente domanda di prestazioni delle applicazioni che richiedono Computazione ad Alte Prestazioni (HPC) come gli algoritmi per l''analisi genomica. In questo contesto, acceleratori hardware, in particolare le Unitá di elaborazione Grafica (GPU) e i Field Programmable Gate Arrays (FPGAs), rappresentano una soluzione efficace per scolgere compiti intensivi al posto della CPU. Tuttavia, per sfruttare appieno la potenza di calcolo delle GPU e FPGA, algoritmi e applicazioni devono essere sviluppate da zero, concentrandosi sulle specifiche caratteristiche di queste architetture. Inoltre, il processo di sviluppo di applicazioni che sfruttano architetture eterogenee ad alte prestazioni richiede conoscenze specifiche del dominio oltre che competenze specifiche per sfruttare efficacemente l'architettura. Per questa ragione, l'obiettivo di questa tesi è un \textit{framework} per lo sviluppo di applicazioni genomiche che sfruttano la computazione ad alte prestazioni con architetture hardware eterogenee. Infatti, l'obiettivo di questo lavoro è sia fornire una pipeline genomica completamente accelerata in hardware, sia aiutare l'utente finale nello sviluppo di applicazioni genomiche. L'aspetto chiave di questo lavoro è concentrarsi sulla flessibilità; pertanto, la pipeline integrata fornisce molteplici implementazioni per ogni stadio della pipeline, compatibili con una vasta gamma di GPU e FPGA. Inoltre, conoscendo il rapido cambiamento nell'ambito degli algoritmi, le pipeline genomiche devono essere aggiornate frequentemente. Per questo motivo, il framework permette e fornisce indicazioni per gli utenti per implementare applicazioni GPU all'interno del framework. Questa tesi esplora le questioni cruciali e le caratteristiche peculiari delle diverse architetture impiegate nel framework. Il primo capitolo che fornisce una panoramica dell'assemblaggio del genoma e delle architetture eterogenee. Successivamente, la tesi approfondisce la descrizione del framework, fornendo un'analisi dettagliata di ogni fase di analisi della pipeline di assemblaggio del genoma che é stata accelerata nel framework. Per ogni fase, la tesi descrive metodologie di progettazione, innovazioni introdotte, panoramica della letteratura e analisi delle prestazioni delle soluzioni presentate. Infine, questa tesi illustra come il framework può essere sfruttato per sviluppare algoritmi su GPU ad alte prestazioni che possono essere utilizzati nella pipeline di assemblaggio del genoma, fornendo varie analisi delle prestazioni ed esempi per dimostrare la sua efficacia.