FPGA-based high performance architecture for computational biology : the case of the Smith-Waterman algorithm

The development of computational biology increased the complexity of the algorithms used by biologists. The huge amount of data they need to process and the complexity of these algorithms, raised the problem of increasing the amount of computational power needed to perform the computation. In this scenario, hardware accelerators revealed to be efficient in achieving a speed-up in the computation while, at the same time, saving power consumption. Among the algorithms used in computational biology,the Smith-Waterman algorithm is a dynamic programming algorithm, guaranteed to find the optimal local alignment between two strings that could be nucleotides or proteins. This pairwise alignment algorithm is particularly compute intensive and for this reason, in the state of the art, there are many implementation of the Smith-Waterman algorithm that involve the use of heuristics in order to speed-up the calculation. Unfortunately, by using such optimizations, the algorithms are no more guaranteed to find the optimal local alignment between the two strings. Furthermore, they may not be able to find similarities for sequences that are very distant. The works presented here is an analysis and successive FPGA-based hardware acceleration of the Smith-Waterman algorithm used to perform pairwise alignment of DNA sequences. We will provide an overview of the state of the art and an analysis of the algorithm exploiting the Berkeley Roofline Model. We will then describe the hardware architecture created for the acceleration. The hardware acceleration will be performed by using the new tool-chain produced by Xilinx, SDAccel. We will target two boards produced by the company Alpha Data, the ADM-PCIE-7V3 and the ADM-PCIE-KU3.

L’evoluzione della biologia computazionale ha aumentato la complessità degli algoritmi usati dai biologi. L' enorme quantità di dati da processare e la complessità stessa degli algoritmi usati per la computazione, hanno fatto sorgere il problema di aumentare la quantità di potenza computazionale necessaria. In questo scenario, gli acceleratori hardware si sono rivelati uno strumento efficiente nel velocizzare la computazione mantenendo, allo stesso tempo, un basso consumo di potenza. Tra gli algoritmi usati in biologia computazionale, l'algoritmo di Smith-Waterman è un algoritmo di programmazione dinamica che garantisce l'ottimo allineamento locale tra due stringhe che posso essere nucleotidi o proteine. Questo algoritmo di allineamento è particolarmente intenso da un punto di vista della computazione, e per questo motivo, nello stato dell'arte sono presenti diverse implementazioni che utilizzano metodi euristici per velocizzarlo. Sfortunatamente, usando questo tipo di ottimizzazioni, non è più garantito che l'algoritmo trovi l'allineamento ottimale tra le due stringhe. In più, esso potrebbe non essere in grado di trovare similarità per sequence che sono molto distanti. Il lavoro che viene presentato è un' analisi, ed una successiva accelerazione hardware basata su FPGA, dell'algoritmo di Smith-Waterman usato per fare allineamento a coppie di sequence di DNA. Faremo un'analisi dello stato dell'arte ed un'analisi dell'algoritmo utilizzando il modello Roofline di Berkeley. Descriveremo poi l'architettura hardware creata per l'accelerazione. L'accelerazione hardware verrà effettuata utilizzando il nuovo strumento sviluppato da Xilinx, SDAccel. Utilizzeremo due board prodotte dalla compagnia AlphaData, la ADM-PCIE-7V3 e la ADM-PCIE-KU3.