A High-Performance Double-Layer Counting Bloom Filter for Multicore Systems

Bo-Cheng Lai, Kuan Ting Chen, Ping Ru Wu

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

The snoopy-based protocol is a widely used cache coherence mechanism for a symmetric multiprocessor (SMP) system. However, this broadcast-based protocol blindly disseminates data sharing information across the system, and introduces many unnecessary data operations. This paper proposes a novel architecture of double-layer counting Bloom filter (DLCBF) to reduce the unnecessary data lookups on the local cache and redundant data transactions on the shared interconnection of an SMP system. By adding an extra filtering layer, the DLCBF effectively exploits the data locality of applications. The two-layer hierarchy reduces the storage size of DLCBF by 18.75%, and achieves 81.99% and 31.36% better filtering rates when compared with a classic Bloom filter (BF) and original counting BF, respectively. When applied on the segmented shared bus of an SMP system, the DLCBF outperforms the previous work by 58% for In-filters and 1.86&Times; for Out-filters. This paper also comprehensively explores the key design parameters of DLCBF, including the sizes of top-layer, bottom-layer, and multilayer design. The results show that enlarging the layer filters enhance the filtering rates of DLCBF, while adding an extra filter layer only provides slight benefit.

Original languageEnglish
Article number6967855
Pages (from-to)2473-2486
Number of pages14
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Volume23
Issue number11
DOIs
StatePublished - Nov 2015

Keywords

  • Cache memory
  • System analysis and design
  • multicore processing
  • simulation

Fingerprint

Dive into the research topics of 'A High-Performance Double-Layer Counting Bloom Filter for Multicore Systems'. Together they form a unique fingerprint.

Cite this