Document Open Access Logo

The Semantic Foundations and a Landscape of Cache-Persistence Analyses

Author Jan Reineke

PDF
Thumbnail PDF

File

LITES-v005-i001-a003.pdf
  • Filesize: 0.87 MB
  • 52 pages

Document Identifiers

Author Details

Jan Reineke
  • Saarland University, Saarland Informatics Campus Saarbrücken

Cite AsGet BibTex

Jan Reineke. The Semantic Foundations and a Landscape of Cache-Persistence Analyses. In LITES, Volume 5, Issue 1 (2018). Leibniz Transactions on Embedded Systems, Volume 5, Issue 1, pp. 03:1-03:52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LITES-v005-i001-a003

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.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time system architecture
  • Theory of computation → Caching and paging algorithms
  • Hardware → Safety critical systems
Keywords
  • caches
  • persistence analysis
  • WCET analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. Christoph Cullmann. Cache persistence analysis for embedded real-time systems. PhD thesis, Saarland University, Saarbrücken, Germany, 2013. URL: http://d-nb.info/1052779867.
  8. 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
  9. B. A. Davey and H. A. Priestley. Introduction to Lattices and Order. Cambridge University Press, second edition, 2002. Google Scholar
  10. 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
  11. Christian Ferdinand. Cache behavior prediction for real-time systems. PhD thesis, Saarland University, Saarbrücken, Germany, 1997. URL: http://d-nb.info/953983706.
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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.
  21. 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
  22. Kartik Nagar. Cache analysis for multi-level data caches. Master's thesis, Indian Institute of Science, Bangalore, India, 2012. Google Scholar
  23. 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
  24. Flemming Nielson, Hanne R. Nielson, and Chris Hankin. Principles of Program Analysis. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 1999. Google Scholar
  25. 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
  26. 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.
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact