Network-on-Chip Hardware Accelerators for Biological Sequence Alignment

• Published in: IEEE transactions on computers 2010-01, Vol.59 (1), p.29-41
• Main Authors: Sarkar, S., Kulkarni, G.R., Pande, P.P., Kalyanaraman, A.
• Format: Article
• Language: English
• Subjects: Acceleration; Bioinformatics; Biology; Computer architecture; Data mining; Decision support systems; DNA/protein sequence alignment; Hardware; hardware acceleration; Network-on-chip; on-chip parallelism
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/TC.2009.133

The most pervasive compute operation carried out in almost all bioinformatics applications is pairwise sequence homology detection (or sequence alignment). Due to exponentially growing sequence databases, computing this operation at a large-scale is becoming expensive. An effective approach to speed up this operation is to integrate a very high number of processing elements in a single chip so that the massive scales of fine-grain parallelism inherent in several bioinformatics applications can be exploited efficiently. Network-on-chip (NoC) is a very efficient method to achieve such large-scale integration. In this work, we propose to bridge the gap between data generation and processing in bioinformatics applications by designing NoC architectures for the sequence alignment operation. Specifically, we 1) propose optimized NoC architectures for different sequence alignment algorithms that were originally designed for distributed memory parallel computers and 2) provide a thorough comparative evaluation of their respective performance and energy dissipation. While accelerators using other hardware architectures such as FPGA, general purpose graphics processing unit (GPU), and the cell broadband engine (CBE) have been previously designed for sequence alignment, the NoC paradigm enables integration of a much larger number of processing elements on a single chip and also offers a higher degree of flexibility in placing them along the die to suit the underlying algorithm. The results show that our NoC-based implementations can provide above 10 2 -10 3 -fold speedup over other hardware accelerators and above 10 4 -fold speedup over traditional CPU architectures. This is significant because it will drastically reduce the time required to perform the millions of alignment operations that are typical in large-scale bioinformatics projects. To the best of our knowledge, this work embodies the first attempt to accelerate a bioinformatics application using NoC.