research-article

Static Probabilistic Timing Analysis of Random Replacement Caches using Lossy Compression

Authors:

Benjamin Lesage,

Robert I. DavisAuthors Info & Claims

RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and Systems

Pages 289 - 298

https://doi.org/10.1145/2659787.2659809

Published: 08 October 2014 Publication History

Abstract

The analysis of random replacement caches is an area that has recently attracted considerable attention in the field of probabilistic real-time systems. A major problem with performing static analysis on such a cache is that the relatively large number of successor states on a cache miss (equal to the cache associativity) renders approaches such as Collecting Semantics intractable. Other approaches must contend with non-trivial behaviours, such as the non-independence of accesses to the cache, which tends to lead to overly pessimistic or computationally expensive analyses.

Utilising techniques from the field of Lossy Compression, where compactly representing large volumes of data without losing valuable data is the norm, this paper outlines a technique for applying compression to the Collecting Semantics of a Random Replacement Cache. This yields a Must and May analysis. Experimental evaluation shows that, with appropriate parameters, this technique is more accurate and significantly faster than current state-of-the-art techniques.

References

[1]

S. Edgar, "Estimation of worst-case execution time using statistical analysis," Ph.D. dissertation, University of York, 2002.

[2]

L. David and I. Puaut, "Static determination of probabilistic execution times," in Proceedings. 16th Euromicro Conference on Real-Time Systems (ECRTS), June 2004, pp. 223--230.

Digital Library

[3]

F. Cazorla, E. Quiñones, T. Vardanega, L. Cucu, B. Triquet, G. Bernat, E. Berger, J. Abella, F. Wartel, M. Houston, L. Santinelli, L. Kosmidis, C. Lo, and D. Maxim, "Proartis: Probabilistically analysable real-time systems," Transactions on Embedded Computing Systems, 2012.

Digital Library

[4]

L. Cucu-Grosjean, L. Santinelli, M. Houston, C. Lo, T. Vardanega, L. Kosmidis, J. Abella, E. Mezzetti, E. Quiñones, and F. J. Cazorla, "Measurement-based probabilistic timing analysis for multi-path programs." in ECRTS, R. Davis, Ed. IEEE Computer Society, 2012, pp. 91--101.

Digital Library

[5]

R. I. Davis, L. Santinelli, S. Altmeyer, C. Maiza, and L. Cucu-Grosjean, "Analysis of probabilistic cache related pre-emption delays," in 25th Euromicro Conference on Real-Time Systems (ECRTS). IEEE, 2013, pp. 168--179.

Digital Library

[6]

S. Altmeyer and R. I. Davis, "On the correctness, optimality and precision of static probabilistic timing analysis," in 17th Design, Automation and Test in Europe Conference (DATE). EDAA, 2014.

Digital Library

[7]

J. Watkinson, Compression in Video and Audio. Focal Press, 1995.

Digital Library

[8]

K. S. G. Brandenburg, "ISO/MPEG-1 audio: A generic standard for coding of high-quality digital audio," J. Audio Engineering Soc, vol. 42, no. 10, pp. 780--792, 1994.

[9]

D. Griffin, B. Lesage, A. Burns, and R. I. Davis, "Lossy compression for worst-case execution time analysis of PLRU caches," in RTNS '14: Proceedings of the 22nd International Conference on Real-Time and Network Systems. Versailles, France: ACM, New York, NY, USA, 2014.

Digital Library

[10]

P. Cousot and R. Cousot, "Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints," in Conference Record of the Fourth Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Los Angeles, California: ACM Press, New York, NY, 1977, pp. 238--252.

Digital Library

[11]

F. Mueller, "Timing analysis for instruction caches," Real-Time Systems, vol. 18, pp. 217--247, May 2000.

Digital Library

[12]

Y. Liang and T. Mitra, "Cache modeling in probabilistic execution time analysis," in Proceedings of the 45th Annual Design Automation Conference, ser. DAC '08. New York, NY, USA: ACM, 2008, pp. 319--324.

Digital Library

[13]

L. Cucu-Grosjean, "Independance - a misunderstood property of and for probabilistic real-time systems," in Alan Burns 60th Anniversary, N. Audsley and S. Baruah, Eds., Mar. 2013.

[14]

T. Lundqvist and P. Stenström, "Timing anomalies in dynamically scheduled microprocessors," in RTSS '99: Proceedings of the 20th IEEE Real-Time Systems Symposium. Washington, DC, USA: IEEE Computer Society, 1999, pp. 12--21.

Digital Library

[15]

D. Grund and J. Reineke, "Toward precise PLRU cache analysis," in Proceedings of 10th International Workshop on Worst-Case Execution Time (WCET) Analysis, B. Lisper, Ed. Austrian Computer Society, July 2010, pp. 28--39.

[16]

Contributors, "Maladärlen WCET benchmarks," http://www.mrtc.mdh.se/projects/wcet/, accessed on 1st September 2013.

Cited By

Dai XZhao SBate IBurns AGuo XChang W(2021)Brief Industry Paper: Digital Twin for Dependable Multi-Core Real-Time Systems — Requirements and Open Challenges2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS52030.2021.00057(481-484)Online publication date: May-2021
https://doi.org/10.1109/RTAS52030.2021.00057
Cazorla FKosmidis LMezzetti EHernandez CAbella JVardanega T(2019)Probabilistic Worst-Case Timing AnalysisACM Computing Surveys10.1145/330128352:1(1-35)Online publication date: 13-Feb-2019
https://dl.acm.org/doi/10.1145/3301283
Chen CPanerati JLi MBeltrame G(2019)Probabilistic timing analysis of time-randomised caches with fault detection mechanismsIET Computers & Digital Techniques10.1049/iet-cdt.2018.5043Online publication date: 7-Jan-2019
https://doi.org/10.1049/iet-cdt.2018.5043
Show More Cited By

