A methodology for automatic GPU kernel optimization

In recent years Graphic Processing Units have seen widespread adoption in many scientific fields, from Machine Learning (ML) to Genomics. Their use makes it possible to achieve significant speedups and improvements in power efficiency over computationally intensive algorithms compared to General Purpose Central Processing Units. However, algorithms require specific knowledge of the GPU architecture and expertise to achieve significant results. In this work, we describe a methodology for automatic GPU kernel optimization. Our methodology exploits the Berkeley Roofline Model to perform a performance analysis of the algorithm considered and aims to increase the accessibility of GPU programming automatizing the optimization process of the kernel. We provide an in-depth analysis of this methodology, an overview on the state of the art, and a description of a tool we developed that automatically applies our methodology to obtain a highly optimized GPU version of two of the most popular algorithms used in computational biology, the X-drop and Smith-Waterman algorithms. The Smith-Waterman algorithm is one of the most used algorithms in genomics pipelines. The algorithm finds the optimal local alignment between two genomic sequences, at the cost of being particularly compute-intensive. The popular X-drop algorithm reduces the time required by the alignment by searching only for high-quality alignments. The algorithms accelerated using our methodology achieve more than 6x and 3x speed-up, for the X-drop and Smith-Waterman algorithms respectively, with respect to the state of the art implementation of these algorithms.

Negli ultimi anni le Unità di Elaborazione Grafica sono state utilizzate in molti campi scientifici, dal machine learning (ML) alla genomica. Il loro utilizzo consente di ottenere miglioramenti significativi sia in termini di tempo di esecuzione che in ​​termini di efficienza energetica rispetto ad algoritmi computazionalmente intensivi eseguiti su processori tradizionali. Tuttavia, per ottenere risultati significativi, lo sviluppo di algoritmi richiede una conoscenza specifica dell'architettura delle GPU e competenze specifiche. In questo lavoro, descriviamo una metodologia per l'ottimizzazione automatica di applicazione eseguite su GPU. La nostra metodologia sfrutta il modello del Roofline di Berkeley per eseguire un'analisi delle prestazioni dell'algoritmo considerato, e mira ad aumentare l'accessibilità della programmazione delle GPU automatizzando il processo di ottimizzazione degli algoritmi. Forniamo un'analisi approfondita di questa metodologia, una panoramica sullo stato dell'arte e una descrizione di uno strumento che sviluppato che implementata la nostra metodologia in maniera automatica per sviluppare una versione altamente ottimizzata su GPU di due degli algoritmi più popolari nel campo della biologia computazionale, gli algoritmi di X-drop e di Smith-Waterman. L'algoritmo di Smith-Waterman è uno degli algoritmi più utilizzati nei processi di analisi genomica. L'algoritmo trova l'ottimo allineamento locale tra due sequenze genomiche, al costo di avere un'intensità di calcolo particolarmente elevata. Il famoso algoritmo X-drop riduce il tempo richiesto dall'allineamento cercando solo allineamenti di alta qualità. Gli algoritmi accelerati utilizzando la nostra metodologia raggiungono una velocità maggiore di 6x e 3x, rispettivamente per gli algoritmi X-drop e Smith-Waterman, rispetto alle soluzioni attualmente presenti nello stato dell'arte.