Document Open Access Logo

Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis

Authors Darshit Shah, Sebastian Hahn, Jan Reineke

PDF
Thumbnail PDF

File

OASIcs.WCET.2018.7.pdf
  • Filesize: 421 kB
  • 11 pages

Document Identifiers

Author Details

Darshit Shah
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Sebastian Hahn
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany
Jan Reineke
  • Saarland University, Saarland Informatics Campus, Saarbrücken, Germany

Funding

This work has been supported by the Deutsche Forschungsgemeinschaft (DFG) as part of the project PEP, and by the Saarbrücken Graduate School of Computer Science which receives funding from the DFG as part of the Excellence Initiative of the German Federal and State Governments.

Cite AsGet BibTex

Darshit Shah, Sebastian Hahn, and Jan Reineke. Experimental Evaluation of Cache-Related Preemption Delay Aware Timing Analysis. In 18th International Workshop on Worst-Case Execution Time Analysis (WCET 2018). Open Access Series in Informatics (OASIcs), Volume 63, pp. 7:1-7:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.WCET.2018.7

Abstract

In the presence of caches, preemptive scheduling may incur a significant overhead referred to as cache-related preemption delay (CRPD). CRPD is caused by preempting tasks evicting cached memory blocks of preempted tasks, which have to be reloaded when the preempted tasks resume their execution. In this paper we experimentally evaluate state-of-the-art techniques to account for the CRPD during timing analysis. We find that purely synthetically-generated task sets may yield misleading conclusions regarding the relative precision of different CRPD analysis techniques and the impact of CRPD on schedulability in general. Based on task characterizations obtained by static worst-case execution time (WCET) analysis, we shed new light on the state of the art.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • real-time systems
  • timing analysis
  • cache-related preemption delay

Metrics

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

References

  1. Sebastian Altmeyer, Robert I. Davis, and Claire Maiza. Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real-Time Syst., 48(5):499-526, 2012. Google Scholar
  2. Sebastian Altmeyer and Claire Maiza. Cache-related preemption delay via useful cache blocks: Survey and redefinition. Journal of Systems Architecture, 57:707-719, August 2011. Google Scholar
  3. Neil C. Audsley et al. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineerung Journal, 1993. Google Scholar
  4. Enrico Bini and Giorgio C. Buttazzo. Measuring the performance of schedulability tests. Real-Time Systems, 30(1-2):129-154, 2005. URL: http://dx.doi.org/10.1007/s11241-005-0507-9.
  5. Claire Burguière, Jan Reineke, and Sebastian Altmeyer. Cache-related preemption delay computation for set-associative caches - pitfalls and solutions. In WCET, June 2009. Google Scholar
  6. José V. Busquets-Mataix et al. Adding instruction cache effect to schedulability analysis of preemptive real-time systems. In RTAS, pages 204-212, 1996. Google Scholar
  7. Christian Ferdinand, Florian Martin, Reinhard Wilhelm, and Martin Alt. Cache behavior prediction by abstract interpretation. Sci. Comput. Program., 35(2):163-189, 1999. URL: http://dx.doi.org/10.1016/S0167-6423(99)00010-6.
  8. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The Mälardalen WCET benchmarks: Past, present and future. In WCET, pages 136-146, 2010. Google Scholar
  9. Sebastian Hahn, Michael Jacobs, and Jan Reineke. Enabling compositionality for multicore timing analysis. In RTNS, pages 299-308, 2016. URL: http://dx.doi.org/10.1145/2997465.2997471.
  10. 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.
  11. John L. Hennessy and David A. Patterson. Computer Architecture - A Quantitative Approach, 5th Edition. Morgan Kaufmann, 2012. Google Scholar
  12. Mathai Joseph and Paritosh Pandya. Finding response times in real-time system. The Computer Journal, 29(5), 1986. Google Scholar
  13. Chang-Gun Lee et al. Analysis of cache-related preemption delay in fixed-priority preemptive scheduling. IEEE Transactions on Computers, 47(6):700-713, 1998. Google Scholar
  14. Yau-Tsun Steven Li and Sharad Malik. Performance analysis of embedded software using implicit path enumeration. In Proceedings of the ACM SIGPLAN Workshop on Languages, Compilers, & Tools for Real-Time Systems (LCT-RTS), pages 88-98, 1995. URL: http://dx.doi.org/10.1145/216636.216666.
  15. Yudong Tan and Vincent John Mooney III. Timing analysis for preemptive multitasking real-time systems with caches. ACM Trans. Embedded Comput. Syst., 6(1):7, 2007. URL: http://dx.doi.org/10.1145/1210268.1210275.
  16. Hiroyuki Tomiyama and Nikil D. Dutt. Program path analysis to bound cache-related preemption delay in preemptive real-time systems. In CODES, pages 67-71, 2000. 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 Imprint Privacy Contact