Index Terms

Recommendations

Static probabilistic timing analysis for real-time systems using random replacement caches

In this paper, we investigate static probabilistic timing analysis (SPTA) for single processor real-time systems that use a cache with an evict-on-miss random replacement policy. We show that previously published formulae for the probability of a cache ...
Introducing hierarchy-awareness in replacement and bypass algorithms for last-level caches
PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniques

The replacement policies for the last-level caches (LLCs) are usually designed based on the access information available locally at the LLC. These policies are inherently sub-optimal due to lack of information about the activities in the inner-levels of ...
Opportunistic compression for direct-mapped DRAM caches
MEMSYS '18: Proceedings of the International Symposium on Memory Systems

Large off-chip DRAM caches offer performance and bandwidth improvements for many systems by bridging the gap between on-chip last level caches and off-chip memories. To avoid the high hit latency resulting from serial DRAM accesses for tags and data, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

RTNS '14: Proceedings of the 22nd International Conference on Real-Time Networks and Systems

October 2014

335 pages

ISBN:9781450327275

DOI:10.1145/2659787

General Chairs:
Mathieu Jan
CEA LIST, Gif-sur-Yvette, France
,
Belgacem Ben Hedia
CEA LIST, Gif-sur-Yvette, France
,
Program Chairs:
Joël Goossens
Université Libre de Bruxelles, Belgium
,
Claire Maiza
Grenoble INP / Verimag, France

Copyright © 2014 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 the author(s) 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].

In-Cooperation

CEA: Commissariat à l'énergie atomique et aux énergies alternatives
GDR ASR: GDR Architecture, Systèmes et Réseaux

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 October 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

RTNS '14

RTNS '14: 22nd International Conference on Real-Time Networks and Systems

October 8 - 10, 2014

Versaille, France

Acceptance Rates

Overall Acceptance Rate 119 of 255 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
91
Total Downloads

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

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dai XZhao SBate IBurns AGuo XChang W(2021)Brief Industry Paper: Digital Twin for Dependable Multi-Core Real-Time Systems — Requirements and Open Challenges2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS52030.2021.00057(481-484)Online publication date: May-2021
https://doi.org/10.1109/RTAS52030.2021.00057
Cazorla FKosmidis LMezzetti EHernandez CAbella JVardanega T(2019)Probabilistic Worst-Case Timing AnalysisACM Computing Surveys10.1145/330128352:1(1-35)Online publication date: 13-Feb-2019
https://dl.acm.org/doi/10.1145/3301283
Chen CPanerati JLi MBeltrame G(2019)Probabilistic timing analysis of time-randomised caches with fault detection mechanismsIET Computers & Digital Techniques10.1049/iet-cdt.2018.5043Online publication date: 7-Jan-2019
https://doi.org/10.1049/iet-cdt.2018.5043
Lesage BGriffin DAltmeyer SCucu-Grosjean LDavis R(2018)On the analysis of random replacement caches using static probabilistic timing methods for multi-path programsReal-Time Systems10.1007/s11241-017-9295-254:2(307-388)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11241-017-9295-2
Maxim DDavis RCucu-Grosjean LEaswaran ABini EPagetti C(2017)Probabilistic analysis for mixed criticality systems using fixed priority preemptive schedulingProceedings of the 25th International Conference on Real-Time Networks and Systems10.1145/3139258.3139276(237-246)Online publication date: 4-Oct-2017
https://dl.acm.org/doi/10.1145/3139258.3139276
Chen CBeltrame G(2017)An Adaptive Markov Model for the Timing Analysis of Probabilistic CachesACM Transactions on Design Automation of Electronic Systems10.1145/312387723:1(1-24)Online publication date: 31-Aug-2017
https://dl.acm.org/doi/10.1145/3123877
Chen CPanerati JHafnaoui IBeltrame G(2017)Static probabilistic timing analysis with a permanent fault detection mechanism2017 12th IEEE International Symposium on Industrial Embedded Systems (SIES)10.1109/SIES.2017.7993373(1-10)Online publication date: Jun-2017
https://doi.org/10.1109/SIES.2017.7993373
Chen CSantinelli LHugues JBeltrame G(2016)Static probabilistic timing analysis in presence of faults2016 11th IEEE Symposium on Industrial Embedded Systems (SIES)10.1109/SIES.2016.7509422(1-10)Online publication date: May-2016
https://doi.org/10.1109/SIES.2016.7509422
Chen CPanerati JBeltrame G(2016)Effects of online fault detection mechanisms on Probabilistic Timing Analysis2016 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems (DFT)10.1109/DFT.2016.7684067(41-46)Online publication date: Sep-2016
https://doi.org/10.1109/DFT.2016.7684067
Griffin DLesage BBate ISoboczenski FDavis RForget J(2015)Modelling fault dependencies when execution time budgets are exceededProceedings of the 23rd International Conference on Real Time and Networks Systems10.1145/2834848.2834870(65-74)Online publication date: 4-Nov-2015
https://dl.acm.org/doi/10.1145/2834848.2834870
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