TL;DR
This paper tackles the bottleneck in FPGA-accelerated biological sequence similarity searches: the slow data transfer between the host CPU and the FPGA. They introduce an adaptive data prefetching scheme that dynamically adjusts buffer sizes to overlap data loading with computation, significantly boosting throughput and achieving a 110x speedup over a standard PC.
What Problem Does This Paper Address?
The exponential growth of biological sequence databases (like DNA and protein sequences) has outpaced the capabilities of traditional general-purpose processors for analysis. Field-Programmable Gate Arrays (FPGAs) offer a promising solution due to their reconfigurable nature, allowing them to be tailored for specific tasks like sequence similarity searches (e.g., using the Smith-Waterman algorithm). However, a major hurdle in using FPGAs as coprocessors is the communication bottleneck between the host CPU and the FPGA. The relatively slow PCI bus and limited on-board memory of FPGAs mean that data transfer often dominates the execution time, negating the computational speedup gained from the FPGA. This paper aims to alleviate this bottleneck by optimizing the data transfer process.
Methods
The core innovation is an adaptive data prefetching scheme. Instead of a static approach where data is loaded and then processed, this method uses double buffering to overlap data transfer and computation.
Here's how it works:
- Double Buffering: Two buffers are used for incoming database sequences and two for outgoing results. While the FPGA processes data from one buffer, the host CPU can load the next set of sequences into the other.
- Adaptive Prefetching: The key novelty is that the size of these prefetching buffers is not fixed. It's dynamically adjusted based on the length of the query sequence. The paper proposes that shorter queries require smaller buffers, while longer queries benefit from larger buffers. This adaptive approach aims to minimize the "overhead" associated with buffer management and ensure that the data is ready precisely when the FPGA needs it, without being too early or too late.
- DMA (Direct Memory Access): The implementation leverages DMA transfers, which allow the FPGA to access host memory directly without constant CPU intervention, further optimizing data movement.
Datasets
The experiments were conducted using a 1 GB section of the compressed nr protein database, which contains approximately 936 million characters across 2.7 million sequences. Various query sequences of different lengths (ranging from 119 to 1420 characters) were used to evaluate the performance of the proposed scheme.
Key Insights and Ideas
- Communication is King (for FPGAs): While FPGAs excel at computation, the paper strongly emphasizes that without efficient data handling, their potential is severely limited. The communication bottleneck is often more critical than the computational speed itself.
- One Size Does Not Fit All (Buffer Sizes): A static buffer size is suboptimal. The adaptive approach, tailoring buffer size to query length, is crucial for maximizing performance. This is because the balance between computation time and data transfer time shifts with query length.
- Overlapping is the Goal: The core idea of prefetching is to hide latency. By intelligently overlapping data loading with computation, the system can achieve much higher effective throughput.
- FPGA Density vs. Communication Strategy: The paper suggests that while high FPGA density and fast I/O are beneficial, an effective communication strategy (like adaptive prefetching) can be even more critical for achieving high performance, potentially allowing smaller, cheaper FPGAs to compete with larger, more expensive ones.
Key Results
- The adaptive data prefetching scheme achieved up to a 42% overall performance increase compared to a non-prefetching implementation for short query sequences.
- For longer query sequences, improvements of 21% and 16% were observed.
- The system achieved a significant speedup of 110x compared to a standard PC implementation running the serial Smith-Waterman algorithm.
- The data transfer rate was significantly improved, especially for longer query sequences, by the adaptive double buffering approach.
Limitations and Future Work
- Buffer Management Overhead: The paper acknowledges that while adaptive prefetching improves performance, there's still an overhead associated with buffer management, which can lead to idle FPGA coprocessors if not managed optimally.
- Networked Systems: The authors plan to extend this adaptive prefetching strategy to network-based heterogeneous parallel and distributed biological database search platforms.
- Query/Database Length Limitations: The current Smith-Waterman implementation on FPGA has limitations on query and database sequence lengths, which they aim to address via heterogeneous parallel computing in future work.
Summary updated