Network on chip based hardware accelerators for computational biology

The focus of this thesis is the design and performance evaluation of Network on Chip (NoC) based multi-core hardware accelerators for computational biology. Sequence analysis and phylogenetic reconstruction are the two problems in this domain which have been addressed here. The basic characteristic of sequence analysis is that it is data intensive in nature whereas the kernel operation in phylogenetic reconstruction is compute intensive. Due to exponentially growing sequence databases, computing sequence alignment 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 this application can be exploited efficiently. Network-on-Chip (NoC) is a very efficient method to achieve such large scale integration. The phylogenetic reconstruction application involves solving the breakpoint median problem which reduces to solving multiple instances of the Traveling Salesman Problem (TSP). Specifically, we (i) propose optimized NoC architectures for different sequence alignment algorithms that were originally designed for distributed memory parallel computers, (ii) a custom NoC architecture for solving the breakpoint phylogeny problem (iii) 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 biocomputing applications, 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 102-10 3-fold speedup over other existing solutions. 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.