research-article

Relative competitive analysis of cache replacement policies

Authors:

Daniel GrundAuthors Info & Claims

LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems

Pages 51 - 60

https://doi.org/10.1145/1375657.1375665

Published: 12 June 2008 Publication History

Abstract

Caches are commonly employed to hide the latency gap between memory and the CPU by exploiting locality in memory accesses. On today's architectures a cache miss may cost several hundred CPU cycles.

In order to fulfill stringent performance requirements, caches are now also used in hard real-time systems. In such systems, upper and sometimes also lower bounds on the execution times of a task have to be computed. To obtain tight bounds, timing analyses must take into account the cache architecture. However, developing cache analyses -- analyses that determine whether a memory access is a hit or a miss -- is a difficult problem for some cache architectures.

In this paper, we present a tool to automatically compute relative competitive ratios for a large class of replacement policies, including LRU, FIFO, and PLRU. Relative competitive ratios bound the performance of one policy relative to the performance of another policy.

These performance relations allow us to use cache-performance predictions for one policy to compute predictions for another, including policies that could previously not be dealt with.

References

[1]

Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. phNetwork flows: theory, algorithms, and applications. Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1993.

Digital Library

[2]

Hussein Al-Zoubi, Aleksandar Milenkovic, and Milena Milenkovic. Performance evaluation of cache replacement policies for the SPEC CPU2000 benchmark suite. In phACM-SE 42: Proceedings of the 42nd Annual Southeast Regional Conference, pages 267--272, New York, NY, USA, 2004.

Digital Library

[3]

James Aspnes and Orli Waarts. Modular competitiveness for distributed algorithms. In phSTOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 237--246, New York, NY, USA, 1996. ACM Press. ISBN 0-89791-785-5.

Digital Library

[4]

L. Belady. A study of replacement algorithms for a virtual storage computer. phIBM Systems Journal, 5: 78--101, 1966.

[5]

Siddhartha Chatterjee, Erin Parker, Philip J. Hanlon, and Alvin R. Lebeck. Exact analysis of the cache behavior of nested loops. In phPLDI '01: Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, pages 286--297, New York, NY, USA, 2001. ACM Press.

Digital Library

[6]

Christian Ferdinand and Reinhard Wilhelm. Efficient and precise cache behavior prediction for real-time systems. phReal-Time Systems, 17 (2-3): 131--181, 1999.

Digital Library

[7]

Christian Ferdinand, Florian Martin, and Reinhard Wilhelm. Applying compiler techniques to cache behavior prediction. In phProceedings of the ACM SIGPLAN Workshop on Languages, Compilers and Tools for Real-Time Systems, pages 37--46, Las Vegas, Nevada, June 1997.

[8]

Somnath Ghosh, Margaret Martonosi, and Sharad Malik. Precise miss analysis for program transformations with caches of arbitrary associativity. In phASPLOS-VIII: Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, pages 228--239, New York, NY, USA, 1998. ACM Press.

Digital Library

[9]

Reinhold Heckmann, Marc Langenbach, Stephan Thesing, and Reinhard Wilhelm. The influence of processor architecture on the design and the results of WCET tools. phProceedings of the IEEE, 91 (7), 2003.

[10]

A. Hergenhan and W. Rosenstiel. Static timing analysis of embedded software on advanced processor architectures. In phDATE '00, pages 552--559, New York, NY, USA, 2000. ACM Press.

Digital Library

[11]

Elias Koutsoupias and Christos H. Papadimitriou. Beyond competitive analysis. In phIEEE Symposium on Foundations of Computer Science, pages 394--400, 1994.

Digital Library

[12]

E.L. Lawler. Optimal cycles in doubly weighted linear graphs. In phInt'l Symp. Theory of Graphs, pages 209--213, 1966.

[13]

Jan Reineke and Daniel Grund. Relative competitiveness of cache replacement policies {extended abstract}. In phSIGMETRICS, 2008 (to appear).

Digital Library

[14]

Jan Reineke, Daniel Grund, Christoph Berg, and Reinhard Wilhelm. Timing predictability of cache replacement policies. phReal-Time Systems, 37 (2): 99--122, November 2007.

Digital Library

[15]

Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules. phCommun. ACM, 28 (2): 202--208, 1985.

Digital Library

[16]

Yannis Smaragdakis, Scott Kaplan, and Paul Wilson. The EELRU adaptive replacement algorithm. phPerform. Eval., 53 (2): 93--123, 2003.

Digital Library

[17]

Randall T. White, Christopher A. Healy, David B. Whalley, Frank Mueller, and Marion G. Harmon. Timing analysis for data caches and set-associative caches. In phRTAS '97, page 192, Washington, DC, USA, 1997. IEEE Computer Society.

Digital Library

Cited By

