The Smith-Waterman algorithm is a dynamic-programming-based database search algorithm that suffers from a long computation time. Hence, the authors target the implementation of the Smith-Waterman algorithm on a heterogeneous computing platform, in order to improve the performance of sequence database searches. The heterogeneous platform consists of: a streaming single instruction, multiple data (SIMD) extensions 2 (SSE2) instruction-enabled multicore processor; a field-programmable gate array (FPGA) coprocessor; and a legacy central processing unit (CPU) processor.
The main focus is on scheduling the tasks so that all of the processors are assigned, thereby increasing the throughput and reducing the computation time for a single dataset of sequence database searches. Data prefetching on the FPGA reduces the data starvation and, combined with latency scheduling, eliminates the communication overhead. The FPGA coprocessor imposes a limit on the maximum length of sequences that it can compute. The query segmentation and overlap is done based on this hard limit, and over 80 percent accuracy is obtained by 15 to 25 percent overlaps. Compared to other configurations used in the experiments, the FPGA+SSE2+message passing interface (MPI) combination provides the best speedup.
In summary, the authors demonstrate a scalable solution by using an FPGA coprocessor as a hardware accelerator for improving the speedup and reducing the computation time in biological sequence database searches.