A parallel bloom filter string searching algorithm on a many-core processor
WenMei Ong, Vishnu Monn Baskaran, Poh Kit Chong, K. K Ettikan, Keh Kok Yong · 2013
This paper analyzes the underlying architecture of a serial Bloom filter string searching algorithm to identify the performance impact of this algorithm for large datasets. Then, a parallel multi-core driven Bloom filter algorithm using software application threads is studied as benchmark. Experimental results suggest that for a set of 10 million strings, this algorithm exhibits speedups of up to 3.3× against a serial Bloom filter algorithm, when using an 8-logical processor multi-core architecture. To further improve the speedup, a many-core driven parallel Bloom filter algorithm is proposed using the Compute Unified Device Architecture (CUDA) parallel computing platform. The proposed algorithm segments the string list into blocks of words and threads in generating the bit table for the string searching process, which maximizes computational performance and sustains consistent string searching results. Experimental results suggest that the proposed algorithm extends the speedup to 5.5× against a serial Bloom filter algorithm, when using a 256-core CUDA graphics processing unit architecture.