research-article

A table-based method for single-pass cache optimization

Authors:

Ann Gordon-Ross,

Frank VahidAuthors Info & Claims

GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSI

Pages 71 - 76

https://doi.org/10.1145/1366110.1366129

Published: 04 May 2008 Publication History

Abstract

Due to the large contribution of the memory subsystem to total system power, the memory subsystem is highly amenable to customization for reduced power/energy and/or improved performance. Cache parameters such as total size, line size, and associativity can be specialized to the needs of an application for system optimization. In order to determine the best values for cache parameters, most methodologies utilize repetitious application execution to individually analyze each configuration explored. In this paper we propose a simplified yet efficient technique to accurately estimate the miss rate of many different cache configurations in just one single-pass of execution. The approach utilizes simple data structures in the form of a multi-layered table and elementary bitwise operations to capture the locality characteristics of an application's addressing behavior. The proposed technique intends to ease miss rate estimation and reduce cache exploration time.

References

[1]

N.B.A. Milenkovic, M. Milenkovic. A performance evaluation of memory hierarchy in embedded systems. In Proceedings of the 35th Southeastern Symposium on System Theory, pages 427--431, March 2003.

[2]

D.H. Albonesi. Selective cache ways: On-demand cache resource allocation. Journal of Instruction-Level Parallelism, 2, May 2000.

[3]

E. Berg and E. Hagersten. StatCache: A Probabilistic Approach to Efficient and Accurate Data Locality Analysis. In Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS-2004).

Digital Library

[4]

