The Semantic Foundations and a Landscape of Cache-Persistence Analyses

Jan Reineke

Abstract


We clarify the notion of cache persistence and contribute to the understanding of persistence analysis for caches with least-recently-used replacement.

To this end, we provide the first formal definition of persistence as a property of a trace semantics. Based on this trace semantics we introduce a semantics-based, i.e., abstract-interpretation-based persistence analysis framework.

We identify four basic persistence analyses and prove their correctness as instances of this analysis framework.

Combining these basic persistence analyses via two generic cooperation mechanisms yields a lattice of ten persistence analyses.

Notably, this lattice contains all persistence analyses previously described in the literature. As a consequence, we obtain uniform correctness proofs for all prior analyses and a precise understanding of how and why these analyses work, as well as how they relate to each other in terms of precision.


Keywords


caches, persistence analysis, WCET analysis

Full Text:

PDF

References


Robert D. Arnold, Frank Mueller, David B. Whalley, and Marion G. Harmon. Bounding worst-case instruction cache performance. In Proceedings of the 15th IEEE Real-Time Systems Symposium (RTSS '94), San Juan, Puerto Rico, December 7-9, 1994, pages 172-181. IEEE Computer Society, 1994. URL: http://dx.doi.org/10.1109/REAL.1994.342718

Clément Ballabriga and Hugues Cassé. Improving the first-miss computation in set-associative instruction caches. In 20th Euromicro Conference on Real-Time Systems, ECRTS 2008, 2-4 July 2008, Prague, Czech Republic, Proceedings, pages 341-350. IEEE Computer Society, 2008. URL: http://dx.doi.org/10.1109/ECRTS.2008.34

Patrick Cousot and Radhia Cousot. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Robert M. Graham, Michael A. Harrison, and Ravi Sethi, editors, Conference Record of the Fourth ACM Symposium on Principles of Programming Languages, Los Angeles, California, USA, January 1977, pages 238-252. ACM, 1977. URL: http://dx.doi.org/10.1145/512950.512973

Patrick Cousot and Radhia Cousot. Systematic design of program analysis frameworks. In Alfred V. Aho, Stephen N. Zilles, and Barry K. Rosen, editors, Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, San Antonio, Texas, USA, January 1979, pages 269-282. ACM Press, 1979. URL: http://dx.doi.org/10.1145/567752.567778

Patrick Cousot and Radhia Cousot. Basic concepts of abstract interpretation. In René Jacquart, editor, Building the Information Society, IFIP 18th World Computer Congress, Topical Sessions, 22-27 August 2004, Toulouse, France, volume 156 of IFIP, pages 359-366. Kluwer/Springer, 2004. URL: http://dx.doi.org/10.1007/978-1-4020-8157-6_27

Christoph Cullmann. Cache persistence analysis: a novel approachtheory and practice. In Jan Vitek and Bjorn De Sutter, editors, Proceedings of the ACMSIGPLAN/SIGBED 2011 conference on Languages, compilers, and tools for embedded systems, LCTES 2011, Chicago, IL, USA, April 11-14, 2011, pages 121-130. ACM, 2011. URL: http://dx.doi.org/10.1145/1967677.1967695

Christoph Cullmann. Cache persistence analysis for embedded real-time systems. PhD thesis, Saarland University, Saarbrücken, Germany, 2013. URL: http://d-nb.info/1052779867.

Christoph Cullmann. Cache persistence analysis: Theory and practice.ACM Trans. Embedded Comput. Syst., 12(1s):40:1-40:25, 2013. URL: http://dx.doi.org/10.1145/2435227.2435236

B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, second edition, 2002.

Goran Doychev, Boris Köpf, Laurent Mauborgne, and Jan Reineke. Cacheaudit: A tool for the static analysis of cache side channels.ACM Trans. Inf. Syst. Secur., 18(1):4:1-4:32, 2015. URL: http://dx.doi.org/10.1145/2756550

Christian Ferdinand. Cache behavior prediction for real-time systems. PhD thesis, Saarland University, Saarbrücken, Germany, 1997. URL: http://d-nb.info/953983706.

Christian Ferdinand and Reinhard Wilhelm. Efficient and precise cache behavior prediction for real-time systems. Real-Time Systems, 17(2-3):131-181, 1999. URL: http://dx.doi.org/10.1023/A:1008186323068

Daniel Grund and Jan Reineke. Precise and efficient fifo-replacement analysis based on static phase detection. In 22nd Euromicro Conference on Real-Time Systems, ECRTS 2010, Brussels, Belgium, July 6-9, 2010, pages 155-164. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/ECRTS.2010.8

Daniel Grund and Jan Reineke. Toward precise PLRU cache analysis. In Björn Lisper, editor, 10th International Workshop on Worst-Case Execution Time Analysis, WCET 2010, July 6, 2010, Brussels, Belgium, volume 15 of OASICS, pages 23-35. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2010. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2010.23

Nan Guan, Mingsong Lv, Wang Yi, and Ge Yu.WCET analysis with MRU cache: Challenging LRU for predictability.ACM Trans. Embedded Comput. Syst., 13(4s):123:1-123:26, 2014. URL: http://dx.doi.org/10.1145/2584655

Nan Guan, Xinping Yang, Mingsong Lv, and Wang Yi.FIFO cache analysis for WCET estimation: a quantitative approach. In Enrico Macii, editor, Design, Automation and Test in Europe, DATE 13, Grenoble, France, March 18-22, 2013, pages 296-301. EDA Consortium San Jose, CA, USA / ACMDL, 2013. URL: http://dx.doi.org/10.7873/DATE.2013.073

Bach Khoa Huynh, Lei Ju, and Abhik Roychoudhury. Scope-aware data cache analysis for WCET estimation. In 17th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2011, Chicago, Illinois, USA, 11-14 April 2011, pages 203-212. IEEE Computer Society, 2011. URL: http://dx.doi.org/10.1109/RTAS.2011.27

Gary A. Kildall. A unified approach to global program optimization. In Patrick C. Fischer and Jeffrey D. Ullman, editors, Conference Record of the ACM Symposium on Principles of Programming Languages, Boston, Massachusetts, USA, October 1973, pages 194-206. ACM Press, 1973. URL: http://dx.doi.org/10.1145/512927.512945

Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi. A survey on static cache analysis for real-time systems.LITES, 3(1):05:1-05:48, 2016. URL: http://dx.doi.org/10.4230/LITES-v003-i001-a005

Frank Mueller. Static cache simulation and its applications. PhD thesis, Florida State University, Tallahassee, United States, 1994. URL: http://www.cs.fsu.edu/ whalley/papers/mueller_diss94.pdf.

Frank Müller. Timing analysis for instruction caches. Real-Time Systems, 18(2/3):217-247, 2000. URL: http://dx.doi.org/10.1023/A:1008145215849

Kartik Nagar. Cache analysis for multi-level data caches. Master's thesis, Indian Institute of Science, Bangalore, India, 2012.

Kartik Nagar and Y. N. Srikant. Interdependent cache analyses for better precision and safety. In Tenth ACM/IEEE International Conference on Formal Methods and Models for Codesign, MEMCODE 2012, Arlington, VA, USA, July 16-17, 2012, pages 99-108. IEEE, 2012. URL: http://dx.doi.org/10.1109/MEMCOD.2012.6292306

Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Principles of Program Analysis. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1999.

Jens Palsberg and Zhendong Su, editors. Static Analysis, 16th International Symposium, SAS 2009, Los Angeles, CA, USA, August 9-11, 2009. Proceedings, volume 5673 of Lecture Notes in Computer Science. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-03237-0

Jan Reineke. Caches in WCET Analysis. PhD thesis, Universität des Saarlandes, November 2008. URL: http://rw4.cs.uni-saarland.de/ reineke/publications/DissertationCachesInWCETAnalysis.pdf.

Jan Reineke and Daniel Grund. Relative competitive analysis of cache replacement policies. In Krisztián Flautner and John Regehr, editors, Proceedings of the 2008 ACMSIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES'08), Tucson, AZ, USA, June 12-13, 2008, pages 51-60. ACM, 2008. URL: http://dx.doi.org/10.1145/1375657.1375665

Xavier Rival and Laurent Mauborgne. The trace partitioning abstract domain.ACM Trans. Program. Lang. Syst., 29(5):26, 2007. URL: http://dx.doi.org/10.1145/1275497.1275501

Helmut Seidl, Reinhard Wilhelm, and Sebastian Hack. Compiler Design - Analysis and Transformation. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-17548-0

Valentin Touzeau, Claire Maïza, David Monniaux, and Jan Reineke. Ascertaining uncertainty for efficient exact cache analysis. In Rupak Majumdar and Viktor Kuncak, editors, Computer Aided Verification - 29th International Conference, CAV 2017, Heidelberg, Germany, July 24-28, 2017, Proceedings, Part II, volume 10427 of Lecture Notes in Computer Science, pages 22-40. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-63390-9_2

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 3rd IEEE Real-Time Technology and Applications Symposium, RTAS '97, Montreal, Canada, June 9-11, 1997, pages 192-202. IEEE Computer Society, 1997. URL: http://dx.doi.org/10.1109/RTTAS.1997.601358

Zhenkai Zhang and Xenofon D. Koutsoukos. Improving the precision of abstract interpretation based cache persistence analysis. In Sam H. Noh, Sebastian Fischmeister, and Jason Xue, editors, Proceedings of the 16th ACMSIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, LCTES 2015, CD-ROM, Portland, OR, USA, June 18 - 19, 2015, pages 10:1-10:10. ACM, 2015. URL: http://dx.doi.org/10.1145/2670529.2754967




DOI: https://doi.org/10.4230/LITES-v005-i001-a003

URN (PDF): http://nbn-resolving.de/urn:nbn:de:0030-lites-v005-i001-a003-pdf4

Copyright (c) 2018 Jan Reineke

Creative Commons License CC BY
This work is licensed under a Creative Commons Attribution 3.0 Germany License (CC BY 3.0 DE).

License URL: http://creativecommons.org/licenses/by/3.0/de/deed.en
To make this site work properly, we sometimes place small data files called cookies on your device. Cookies are only here to manage user sessions. Cookies aren’t required for simply visiting the site and read content.
OK




Published by the European Design and Automation Association (EDAA) \ EMbedded Systems Special Interest Group (EMSIG) and Schloss Dagstuhl -- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing. | Imprint | Data Privacy Policy