Hou IZhao TWang SChan KDressler Fauf der Heide F(2016)Asymptotically optimal algorithm for online reconfiguration of edge-cloudsProceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/2942358.2942363(291-300)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1145/2942358.2942363
Reineke JWilhelm R(2015)Static Timing Analysis --- What is Special?Essays Dedicated to Hanne Riis Nielson and Flemming Nielson on the Occasion of Their 60th Birthdays on Semantics, Logics, and Calculi - Volume 956010.1007/978-3-319-27810-0_4(74-87)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-27810-0_4
Ballabriga CChong LRoychoudhury A(2014)Cache-related preemption delay analysis for FIFO cachesACM SIGPLAN Notices10.1145/2666357.259781449:5(33-42)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2666357.2597814
Show More Cited By

Index Terms

Relative competitive analysis of cache replacement policies
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies
2. Hardware
  1. Hardware validation

Recommendations

Relative competitive analysis of cache replacement policies
LCTES '08

Caches are commonly employed to hide the latency gap between memory and the CPU by exploiting locality in memory accesses. On today's architectures a cache miss may cost several hundred CPU cycles.

In order to fulfill stringent performance requirements, ...
Sensitivity of cache replacement policies
Special section on ESTIMedia'12, LCTES'11, rigorous embedded systems design, and multiprocessor system-on-chip for cyber-physical systems

The sensitivity of a cache replacement policy expresses to what extent the execution history may influence the number of cache hits and misses during program execution. We present an algorithm to compute the sensitivity of a replacement policy. We have ...
Relative competitiveness of cache replacement policies
SIGMETRICS '08: Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '08: Proceedings of the 2008 ACM SIGPLAN-SIGBED conference on Languages, compilers, and tools for embedded systems

June 2008

180 pages

ISBN:9781605581040

DOI:10.1145/1375657

General Chair:
Krisztián Flautner
ARM Limited, UK
,
Program Chair:
John Regehr
University of Utah, USA

ACM SIGPLAN Notices Volume 43, Issue 7
LCTES '08
July 2008
167 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1379023
Issue’s Table of Contents

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: 12 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES08

Sponsor:

LCTES08: ACM SIGPLAN/SIGBED 2008 Conference on Languages, Compilers, and Tools for Embedded Systems

June 12 - 13, 2008

AZ, Tucson, USA

Acceptance Rates

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
562
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)3

Reflects downloads up to 23 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hou IZhao TWang SChan KDressler Fauf der Heide F(2016)Asymptotically optimal algorithm for online reconfiguration of edge-cloudsProceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing10.1145/2942358.2942363(291-300)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1145/2942358.2942363
Reineke JWilhelm R(2015)Static Timing Analysis --- What is Special?Essays Dedicated to Hanne Riis Nielson and Flemming Nielson on the Occasion of Their 60th Birthdays on Semantics, Logics, and Calculi - Volume 956010.1007/978-3-319-27810-0_4(74-87)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/978-3-319-27810-0_4
Ballabriga CChong LRoychoudhury A(2014)Cache-related preemption delay analysis for FIFO cachesACM SIGPLAN Notices10.1145/2666357.259781449:5(33-42)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2666357.2597814
Ballabriga CChong LRoychoudhury AZhang YKulkarni P(2014)Cache-related preemption delay analysis for FIFO cachesProceedings of the 2014 SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems10.1145/2597809.2597814(33-42)Online publication date: 12-Jun-2014
https://dl.acm.org/doi/10.1145/2597809.2597814
Guan NLv MYi WYu G(2014)WCET analysis with MRU cacheACM Transactions on Embedded Computing Systems10.1145/258465513:4s(1-26)Online publication date: 1-Apr-2014
https://dl.acm.org/doi/10.1145/2584655
Guan NYang XLv MYi WMacii E(2013)FIFO cache analysis for WCET estimationProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485362(296-301)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485362
Sen RWood D(2013)Reuse-based online models for cachesACM SIGMETRICS Performance Evaluation Review10.1145/2494232.246575641:1(279-292)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2494232.2465756
Sen RWood DHarchol-Balter MDouceur JXu J(2013)Reuse-based online models for cachesProceedings of the ACM SIGMETRICS/international conference on Measurement and modeling of computer systems10.1145/2465529.2465756(279-292)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1145/2465529.2465756
Reineke JGrund D(2013)Sensitivity of cache replacement policiesACM Transactions on Embedded Computing Systems10.1145/2435227.243523812:1s(1-18)Online publication date: 21-Mar-2013
https://dl.acm.org/doi/10.1145/2435227.2435238
Abel AReineke J(2013)Measurement-based modeling of the cache replacement policyProceedings of the 2013 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS.2013.6531080(65-74)Online publication date: 9-Apr-2013
https://dl.acm.org/doi/10.1109/RTAS.2013.6531080
Show More Cited By

View Options

Get Access

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