L-CBF: a low-power, fast counting Bloom filter architecture

We study the energy, latency and area characteristics of two Counting Bloom Filter implementations using a commercial 0.13µm technology and full custom layouts. The first implementation, S-CBF, uses an SRAM array of counts and a shared counter. The second, L-CBF, utilizes an array of up/down linear feedback shift registers. Circuit level simulations demonstrate that for a 1K-entry CBF with a 15-bit count per entry, L-CBF is 3.7 or 1.6 times faster than the S-CBF depending on the operation. The L-CBF requires 2.3 or 1.4 times less energy per operation compared to the S-CBF. However, the L-CBF requires 3.2 times more area. We demonstrate that for one application of CBFs (early hit/miss detection for L1 caches [13] for an aggressive dynamically-scheduled superscalar processor) the energy consumed by the L-CBF is 60 % of the energy consumed by the S-CBF for most of the SPEC CPU 2000 benchmarks.