PipeBSW: A Two-Stage Pipeline Structure for Banded Smith-Waterman Algorithm on FPGA

Abstract

With the development of bioinformatics, there is unprecedented progress and wide applications of DNA sequencing technology, especially in helping biological and medical researchers obtain and analyze complete DNA sequences. Smith-Waterman (S-W) algorithm is one of the critical algorithms used in this technology. However, the tremendous amount of DNA sequence data makes it very inefficient to implement the algorithm only with software, so many recent works have tried to accelerate it on hardware. Unfortunately, many of them implemented on the CPU+FPGA heterogeneous platform are likely to require high memory bandwidth and large hardware resource. To mitigate these drawbacks, in this paper we propose PipeBSW, a hardware acceleration implementation on FPGA based on the concept of banded S-W. Using the lookahead calculation technique in cells and a two-stage pipeline structure for processing elements and the backtracking module, the experimental results show that the proposed system can achieve a 720.9Mbps throughput with a 58.4% LUT consumption reduction, compared with the prior work without the pipeline structure.

Publication
IEEE Computer Society Annual Symposium on VLSI 2021