skip to main content
10.1145/1165573.1165634acmconferencesArticle/Chapter ViewAbstractPublication PagesislpedConference Proceedingsconference-collections
Article

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

Published: 04 October 2006 Publication History

Abstract

We study the energy, latency and area characteristics of two Counting Bloom Filter implementations using full custom layouts in a commercial 0.13μm technology. 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 [12] 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.

References

[1]
P. Alfke, "Efficient Shift Registers, LFSR Counters, and Long Pseudo-Random Sequence Generators", Xilinx, Application Note 052, Jul. 1996.
[2]
B. S. Amrutur and M. A. Horowitz, "Fast Low-Power Decoders for RAMs", IEEE Journal of Solid-State Circuits, 36(10):1506--1515, Oct. 2001.
[3]
B. S. Amrutur, "Design and Analysis of Fast Low Power SRAMs", Ph.D. dissertation, Electrical Engineering Department, Stanford University, 1999.
[4]
B. S. Amrutur and M. A. Horowitz, "Speed and Power Scaling of SRAM's", IEEE Journal of Solid-State Circuits, 35(2):175--185, Feb. 2000.
[5]
P. H. Bardell, W. H. McAnney, and J. Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, Inc., 1987.
[6]
D. Burger and T. Austin. "The Simplescalar Tool Set v2.0", Technical Report UW-CS-97-1342, Computer Sciences Department, University of Wisconsin-Madison, Jun. 1997.
[7]
M. Margala, "Low-power SRAM Circuit Design", In Proc. of IEEE Workshop on Memory Technology, Design and Testing, 115 -- 122, Aug. 1999.
[8]
A. Moshovos, "RegionScout: Exploiting Coarse-Grain Sharing in Snoop-Coherence", In Proc. Annual International Symposium on Computer Architecture, Jun. 2005.
[9]
A. Moshovos, G. Memik, B. Falsafi, and A. Choudhary, "Jetty: Filtering Snoops for Reduced Energy Consumption in SMP Servers", In Proc. of the Annual International Conference on High-Performance Computer Architecture, 85--96, Feb. 2001.
[10]
S. Sethumadhavan, R. Desikan, D. Burger, C.R. Moore, S.W. Keckler, "Scalable Hardware Memory Disambiguation for High-ILP Processors", IEEE Micro, 24(6):118 -- 127, Nov. 2004.
[11]
M. R Stan, "Synchronous Up/Down Counter with Clock Period Independent of Counter Size", In Proc. IEEE Symposium on Computer Arithmetic, 274--281, Jul. 1997.
[12]
J. K. Peir, S.C. Lai, S.L. Lu, J. Stark, and K. Lai, "Bloom Filtering Cache Misses for Accurate Data Speculation and Prefetching", In Proc. Annual International Conference on Supercomputing, Jun. 2002.

Cited By

View all
  • (2008)L-CBFIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2008.200024416:6(628-638)Online publication date: 1-Jun-2008
  • (2007)Late-bindingACM SIGARCH Computer Architecture News10.1145/1273440.125070535:2(347-357)Online publication date: 9-Jun-2007
  • (2007)Late-bindingProceedings of the 34th annual international symposium on Computer architecture10.1145/1250662.1250705(347-357)Online publication date: 9-Jun-2007

Index Terms

  1. L-CBF: a low-power, fast counting bloom filter architecture

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Conferences
        ISLPED '06: Proceedings of the 2006 international symposium on Low power electronics and design
        October 2006
        446 pages
        ISBN:1595934626
        DOI:10.1145/1165573
        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Sponsors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        Published: 04 October 2006

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. counting bloom filters
        2. delay
        3. energy per operation
        4. processors

        Qualifiers

        • Article

        Conference

        ISLPED06
        Sponsor:
        ISLPED06: International Symposium on Low Power Electronics and Design
        October 4 - 6, 2006
        Bavaria, Tegernsee, Germany

        Acceptance Rates

        Overall Acceptance Rate 398 of 1,159 submissions, 34%

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)5
        • Downloads (Last 6 weeks)2
        Reflects downloads up to 15 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2008)L-CBFIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2008.200024416:6(628-638)Online publication date: 1-Jun-2008
        • (2007)Late-bindingACM SIGARCH Computer Architecture News10.1145/1273440.125070535:2(347-357)Online publication date: 9-Jun-2007
        • (2007)Late-bindingProceedings of the 34th annual international symposium on Computer architecture10.1145/1250662.1250705(347-357)Online publication date: 9-Jun-2007

        View Options

        Login options

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media