Document Open Access Logo

Impact of DM-LRU on WCET: A Static Analysis Approach

Authors Renato Mancuso, Heechul Yun, Isabelle Puaut

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2019.17.pdf
  • Filesize: 0.99 MB
  • 25 pages

Document Identifiers

Author Details

Renato Mancuso
  • Boston University, MA, USA
Heechul Yun
  • University of Kansas, Lawrence, KS, USA
Isabelle Puaut
  • University of Rennes 1/IRISA, France

Funding

This research is supported in part by NSF CNS 1718880. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the NSF.

Acknowledgements

We are especially grateful to Daniel Grund for making his research thesis [Grund, 2012] promptly available to us.

Cite As Get BibTex

Renato Mancuso, Heechul Yun, and Isabelle Puaut. Impact of DM-LRU on WCET: A Static Analysis Approach. In 31st Euromicro Conference on Real-Time Systems (ECRTS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 133, pp. 17:1-17:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ECRTS.2019.17

Abstract

Cache memories in modern embedded processors are known to improve average memory access performance. Unfortunately, they are also known to represent a major source of unpredictability for hard real-time workload. One of the main limitations of typical caches is that content selection and replacement is entirely performed in hardware. As such, it is hard to control the cache behavior in software to favor caching of blocks that are known to have an impact on an application’s worst-case execution time (WCET).
In this paper, we consider a cache replacement policy, namely DM-LRU, that allows system designers to prioritize caching of memory blocks that are known to have an important impact on an application’s WCET. Considering a single-core, single-level cache hierarchy, we describe an abstract interpretation-based timing analysis for DM-LRU. We implement the proposed analysis in a self-contained toolkit and study its qualitative properties on a set of representative benchmarks. Apart from being useful to compute the WCET when DM-LRU or similar policies are used, the proposed analysis can allow designers to perform WCET impact-aware selection of content to be retained in cache.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
  • Theory of computation → Caching and paging algorithms
Keywords
  • real-time
  • static cache analysis
  • abstract interpretation
  • LRU
  • deterministic memory
  • static cache locking
  • dynamic cache locking
  • cache profiling
  • WCET 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 Proceedings of the Third International Symposium on Static Analysis, SAS '96, pages 52-66, Berlin, Heidelberg, 1996. Springer-Verlag. Google Scholar
  2. ARM. PL310 Cache Controller Technical Reference Manual, Rev: r0p0, 2007. Google Scholar
  3. R. Banakar, S. Steinke, B. Lee, M. Balakrishnan, and P. Marwedel. Scratchpad memory: design alternative for cache on-chip memory in embedded systems. In Int. Symp. Hardware/Software Codesign (CODES+ISSS), pages 73-78. ACM, 2002. Google Scholar
  4. Alex Bradbury, Gavin Ferris, and Robert Mullins. Tagged memory and minion cores in the lowRISC SoC. Memo, University of Cambridge, 2014. Google Scholar
  5. Marti Campoy, A Perles Ivars, and JV Busquets-Mataix. Static use of locking caches in multitask preemptive real-time systems. In Real-Time Embedded Systems Workshop (Satellite of the IEEE Real-Time Systems Symposium), pages 1-6, 2001. Google Scholar
  6. Shuo Chen, Jun Xu, Nithin Nakka, Zbigniew Kalbarczyk, and Ravishankar K Iyer. Defeating memory corruption attacks via pointer taintedness detection. In Dependable Systems and Networks (DSN), pages 378-387. IEEE, 2005. Google Scholar
  7. NVIDIA Corp. Variable SMP – A Multi-Core CPU Architecture for Low Power and High Performance. Technical report, Nvidia, 2011. Google Scholar
  8. Christoph Cullmann. Cache Persistence Analysis: Theory and Practice. ACM Trans. Embed. Comput. Syst., 12(1s):40:1-40:25, March 2013. Google Scholar
  9. Jean-Francois Deverge and Isabelle Puaut. WCET-directed dynamic scratchpad memory allocation of data. In Euromicro Conference on Real-Time Systems (ECRTS), pages 179-190. IEEE, 2007. Google Scholar
  10. Farzad Farshchi, Prathap Kumar Valsan, Renato Mancuso, and Heechul Yun. Deterministic Memory Abstraction and Supporting Multicore System Architecture. In Euromicro Conf. Real-Time Syst. (ECRTS). IEEE, 2018. Google Scholar
  11. Christian Ferdinand, Florian Martin, Reinhard Wilhelm, and Martin Alt. Cache Behavior Prediction by Abstract Interpretation. Sci. Comput. Program., 35(2-3):163-189, November 1999. Google Scholar
  12. Christian Ferdinand and Reinhard Wilhelm. Efficient and Precise Cache Behavior Prediction for Real-TimeSystems. Real-Time Syst., 17(2-3):131-181, December 1999. Google Scholar
  13. Freescale. e500mc Core Reference Manual, 2012. Google Scholar
  14. D. Grund and J. Reineke. Precise and Efficient FIFO-Replacement Analysis Based on Static Phase Detection. In Euromicro Conference on Real-Time Systems (ECRTS), pages 155-164, July 2010. Google Scholar
  15. Daniel Grund. Static Cache Analysis for Real-Time Systems: LRU, FIFO, PLRU. epubli, 2012. Google Scholar
  16. Daniel Grund and Jan Reineke. Toward Precise PLRU Cache Analysis. In International Workshop on Worst-Case Execution Time Analysis (WCET), pages 23-35, 2010. Google Scholar
  17. N. Guan, M. Lv, W. Yi, and G. Yu. WCET Analysis with MRU Caches: Challenging LRU for Predictability. In Real Time and Embedded Technology and Applications Symposium (RTAS), pages 55-64, April 2012. Google Scholar
  18. Nan Guan, Xinping Yang, Mingsong Lv, and Wang Yi. FIFO Cache Analysis for WCET Estimation: A Quantitative Approach. In Design, Automation and Test in Europe (DATE), pages 296-301, San Jose, CA, USA, 2013. EDA Consortium. Google Scholar
  19. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The Mälardalen WCET Benchmarks - Past, Present and Future. In Björn Lisper, editor, Procedings of the 10th International Workshop on Worst-Case Execution Time Analysis (WCET'2010), pages 137-147, Brussels, Belgium, July 2010. OCG. Google Scholar
  20. Sebastian Hahn and Jan Reineke. Design and Analysis of SIC: A Provably Timing-Predictable Pipelined Processor Core. In Real-Time Systems Symposium (RTSS), pages 469-481. IEEE, 2018. Google Scholar
  21. D. Hardy and I. Puaut. WCET Analysis of Multi-level Non-inclusive Set-Associative Instruction Caches. In Real-Time Systems Symposium (RTSS), pages 456-466, November 2008. Google Scholar
  22. Damien Hardy and Isabelle Puaut. WCET Analysis of Instruction Cache Hierarchies. J. Syst. Archit., 57(7):677-694, August 2011. Google Scholar
  23. Damien Hardy, Benjamin Rouxel, and Isabelle Puaut. The Heptane Static Worst-Case Execution Time Estimation Tool. In 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017), volume 8 of International Workshop on Worst-Case Execution Time Analysis, page 12, Dubrovnik, Croatia, June 2017. URL: http://dx.doi.org/10.4230/OASIcs.WCET.2017.8.
  24. Alexandre Joannou, Jonathan Woodruff, Robert Kovacsics, Simon W Moore, Alex Bradbury, Hongyan Xia, Robert NM Watson, David Chisnall, Michael Roe, Brooks Davis, et al. Efficient Tagged Memory. In International Conference on Computer Design (ICCD), pages 641-648. IEEE, 2017. Google Scholar
  25. Lei Ju, Samarjit Chakraborty, and Abhik Roychoudhury. Accounting for Cache-related Preemption Delay in Dynamic Priority Schedulability Analysis. In Design, Automation and Test in Europe (DATE), pages 1623-1628, San Jose, CA, USA, 2007. EDA Consortium. Google Scholar
  26. T. Kloda, M. Solieri, R. Mancuso, N. Capodieci, P. Valente, and M. Bertogna. Deterministic Memory Hierarchy and Virtualization for Modern Multi-Core Embedded Systems. In 2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), Montreal, Canada, April 2019. Google Scholar
  27. NG Chetan Kumar, Sudhanshu Vyas, Ron K Cytron, Christopher D Gill, Joseph Zambreno, and Phillip H Jones. Cache design for mixed criticality real-time systems. In Computer Design (ICCD), pages 513-516. IEEE, 2014. Google Scholar
  28. Benjamin Lesage, Isabelle Puaut, and André Seznec. PRETI: Partitioned REal-TIme shared cache for mixed-criticality real-time systems. In Real-Time and Network Systems (RTNS), pages 171-180. ACM, 2012. Google Scholar
  29. Y. S. Li and S. Malik. Performance analysis of embedded software using implicit path enumeration. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 16(12):1477-1487, December 1997. URL: http://dx.doi.org/10.1109/43.664229.
  30. T. Liu, Y. Zhao, M. Li, and C. J. Xue. Task Assignment with Cache Partitioning and Locking for WCET Minimization on MPSoC. In 2010 39th Int. Conf. Parallel Processing, pages 573-582, September 2010. Google Scholar
  31. Thomas Lundqvist and Per Stenström. Timing Anomalies in Dynamically Scheduled Microprocessors. In Proceedings of the 20th IEEE Real-Time Systems Symposium, RTSS '99, pages 12-, Washington, DC, USA, 1999. IEEE Computer Society. URL: http://dl.acm.org/citation.cfm?id=827271.829103.
  32. Mingsong Lv, Nan Guan, Jan Reineke, Reinhard Wilhelm, and Wang Yi. A survey on static cache analysis for real-time systems. Leibniz Transactions on Embedded Systems, 3(1):05-1, 2016. Google Scholar
  33. R. Mancuso, R. Dudko, E. Betti, M. Cesati, M. Caccamo, and R. Pellizzoni. Real-Time Cache Management Framework for Multi-core Architectures. In Real-Time and Embedded Technology and Applicat. Symp. (RTAS). IEEE, 2013. Google Scholar
  34. Florian Martin, Martin Alt, Reinhard Wilhelm, and Christian Ferdinand. Analysis of Loops. In International Conference on Compiler Construction (CC), pages 80-94, London, UK, UK, 1998. Springer-Verlag. Google Scholar
  35. Sparsh Mittal. A Survey of Techniques for Cache Locking. Transactions on Design Automation of Electronic Systems (TODAES), 21(3):49:1-49:24, May 2016. URL: http://dx.doi.org/10.1145/2858792.
  36. Frank Mueller. Timing Predictions for Multi-Level Caches. In In ACM SIGPLAN Workshop on Language, Compiler, and Tool Support for Real-Time Systems, pages 29-36, 1997. Google Scholar
  37. R. Pellizzoni, E. Betti, S. Bak, G. Yao, J. Criswell, M. Caccamo, and R. Kegley. A predictable execution model for COTS-based embedded systems. In Real-Time and Embedded Technology and Applicat. Symp. (RTAS), pages 269-279. IEEE, 2011. Google Scholar
  38. Krerk Piromsopa and Richard J Enbody. Secure bit: Transparent, hardware buffer-overflow protection. Transactions on Dependable and Secure Computing, 3(4):365-376, 2006. Google Scholar
  39. Isabelle Puaut. WCET-centric software-controlled instruction caches for hard real-time systems. In Euromicro Conference on Real-Time Systems (ECRTS), pages 10-pp. IEEE, 2006. Google Scholar
  40. Isabelle Puaut and David Decotigny. Low-complexity algorithms for static cache locking in multitasking hard real-time systems. In Real-Time Systems Symposium (RTSS), pages 114-123. IEEE, 2002. Google Scholar
  41. Jan Reineke. Caches in WCET analysis: predictability, competitiveness, sensitivity. epubli, 2008. Google Scholar
  42. Jan Reineke, Daniel Grund, Christoph Berg, and Reinhard Wilhelm. Timing Predictability of Cache Replacement Policies. Real-Time Syst., 37(2):99-122, November 2007. URL: http://dx.doi.org/10.1007/s11241-007-9032-3.
  43. A. Sarkar, F. Mueller, and H. Ramaprasad. Static Task Partitioning for Locked Caches in Multicore Real-Time Systems. ACM Trans. Embed. Comput. Syst., 14(1):4:1-4:30, January 2015. Google Scholar
  44. M. R. Soliman and R. Pellizzoni. WCET-Driven dynamic data scratchpad management with compiler-directed prefetching. In Euromicro Conference on Real-Time Systems (ECRTS), volume 76, pages 24:1-24:23, 2017. Google Scholar
  45. Chengyu Song, Hyungon Moon, Monjur Alam, Insu Yun, Byoungyoung Lee, Taesoo Kim, Wenke Lee, and Yunheung Paek. HDFI: hardware-assisted data-flow isolation. In Symposium on Security and Privacy (SP), pages 1-17. IEEE, 2016. Google Scholar
  46. Vivy Suhendra, Tulika Mitra, Abhik Roychoudhury, and Ting Chen. WCET centric data allocation to scratchpad memory. In Real-Time Systems Symposium (RTSS), pages 10-pp. IEEE, 2005. Google Scholar
  47. X. Vera, B. Lisper, and J. Xue. Data Cache Locking for Tight Timing Calculations. ACM Trans. Embed. Comput. Syst., 7(1):4:1-4:38, December 2007. Google Scholar
  48. Xavier Vera, Björn Lisper, and Jingling Xue. Data Cache Locking for Higher Program Predictability. SIGMETRICS Perform. Eval. Rev., 31(1):272-282, June 2003. URL: http://dx.doi.org/10.1145/885651.781062.
  49. Jack Whitham and Neil Audsley. Studying the applicability of the scratchpad memory management unit. In Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 205-214. IEEE, 2010. Google Scholar
  50. R. Wilhelm, J. Engblom, A. Ermedahl, N. Holsti, S. Thesing, D. Whalley, G. Bernat, C. Ferdinand, R. Heckmann, T. Mitra, F. Mueller, I. Puaut, P. Puschner, J. Staschulat, and P. Stenström. The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embedded Comput. Syst. (TECS), 7(3), 2008. Google Scholar
  51. Jonathan Woodruff, Robert NM Watson, David Chisnall, Simon W Moore, Jonathan Anderson, Brooks Davis, Ben Laurie, Peter G Neumann, Robert Norton, and Michael Roe. The CHERI capability model: Revisiting RISC in an age of risk. In International Symposium on Computer Architecture (ISCA), 2014. Google Scholar
  52. G. Yao, R. Pellizzoni, S. Bak, E. Betti, and M. Caccamo. Memory-centric scheduling for multicore hard real-time systems. Real-Time Syst., 48(6):681-715, 2012. Google Scholar
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