More Web Proxy on the site http://driver.im/

research-article

Way guard: a segmented counting bloom filter approach to reducing energy for set-associative caches

Authors:

Hsien-Hsin S. LeeAuthors Info & Claims

ISLPED '09: Proceedings of the 2009 ACM/IEEE international symposium on Low power electronics and design

Pages 165 - 170

https://doi.org/10.1145/1594233.1594276

Published: 19 August 2009 Publication History

Publisher Site Get Access

Abstract

The design trend of caches in modern processors continues to increase their capacity with higher associativity to cope with large data footprint and take advantage of feature size shrink, which, unfortunately, also leads to higher energy consumption. This paper presents a technique using segmented counting Bloom filters called "Way Guard" to reduce the number of redundant way lookups in large set-associative caches to achieve dynamic energy savings. Our Way Guard mechanism only looks up an average of 25-30% of the cache ways and saved up to 65% of the L2 energy and up to 70% of the L1 cache energy.

References

[1]

B. Batson and T. N. Vijaykumar. Reactive-Associative Caches. Proc. of Int'l Conf. on Parallel Architectures and Compilation Techniques, 2001.

Digital Library

[2]

A. Border and M. Mitzenmacher. Network application of bloom filters: A Survey. In 40th Annual Allerton Conference on Communication, Control, and Computing, 2002.

[3]

B. Calder, D. Grunwald, and J. Emer. Predictive sequential associative cache. Proc. of the Int'l Symp. on High-Performance Computer Architecture, 1996.

Digital Library

[4]

Y.-J. Chang, S.-J. Ruan, and F. Lai. Sentry tag: An efficient filter scheme for low power cache. In Proc. the 7th Asia-Pacific Computer Systems Architectures Conference, 2002.

Digital Library

[5]

S. Cohen and Y. Matias. Spectral bloom filters. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, 2003.

Digital Library

[6]

S. Dharmapurikar, P. Krishnamurthy, T. Sproull, and J. Lockwood. Deep packet inspection using parallel bloom filters. In IEEE Hot Interconnects 12, 2003.

[7]

L. Fan, P. Cao, J. Almeida, and A. Broder. Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking, 8(3):281--293, 2000.

Digital Library

[8]

M. Ghosh, E. Özer, S. Biles, and H.-H. S. Lee. Efficient System-on-Chip Energy Management with a Segmented Bloom Filter. In Proc. the 19th Int'l Conf. on Architecture of Computing Systems, 2006.

Digital Library

[9]

K. Inoue, T. Ishihara, and K. Murakami. Way-predicting set-associative cache for high performance and low energy consumption. In Proc. 1999 International Symposium on Low Power Electronics and Design, 1999.

Digital Library

[10]

K. Lawton. Welcome to the Bochs x86 PC Emulation Software Home Page. http://www.bochs.com.

[11]

G. Keramidas, P. Xekalakis, and S. Kaxiras. Applying Decay to Reduce Dynamic Power in Set-Associative Caches. In 2007 International Conference on High Performance Embedded Architectures and Compilers, January 2007.

Digital Library

[12]

R. Kessler, R. Jooss, A. Lebeck, and M. Hill. Inexpensive Implementations Of Set-Associativity. The 16th Annual Int'l Symp. on Computer Architecture, 1989.

Digital Library

[13]

A. Kumar, J. Xu, J. Wang, O. Spatschek, and L. Li. Space-code bloom filter for efficient per-flow traffic measurement. In Proc. IEEE INFOCOM, March 2004.

[14]

A. Ma, M. Zhang, and K. Asanovic. Way memoization to reduce fetch energy in instruction caches. Workshop on Complexity Effective Design, 2001.

[15]

N. Mehta, B. Singer, R. I. Bahar, M. Leuchtenburg, and R. Weiss. Fetch halting on critical load misses. In Proc the 22nd Int'l Conf. on Computer Design, 2004.

Digital Library

[16]

G. Memik, G. Reinman, and W. H. Mangione-Smith. Just say no: Benefits of early cache miss determination. In Proceedings of the Ninth International Symposium on High Performance Computer Architecture, 2003.

Digital Library

[17]

A. Moshovos, G. Memik, B. Falsafi, and A. Choudhary. Jetty: Snoop filtering for reduced power in smp servers. In Proceedings of International Symposium on High Performance Computer Architecture (HPCA-7), January 2001.

[18]

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 Proceedings of the 16th International Conference of Supercomputing, pages 189--198, 2002.

Digital Library

[19]

A. Roth. Store Vulnerability Window (SVW): Re-Execution Filtering for Enhanced Load Optimization. In Proc. of the 32th Int'l Symp. on Computer Architecture, 2005.

Digital Library

[20]

S. Sethumadhavan, R. Desikan, D. Burger, C. R. Moore, and S. W. Keckler. Scalable hardware memory disambiguation for high ilp processors. In Proceedings of the 36th International Symposium for Microarchitecture, 2003.

Digital Library

[21]

D. H. Woo, M. Ghosh, E. Özer, S. Biles, and H.-H. S. Lee. Reducing energy of virtual cache synonym lookup using bloom filters. In Proc. the 2006 Int'l Conf. on Compilers, Architecture and Synthesis for Embedded Systems, 2006.

Digital Library

[22]

C. Zhang, F. Vahid, J. Yang, and W. Najjar. A way-halting cache for low-energy high-performance systems. ACM Transactions on Architecture and Code Optimization (TACO), 2(1):34--54, 2005.

Digital Library

[23]

M. Zhang and K. Asanovic. Highly-associative caches for low-power processors. In Kool Chips Workshop in conj. with MICRO-33, 2000.

Cited By

