Efficient implementations of Bloom filter using block RAMs and DSP slices on the FPGA. (8th August 2019)

• Record Type: Journal Article
• Authors: Wada, Takuma; Matsumura, Naoki; Yasudo, Ryota; Nakano, Koji; Ito, Yasuaki
• Is Part Of: Concurrency and computation. Volume 33:Number 12(2021)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-08-08
• Subjects: database -- hardware algorithm -- hash function -- intrusion detection; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5475
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: This paper presents efficient FPGA implementations for the Bloom filter, in which a large set P of L ‐byte patterns are registered beforehand. Our Bloom filter circuit performs the byte stream pattern test such that it receives an input byte stream t and outputs the bit stream in every clock cycle. Each bit of the output bit stream is 1 if an L ‐byte sequence of t starting from the corresponding position is identical with one of the patterns in P . Our circuits use rolling hash functions to compute signatures of all patterns in P registered in Ultra RAMs of the Xilinx UltraScale+ FPGA VU9P. We present two types of implementations, DSP‐based implementation and RAM‐based implementation to compute rolling hash functions of L ‐byte sequences using DSP slices and Block RAMs in the FPGA, respectively. The experimental results show that both DSP‐based and RAM‐based Bloom filter circuits for 4800K patterns of length 1024 can perform the byte stream pattern test for 1.1 Gps and 1.3 Gbps input byte streams, respectively, with false positive probability 10 −12 . Moreover, we can configure DSP‐based and RAM‐based Bloom filter circuits for 100K patterns to work for 54.9 Gbps and 62.2 Gbps input byte streams, respectively, with false positive probability 10 −12 .