Premium
Efficient implementations of Bloom filter using block RAMs and DSP slices on the FPGA
Author(s) -
Wada Takuma,
Matsumura Naoki,
Yasudo Ryota,
Nakano Koji,
Ito Yasuaki
Publication year - 2019
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.5475
Subject(s) - byte , bloom filter , computer science , field programmable gate array , hash function , digital signal processing , filter (signal processing) , block (permutation group theory) , bitstream , parallel computing , computer hardware , algorithm , mathematics , decoding methods , geometry , computer security , computer vision
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 .