Document Open Access Logo

Write-Back Caches in WCET Analysis

Authors Tobias Blaß, Sebastian Hahn, Jan Reineke

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2017.26.pdf
  • Filesize: 0.76 MB
  • 22 pages

Document Identifiers

Author Details

Tobias Blaß
Sebastian Hahn
Jan Reineke

Cite As Get BibTex

Tobias Blaß, Sebastian Hahn, and Jan Reineke. Write-Back Caches in WCET Analysis. In 29th Euromicro Conference on Real-Time Systems (ECRTS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 76, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ECRTS.2017.26

Abstract

Write-back caches are a popular choice in embedded microprocessors as they promise higher performance than write-through caches. So far, however, their use in hard real-time systems has been prohibited by the lack of adequate worst-case execution time (WCET) analysis support.

In this paper, we introduce a new approach to statically analyze the behavior of write-back caches. Prior work took an "eviction-focussed perspective", answering for each potential cache miss: May this miss evict a dirty cache line and thus cause a write back? We complement this approach by exploring a "store-focussed perspective", answering for each store: May this store dirtify a clean cache line and thus cause a write back later on?

Experimental evaluation demonstrates substantial precision improvements when both perspectives are combined. For most benchmarks, write-back caches are then preferable to write-through caches in terms of the computed WCET bounds.

Subject Classification

Keywords
  • write-back caches
  • real-time systems
  • WCET analysis
  • cache analysis

Metrics

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

References

  1. Martin Alt, Christian Ferdinand, Florian Martin, and Reinhard Wilhelm. Cache behavior prediction by abstract interpretation. In Radhia Cousot and David A. Schmidt, editors, Static Analysis, Third International Symposium, SAS'96, Aachen, Germany, September 24-26, 1996, Proceedings, volume 1145 of Lecture Notes in Computer Science, pages 52-66. Springer, 1996. URL: http://dx.doi.org/10.1007/3-540-61739-6_33.
  2. Sebastian Altmeyer, Robert I. Davis, and Claire Maiza. Cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. In Proceedings of the 32nd IEEE Real-Time Systems Symposium, RTSS 2011, Vienna, Austria, November 29 - December 2, 2011, pages 261-271, 2011. URL: http://dx.doi.org/10.1109/RTSS.2011.31.
  3. ARM Limited. ARM946E-S Technical Reference Manual. Available at URL: http://infocenter.arm.com/help/topic/com.arm.doc.ddi0201d/DDI0201D_arm946es_r1p1_trm.pdf.
  4. José V. Busquets-Mataix, Juan José Serrano, Rafael Ors, Pedro J. Gil, and Andy J. Wellings. Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In Proceedings of the IEEE Real-Time Embedded Technology and Applications (RTAS), pages 204-212, June 1996. Google Scholar
  5. Christoph Cullmann. Cache persistence analysis: a novel approach - theory and practice. In Proceedings of the ACM SIGPLAN/SIGBED 2011 conference on Languages, compilers, and tools for embedded systems, LCTES 2011, Chicago, IL, USA, April 11-14, 2011, pages 121-130, 2011. URL: http://dx.doi.org/10.1145/1967677.1967695.
  6. Christoph Cullmann. Cache persistence analysis: Theory and practice. ACM Trans. Embed. Comput. Syst., 12(1s):40:1-40:25, March 2013. URL: http://dx.doi.org/10.1145/2435227.2435236.
  7. Robert I. Davis, Sebastian Altmeyer, and Jan Reineke. Analysis of write-back caches under fixed-priority preemptive and non-preemptive scheduling. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016, Brest, France, October 19-21, 2016, pages 309-318, 2016. URL: http://dx.doi.org/10.1145/2997465.2997476.
  8. Christian Ferdinand and Reinhard Wilhelm. Efficient and precise cache behavior prediction for real-time systems. Real-Time Systems, 17(2):131-181, 1999. URL: http://dx.doi.org/10.1023/A:1008186323068.
  9. Ricardo Bedin França, Denis Favre-Felix, Xavier Leroy, Marc Pantel, and Jean Souyris. Towards formally verified optimizing compilation in flight control software. In PPES 2011: Predictability and Performance in Embedded Systems, volume 18, pages 59-68. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2011. Google Scholar
  10. Freescale Semiconductor, Inc. MPC603e RISC Microprocessor User’s Manual. Available at URL: http://www.nxp.com/files/32bit/doc/ref_manual/MPC603EUM.pdf.
  11. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The Mälardalen WCET benchmarks - past, present and future. In Björn Lisper, editor, WCET2010, pages 137-147, Brussels, Belgium, July 2010. OCG. Google Scholar
  12. Sebastian Hahn and Daniel Grund. Relational cache analysis for static timing analysis. In 24th Euromicro Conference on Real-Time Systems, ECRTS 2012, Pisa, Italy, July 11-13, 2012, pages 102-111, 2012. URL: http://dx.doi.org/10.1109/ECRTS.2012.14.
  13. Sebastian Hahn, Michael Jacobs, and Jan Reineke. Enabling compositionality for multicore timing analysis. In Proceedings of the 24th International Conference on Real-Time Networks and Systems, RTNS 2016, Brest, France, October 19-21, 2016, pages 299-308, 2016. URL: http://dx.doi.org/10.1145/2997465.2997471.
  14. Sebastian Hahn, Jan Reineke, and Reinhard Wilhelm. Towards compositionality in execution time analysis: definition and challenges. SIGBED Review, 12(1):28-36, 2015. URL: http://dx.doi.org/10.1145/2752801.2752805.
  15. 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, 2011. URL: http://dx.doi.org/10.1109/RTAS.2011.27.
  16. Michael Jacobs, Sebastian Hahn, and Sebastian Hack. WCET analysis for multi-core processors with shared buses and event-driven bus arbitration. In Proceedings of the 23rd International Conference on Real Time Networks and Systems, RTNS 2015, Lille, France, November 4-6, 2015, pages 193-202, 2015. URL: http://dx.doi.org/10.1145/2834848.2834872.
  17. Norman P. Jouppi. Cache write policies and performance. In Alan Jay Smith, editor, Proceedings of the 20th Annual International Symposium on Computer Architecture. San Diego, CA, May 1993, pages 191-201. ACM, 1993. URL: http://dx.doi.org/10.1145/165123.165154.
  18. Daniel Kröning and Silvia M. Müller. The impact of write-back on the cache performance. In Proceedings of the IASTED International Conference on Applied Informatics, Innsbruck, pages 213-217. ACTA Press, 2000. Google Scholar
  19. Chang-Gun Lee, Joosun Hahn, Yang-Min Seo, Sang Lyul Min, Rhan Ha, Seongsoo Hong, Chang Yun Park, Minsuk Lee, and Chong Sang Kim. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Transactions on Computers, 47(6):700-713, 1998. Google Scholar
  20. Benjamin Lesage, Damien Hardy, and Isabelle Puaut. WCET analysis of multi-level set-associative data caches. In Niklas Holsti, editor, 9th Int'l Workshop on Worst-Case Execution Time Analysis, WCET 2009, Dublin, Ireland, July 1-3, 2009, volume 10 of OASICS. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2009. URL: http://www.dagstuhl.de/dagpub/978-3-939897-14-9, URL: http://dx.doi.org/10.4230/OASIcs.WCET.2009.2283.
  21. Thomas Lundqvist and Per Stenström. Timing anomalies in dynamically scheduled microprocessors. In Proceedings of the 20th IEEE Real-Time Systems Symposium, Phoenix, AZ, USA, December 1-3, 1999, pages 12-21, 1999. URL: http://dx.doi.org/10.1109/REAL.1999.818824.
  22. 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.
  23. Laurent Mauborgne and Xavier Rival. Trace partitioning in abstract interpretation based static analyzers. In Shmuel Sagiv, editor, 14th European Symposium on Programming (ESOP) 2005, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2005, Edinburgh, UK, April 4-8, 2005, Proceedings, volume 3444 of Lecture Notes in Computer Science, pages 5-20. Springer, 2005. URL: http://dx.doi.org/10.1007/978-3-540-31987-0_2.
  24. Micron Technology, Inc. Automotive DDR SDRAM MT46V32M8, MT46V16M16. Available at URL: https://www.micron.com/~/media/documents/products/data-sheet/dram/mobile-dram/low-power-dram/lpddr/256mb_x8x16_at_ddr_t66a.pdf.
  25. Jan Reineke, Björn Wachter, Stephan Thesing, Reinhard Wilhelm, Ilia Polian, Jochen Eisinger, and Bernd Becker. A definition and classification of timing anomalies. In 6th Int'l Workshop on Worst-Case Execution Time (WCET) Analysis, July 4, 2006, Dresden, Germany, 2006. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2006.671.
  26. SCADE suite. URL: http://www.esterel-technologies.com/products/scade-suite/.
  27. Tyler Sondag and Hridesh Rajan. A more precise abstract domain for multi-level caches for tighter WCET analysis. In Proceedings of the 31st IEEE Real-Time Systems Symposium, RTSS 2010, San Diego, California, USA, November 30 - December 3, 2010, pages 395-404, 2010. URL: http://dx.doi.org/10.1109/RTSS.2010.8.
  28. 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, 1997. URL: http://dx.doi.org/10.1109/RTTAS.1997.601358.
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 About DROPS Imprint Privacy Contact