G. Braun, A. Wieferink, O. Schliebusch, R. Leupers, H. Meyr, and A. Nohl. Processor/memory co-exploration on multiple abstraction levels. In Proc. of the Design, Automation and Test in Europe (DATE'03), March 2003.

Digital Library

[5]

C. Cascaval and D.A. Padua. Estimating cache misses and locality using stack distances. In ICS '03: Proceedings of the 17th annual international conference on Supercomputing, pages 150--159, 2003.

Digital Library

[6]

A. Ghosh and T. Givargis. Analytical design space exploration of caches for embedded systems. In Proc. of the Design, Automation and Test in Europe (DATE'03), March 2003.

Digital Library

[7]

A. Gordon-Ross and F. Vahid. A self-tuning configurable cache. In DAC '07: Proceedings of the 44th annual conference on Design automation, pages 234--237, New York, NY, USA, 2007. ACM.

Digital Library

[8]

A. Gordon-Ross, F. Vahid, and N. Dutt. Fast configurable-cache tuning with a unified second-level cache. In ISLPED '05: Proceedings of the 2005 international symposium on Low power electronics and design, pages 323--326, 2005.

Digital Library

[9]

A. Gordon-Ross, P. Viana, F. Vahid, W. Najjar, and E. Barros. A one-shot configurable-cache tuner for improved energy and performance. In Proceedings of the Design, Automation and Test in Europe(DATE), New York, NY, USA, 2007. ACM Press.

Digital Library

[10]

S. Gosh, M. Martonosi, and S. Malik. Cache miss equations: An analytical representation of cache misses. In In the Proceedings of the Workshop on Interaction between Compilers and Computer Architectures (HPCA-3), 1997.

Digital Library

[11]

K. Grimsrud, J. Archibald, R. Frost, and B. Nelson. Locality as a visualization tool. IEEE Trans. Comput., 45(11):1319--1326, 1996.

Digital Library

[12]

M.D. Hill and A.J. Smith. Evaluating associativity in cpu caches. IEEE Trans. Comput., 38(12):1612--1630, 1989.

Digital Library

[13]

A. Janapsatya, A. Ignjatovi´c, and S. Parameswaran. Finding optimal l1 cache configuration for embedded systems. In ASP-DAC '06: Proceedings of the 2006 conference on Asia South Pacific design automation, pages 796--801, Piscataway, NJ, USA, 2006. IEEE Press.

Digital Library

[14]

A. Malik, B. Moyer, and D. Cermak. A low power unified cache architecture providing power and performance flexibility. In ISLPED'00: Proceedings of the 2000 international symposium on Low power electronics and design, pages 241--243, 2000.

Digital Library

[15]

R.L. Mattson, J. Gecsei, D.R. Slutz, and I.L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78--117, 1970.

Digital Library

[16]

P.R. Panda, A. Nicolau, and N. Dutt. Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration. Kluwer Academic Publishers, Norwell, MA, USA, 1998.

Digital Library

[17]

S. Segars. Low-power design techniques for microprocessors. In ISSCC'01: International Solid State Circuits Conference, San Francisco, CA, USA, 2001. IEEE Computer Society.

[18]

R. Sugumar and S. Abraham. Efficient simulation of multiple cache configurations using binomial trees. In Technical Report CSE-TR-111-91., 1991.

[19]

C. Zhang, F. Vahid, and R. Lysecky. A self-tuning cache architecture for embedded systems. In Proc. of the Design, Automation and Test in Europe(DATE'04), February 2004.

Digital Library

[20]

C. Zhang, F. Vahid, and W. Najjar. A highly configurable cache for low energy embedded systems. Trans. on Embedded Computing Sys., 4(2):363--387, 2005.

Digital Library

Cited By

Liu JZhou YZhang D(2016)TranSimIEEE Transactions on Computers10.1109/TC.2016.251990165:10(3171-3183)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TC.2016.2519901
Upadhyay BSudarshan T(2016)Design space exploration of cache memory — A survey2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT)10.1109/ICEEOT.2016.7755102(2294-2297)Online publication date: Mar-2016
https://doi.org/10.1109/ICEEOT.2016.7755102
dos Santos MBarros EAziz A(2016)A MPSoC cache design space exploration approach based on ABC algorithm to optimize energy consumption and performance2016 IEEE 27th International Conference on Application-specific Systems, Architectures and Processors (ASAP)10.1109/ASAP.2016.7760785(153-158)Online publication date: Jul-2016
https://doi.org/10.1109/ASAP.2016.7760785
Show More Cited By

Index Terms

A table-based method for single-pass cache optimization
1. Hardware
  1. Hardware validation

Recommendations

Configurable cache subsetting for fast cache tuning
DAC '06: Proceedings of the 43rd annual Design Automation Conference

Numerous variations of configurable caches, having variable parameters like total size, line size, and associativity, have been proposed in commercial microprocessors in recent years. Tuning a configurable cache to a target application has been shown to ...
Combining code reordering and cache configuration

The instruction cache is a popular optimization target due to the cache's high impact on system performance and power and because of the cache's predictable temporal and spatial locality. This article is an in depth study on the interaction of code ...
Fast configurable-cache tuning with a unified second-level cache

Tuning a configurable cache subsystem to an application can greatly reduce memory hierarchy energy consumption. Previous tuning methods use a level one configurable cache only, or a second level with separate instruction and data configurable caches. We ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GLSVLSI '08: Proceedings of the 18th ACM Great Lakes symposium on VLSI

May 2008

480 pages

ISBN:9781595939999

DOI:10.1145/1366110

General Chairs:
Vijay Narayanan
Penn State University
,
Zhiyuan Yan
Lehigh University
,
Program Chairs:
Enrico Macii
Politecnico di Torino
,
Sanjukta Bhanja
University of South Florida

Copyright © 2008 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: 04 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GLSVLSI08

Sponsor:

GLSVLSI08: Great Lakes Symposium on VLSI 2008

May 4 - 6, 2008

Florida, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25

Sponsor:
sigda

Great Lakes Symposium on VLSI 2025

June 30 - July 2, 2025

New Orleans , LA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
211
Total Downloads

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

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu JZhou YZhang D(2016)TranSimIEEE Transactions on Computers10.1109/TC.2016.251990165:10(3171-3183)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1109/TC.2016.2519901
Upadhyay BSudarshan T(2016)Design space exploration of cache memory — A survey2016 International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT)10.1109/ICEEOT.2016.7755102(2294-2297)Online publication date: Mar-2016
https://doi.org/10.1109/ICEEOT.2016.7755102
dos Santos MBarros EAziz A(2016)A MPSoC cache design space exploration approach based on ABC algorithm to optimize energy consumption and performance2016 IEEE 27th International Conference on Application-specific Systems, Architectures and Processors (ASAP)10.1109/ASAP.2016.7760785(153-158)Online publication date: Jul-2016
https://doi.org/10.1109/ASAP.2016.7760785
Waldspurger CPark NGarthwaite AAhmad ISchindler JZadok E(2015)Efficient MRC construction with SHARDSProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750490(95-110)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.5555/2750482.2750490
Nawinne ISchneider JJavaid HParameswaran SFettweis GNebel W(2014)Hardware-based fast exploration of cache hierarchies in application specific MPSoCsProceedings of the conference on Design, Automation & Test in Europe10.5555/2616606.2617020(1-6)Online publication date: 24-Mar-2014
https://dl.acm.org/doi/10.5555/2616606.2617020
Zang WGordon-Ross A(2013)A survey on cache tuning from a power/energy perspectiveACM Computing Surveys10.1145/2480741.248074945:3(1-49)Online publication date: 3-Jul-2013
https://dl.acm.org/doi/10.1145/2480741.2480749
Zang WGordon-Ross A(2013)T-SPaCS—A Two-Level Single-Pass Cache Simulation MethodologyIEEE Transactions on Computers10.1109/TC.2011.19462:2(390-403)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1109/TC.2011.194
Nawinne IParameswaran S(2013)A survey on exact cache design space exploration methodologies for application specific SoC memory hierarchies2013 IEEE 8th International Conference on Industrial and Information Systems10.1109/ICIInfS.2013.6732005(332-337)Online publication date: Dec-2013
https://doi.org/10.1109/ICIInfS.2013.6732005
Peng MLiu X(2013)Adaptive Rapid Reconfigurable Algorithm for Low Power CacheProceedings of the 2013 International Conference on Computational and Information Sciences10.1109/ICCIS.2013.61(203-206)Online publication date: 21-Jun-2013
https://dl.acm.org/doi/10.1109/ICCIS.2013.61
Wu JLing MZhang YMei CWang H(2013)A novel energy-oriented reconfigurable on-chip unified memory architecture based on Cache Behavior Phase Graph2013 IEEE 10th International Conference on ASIC10.1109/ASICON.2013.6812000(1-5)Online publication date: Oct-2013
https://doi.org/10.1109/ASICON.2013.6812000
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.

Figures

Tables

Media

View Table of Conten