Jiang ZYang KFisher NGuan NAudsley NDong Z(2024)Hopscotch: A Hardware-Software Co-Design for Efficient Cache Resizing on Multi-Core SoCsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333271135:1(89-104)Online publication date: Jan-2024
https://doi.org/10.1109/TPDS.2023.3332711
Ravipati DGoel RSanten VAmrouch HPanda P(2024)CAPE: Criticality-Aware Performance and Energy Optimization Policy for NCFET-Based CachesIEEE Transactions on Computers10.1109/TC.2024.345773473:12(2830-2843)Online publication date: Dec-2024
https://doi.org/10.1109/TC.2024.3457734
Sakalis CKaxiras SSjälander M(2022)Delay-on-Squash: Stopping Microarchitectural Replay Attacks in Their TracksACM Transactions on Architecture and Code Optimization10.1145/356369520:1(1-24)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1145/3563695
Show More Cited By

Index Terms

Way guard: a segmented counting bloom filter approach to reducing energy for set-associative caches
1. Computer systems organization
  1. Architectures
2. Hardware
  1. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory

Recommendations

Reducing energy of virtual cache synonym lookup using bloom filters
CASES '06: Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems

Virtual caches are employed as L1 caches of both high performance and embedded processors to meet their short latency requirements. However, they also introduce the synonym problem where the same physical cache line can be present at multiple locations ...
Heterogeneous way-size cache
ICS '06: Proceedings of the 20th annual international conference on Supercomputing

Set-associative cache architectures are commonly used. These caches consist of a number of ways, each of the same size. We have observed that the different ways have very different utilization, which motivates the design of caches with heterogeneous way ...
An energy-efficient L2 cache architecture using way tag information under write-through policy

Many high-performance microprocessors employ cache write-through policy for performance improvement and at the same time achieving good tolerance to soft errors in on-chip caches. However, write-through policy also incurs large energy overhead due to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISLPED '09: Proceedings of the 2009 ACM/IEEE international symposium on Low power electronics and design

August 2009

452 pages

ISBN:9781605586847

DOI:10.1145/1594233

General Chairs:
Jörg Henkel
University of Karlsruhe
,
Ali Keshavarzi
Taiwan Semiconductor Manufacturing Company
,
Program Chairs:
Naehyuck Chang
Seoul National University
,
Tahir Ghani
Intel Corporation

Copyright © 2009 ACM.

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: 19 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ISLPED'09

Sponsor:

ISLPED'09: International Symposium on Low Power Electronics and Design

August 19 - 21, 2009

CA, San Fancisco, USA

Acceptance Rates

ISLPED '09 Paper Acceptance Rate 72 of 208 submissions, 35%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
326
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Jiang ZYang KFisher NGuan NAudsley NDong Z(2024)Hopscotch: A Hardware-Software Co-Design for Efficient Cache Resizing on Multi-Core SoCsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2023.333271135:1(89-104)Online publication date: Jan-2024
https://doi.org/10.1109/TPDS.2023.3332711
Ravipati DGoel RSanten VAmrouch HPanda P(2024)CAPE: Criticality-Aware Performance and Energy Optimization Policy for NCFET-Based CachesIEEE Transactions on Computers10.1109/TC.2024.345773473:12(2830-2843)Online publication date: Dec-2024
https://doi.org/10.1109/TC.2024.3457734
Sakalis CKaxiras SSjälander M(2022)Delay-on-Squash: Stopping Microarchitectural Replay Attacks in Their TracksACM Transactions on Architecture and Code Optimization10.1145/356369520:1(1-24)Online publication date: 17-Nov-2022
https://dl.acm.org/doi/10.1145/3563695
Oh YChung E(2021)Energy-Efficient Shared Cache Using Way Prediction Based on Way Access Dominance DetectionIEEE Access10.1109/ACCESS.2021.31267399(155048-155057)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3126739
Wu WZhu QWang FLin RQi F(2020)Compiler Optimizing for Power Efficiency of On-Chip MemoryAdvanced Computer Architecture10.1007/978-981-15-8135-9_21(290-303)Online publication date: 5-Sep-2020
https://doi.org/10.1007/978-981-15-8135-9_21
Kim KJeong YLee YLee S(2019)Analysis of Counting Bloom Filters Used for Count ThresholdingElectronics10.3390/electronics80707798:7(779)Online publication date: 11-Jul-2019
https://doi.org/10.3390/electronics8070779
Kim MChang ILee H(2019)Segmented Tag Cache: A Novel Cache Organization for Reducing Dynamic Read EnergyIEEE Transactions on Computers10.1109/TC.2019.2906872(1-1)Online publication date: 2019
https://doi.org/10.1109/TC.2019.2906872
Rostami-Sani SValinataj MChamazcoti S(2018)Parloom: a new low-power set-associative instruction cache architecture utilizing enhanced counting Bloom filter and partial tagsJournal of Circuits, Systems and Computers10.1142/S0218126619502037Online publication date: 15-Nov-2018
https://doi.org/10.1142/S0218126619502037
Young VChou CJaleel AQureshi M(2018)ACCORDProceedings of the 45th Annual International Symposium on Computer Architecture10.1109/ISCA.2018.00036(328-339)Online publication date: 2-Jun-2018
https://dl.acm.org/doi/10.1109/ISCA.2018.00036
Alves RKaxiras SBlack-Schaffer D(2018)Dynamically Disabling Way-prediction to Reduce Instruction Replay2018 IEEE 36th International Conference on Computer Design (ICCD)10.1109/ICCD.2018.00029(140-143)Online publication date: Oct-2018
https://doi.org/10.1109/ICCD.2018.00029
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents