الفهرس 
Word-Matching Stage
Acceleration of BLASTNOnly 14 pages are availabe for public view
 |  | from | 154 |  |  |
| | | from | 154 | | |
Abstract
Scanning genomic sequence databases is a very common task in bioinformatics to lookup for similarities between the query sequence and particular data-base sequences. The speedup of these searches became a must to keep up with the rapid growth in gene banks; where every year their size is scaled by a factor of 1.5 to 2. The DNA Basic local alignment search tool (BLASTN) is one of the most widely used tool in analysis of DNA sequences. This tool uses heuristics approach to accelerate the time consuming search algorithm. Although BLASTN is a highly optimized algorithm, the growth of biological databases outpaces its speed improvement.
There are several acceleration approaches adopted in BLASTN. Some of these approaches try to accelerate BLASTN in software using more efficient algorithms or heuristics. Other approaches use a hybrid software/hardware architectures. Some of these approaches design hardware accelerators for BLASTN. Since the implementation of BLASTN can benefit from the acceleration through fine-grained and coarse-grained parallelism, the acceleration using hardware is an appealing approach. Similar to any hardware design process, the design process of the BLASTN accelerator is laborious and error prone. Moreover, the algorithm complexity causes the design process to be more complicated. Therefore, there is a rising need to find a more convenient tool for complex systems design.
Raising the abstraction level in the design process became very important in order to cope with the increasing system design complexities. High level synthesis (HLS) introduces such high abstraction level that is essential for efficient modern system design in different domains. The capabilities of HLS help designers produce efficient system in terms of performance and cost by simply writing its functionalities using high level languages, such as C, C++, or SystemC.
The main aim of this research is developing a hardware accelerator for BLASTN algorithm using a more efficient designing tool. Therefore, we pre-sent an HLS solution to accelerate the BLASTN algorithm. Our solution implements the BLASTN stages using C++ as a high level language. The HLS tool automatically transforms the implementation into register transfer level (RTL). The hardware implementation is generated without any knowledge of the RTL design in general and without going through the tedi-ous design process. Also, we implemented an optimized version from our HLS solution using the pipeline directive provided by the HLS tool.
Our experiments show that the use of HLS to directly implement BLASTN is very efficient and improves both the latency and throughput of the algorithm. The HLS implementation achieves a latency and throughput speedup around 20x. Further acceleration is achieved by applying the pipeline directive to optimize the HLS implementation, which yields a latency and throughput speedup around 5x. A comparison versus software implementation shows that an overall latency and throughput speedup of 100x is achieved. We augmented our results with a throughput comparison against similar and previous hardware-accelerated algorithms. Our HLS BLASTN achieves an average throughput speedup of 70x over the NCBI implementation. Furthermore, our HLS BLASTN outperforms the Mercury BLASTN implementation by 11x.