RNS Smith-Waterman Accelerator based on the moduli set 2 n , 2 n-1 , 2 n-1 -1
Patrick Kwabena Mensah, Edem K. Bankas, Mohammed Muniru Iddrisu · 2018
The Smith-Waterman algorithm is very sensitive but computationally intensive on general purpose CPUs. On the other hand, the FPGA has proven to be an excellent platform for accelerating the algorithm in addition to its low cost and power consumption. This paper therefore proposes the use of the parallelism and carry-free propagation properties of Residue Number Systems (RNS) to accelerate the algorithm on an FPGA; a deviation from the usual binary/decimal implementations. Compared to the only previous known work that uses RNS for this task, our implementation is (1) the first to employ the use of Linear Systolic Arrays (LSA), (2) avoid the use of Lookup Tables, (3) has a larger dynamic range and (4) aligns long sequences. Implemented on a modest hardware and on a Kintex7 FPGA, we achieved a performance improvement of 169 times over the general-purpose processor implementation. This result was obtained using the naïve implementation of LSAs, indicating the positive effects of using RNS.