EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Kenneth Liu, Zhenman Fang

ACM Transactions on Reconfigurable Technology and Systems · 30.09.2026 · 19 (3) · 1-33

DOI: 10.1145/3814958 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Reconfigurable Technology and Systems, online erschienen am 12.08.2026. Verfasst von Kenneth Liu und 1 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Natural Sciences and Engineering Research Council of Canada, Canada Foundation for Innovation, John R. Evans Leaders Fund.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.89×, up to a maximum of 10.47×. Compared to the naïvely-duplicated multi-stream FPGA design, it achieves an average speedup of 5.30×, up to a maximum of 7.42×. BitBlender is available at https://github.com/SFU-HiAccel/BitBlender .

Förderung

  • Natural Sciences and Engineering Research Council of Canada
  • Canada Foundation for Innovation
  • John R. Evans Leaders Fund

Zitieren

APA

Liu, K., & Fang, Z. (2026). BitBlender: Scalable, High-Throughput Bloom Filter Acceleration on FPGAs with Dynamic Scheduling. ACM Transactions on Reconfigurable Technology and Systems, 19(3), 1-33. https://doi.org/10.1145/3814958

Vancouver

Liu K, Fang Z. BitBlender: Scalable, High-Throughput Bloom Filter Acceleration on FPGAs with Dynamic Scheduling. ACM Transactions on Reconfigurable Technology and Systems. 2026;19(3):1-33. doi:10.1145/3814958

BibTeX
@article{Liu2026,
  author = {Liu, Kenneth and Fang, Zhenman},
  title = {BitBlender: Scalable, High-Throughput Bloom Filter Acceleration on FPGAs with Dynamic Scheduling},
  journal = {ACM Transactions on Reconfigurable Technology and Systems},
  year = {2026},
  volume = {19},
  number = {3},
  pages = {1--33},
  doi = {10.1145/3814958}
}
Kostenlos starten →