BitBlender: Scalable, High-Throughput Bloom Filter Acceleration on FPGAs with Dynamic Scheduling

The Bloom filter is one of the most widely used data structures in big data analytics to efficiently filter out vast amounts of noisy data. Bloom filters are used to accelerate many applications, including databases, networking, security, and bioinformatics. Unfortunately, prior Bloom filter designs only focus on single-input-stream acceleration, and cannot match the increasing data rates offered by modern networks. The underlying problem is reading from the bit-vector, which requires fast random access. Since accesses are random, sharing the bit-vector is difficult, due to dynamic access conflicts. However, naïvely duplicating the single-stream accelerator sacrifices scalability, due to the resource overhead of storing the entire bit-vector multiple times. We present BitBlender, the first scalable, high-throughput multi-input-stream Bloom filter acceleration framework in HLS. BitBlender’s architecture stores a large bit-vector in on-chip memories for ultra low latency. Moreover, it efficiently shares access among all input streams to allow high throughput even for large Bloom filters with low false-positive rates. To enable this efficient shared access, we design and implement the novel Arbiter and Unshuffle modules, to dynamically schedule conflicting accesses to execute sequentially, and non-conflicting accesses to execute in parallel. To support different user configurations of the Bloom filter, we also develop an automation flow, together with an accurate performance estimator, to automatically generate the best BitBlender design to meet a user-provided Bloom filter specification. Experimental results show that, on the AMD/Xilinx Alveo U280 FPGA, BitBlender achieves a throughput up to 3,213 MQueries/s (i.e., 12.8 GB/s) for a 130Mib bit-vector with 0.005% false-positive rate. Compared to the highly-optimized Rust crate fastbloom running on 24 CPU threads, it achieves an average speedup of 8.89x, up to a maximum of 10.47x. Compared to the naïvely-duplicated multi-stream FPGA design, it achieves an average speedup of 5.30x, up to a maximum of 7.42x. BitBlender is available at https://github.com/SFU-HiAccel/BitBlender .