Document Open Access Logo

WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?

Authors Sebastian Altmeyer, Björn Lisper, Claire Maiza, Jan Reineke, Christine Rochange

PDF

File

Thumbnail PDF
PDF
OASIcs.WCET.2015.65.pdf
  • Filesize: 362 kB
  • 10 pages

Document Identifiers

Subject Classification

Keywords
  • mixed criticality
  • WCET analysis
  • confidence in WCET estimates

Metrics

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

Abstract

Mixed-criticality systems integrate components of different criticality. Different criticality levels require different levels of confidence in the correct behavior of a component. One aspect of correctness is timing. Confidence in worst-case execution time (WCET) estimates depends on the process by which they have been obtained. A somewhat naive view is that static WCET analyses determines safe bounds in which we can have absolute confidence, while measurement-based approaches are inherently unreliable. In this paper, we refine this view by exploring sources of doubt in the correctness of both static and measurement-based WCET analysis.

Cite As Get BibTex

Sebastian Altmeyer, Björn Lisper, Claire Maiza, Jan Reineke, and Christine Rochange. WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon?. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 65-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/OASIcs.WCET.2015.65

Author Details

Sebastian Altmeyer
Björn Lisper
Claire Maiza
Jan Reineke
Christine Rochange

References

  1. Andreas Abel and Jan Reineke. Measurement-based modeling of the cache replacement policy. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2013. Google Scholar
  2. Andreas Abel and Jan Reineke. Reverse engineering of cache replacement policies in intel microprocessors and their evaluation. In Int'l Symp. on Performance Analysis of Systems and Software (ISPASS), 2014. Google Scholar
  3. 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 Systems, 48(5):499-526, 2012. Google Scholar
  4. Mickaël Armand, Germain Faure, Benjamin Grégoire, Chantal Keller, Laurent Théry, and Benjamin Wener. Verifying SAT and SMT in Coq for a fully automated decision procedure. In International Workshop on Proof-Search in Axiomatic Theories and Type Theories, 2011. Google Scholar
  5. Vlastimil Babka and Petr Tuma. Investigating cache parameters of x86 family processors. In Computer Performance Evaluation and Benchmarking. Springer, 2009. Google Scholar
  6. Lee Kee Chong et al. Integrated timing analysis of application and operating systems code. In 34th Real-Time Systems Symposium (RTSS), pages 128-139. IEEE, 2013. Google Scholar
  7. Patrick Cousot and Radhia Cousot. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In 4th ACM Symposium on Principles of Programming Languages (POPL), Los Angeles, January 1977. Google Scholar
  8. Christian Ferdinand and Reinhard Wilhelm. Efficient and precise cache behavior prediction for real-time systems. Real-Time Systems, 17(2-3):131-181, 1999. Google Scholar
  9. Alexis Fouilhé, David Monniaux, and Michaël Périn. Efficient generation of correctness certificates for the abstract domain of polyhedra. In 20th International Symposium on Static Analysis (SAS), pages 345-365, 2013. Google Scholar
  10. Patrick Graydon and Iain Bate. Safety assurance driven problem formulation for mixed-criticality scheduling. In Workshop on Mixed Criticality Systems, 2013. Google Scholar
  11. Sebastian Hahn, Jan Reineke, and Reinhard Wilhelm. Towards compositionality in execution time analysis: definition and challenges. SIGBED Review, 12(1):28-36, 2015. Google Scholar
  12. Andreas Hansson et al. CoMPSoC: A template for composable and predictable multi-processor system on chips. ACM TODAES, 14(1):1-24, 2009. Google Scholar
  13. Damien Hardy, Thomas Piquet, and Isabelle Puaut. Using bypass to tighten WCET estimates for multi-core processors with shared instruction caches. In Real-Time Systems Symposium (RTSS), 2009. Google Scholar
  14. Tobias John and Robert Baumgartl. Exact cache characterization by experimental parameter extraction. In Int'l Conf. on Real-Time and Network Systems (RTNS), 2007. Google Scholar
  15. Timon Kelter et al. Static analysis of multi-core TDMA resource arbitration delays. Real-Time Systems, 50(2), 2014. Google Scholar
  16. Hanbing Li, Isabelle Puaut, and Erven Rohou. Traceability of flow information: Reconciling compiler optimizations and WCET estimation. In 22nd International Conference on Real-Time Networks and Systems (RTNS), page 97, 2014. Google Scholar
  17. Markus Lindgren, Hans Hansson, and Henrik Thane. Using measurements to derive the worst-case execution time. In Int'l Conf. on Real-Time Computing Systems and Applications (RCTSA), 2000. Google Scholar
  18. Björn Lisper and Marcelo Santos. Model identification for WCET analysis. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2009. Google Scholar
  19. Isaac Liu et al. A PRET microarchitecture implementation with repeatable timing and competitive performance. In ICCD, September 2012. Google Scholar
  20. Thomas Lundqvist and Per Stenström. Timing anomalies in dynamically scheduled microprocessors. In 20th IEEE Real-Time Systems Symposium (RTSS), 1999. Google Scholar
  21. Mingsong Lv et al. Combining abstract interpretation with model checking for timing analysis of multicore software. In Real-Time Systems Symposium (RTSS), 2010. Google Scholar
  22. André Oliveira Maroneze. Certified Compilation and Worst-Case Execution Time Estimation. PhD thesis, Université Rennes 1, June 2014. Google Scholar
  23. Marco Paolieri, Eduardo Quiñones, Francisco J. Cazorla, Robert I. Davis, and Mateo Valero. IA3: An interference aware allocation algorithm for multicore hard real-time systems. In Real-Time and Embedded Technology and Applications Symposium (RTAS), 2011. Google Scholar
  24. Adrian Prantl. High-level compiler support for timing analysis. PhD thesis, Technical University of Vienna, June 2010. Google Scholar
  25. Jan Reineke et al. A definition and classification of timing anomalies. In 6th International Workshop on Worst-Case Execution Time Analysis (WCET), July 2006. Google Scholar
  26. Jan Reineke and Rathijit Sen. Sound and efficient WCET analysis in presence of timing anomalies. In Workshop on Worst-Case Execution-Time Analysis (WCET), 2009. Google Scholar
  27. Marc Schlickling. Timing Model Derivation - Static Analysis of Hardware Description Languages. PhD thesis, Saarland University, January 2013. Google Scholar
  28. Marc Schlickling and Markus Pister. Semi-automatic derivation of timing models for WCET analysis. In Int'l Conf. on Languages, Compilers, and Tools for Embedded Systems (LCTES), 2010. Google Scholar
  29. Martin Schoeberl. A Java processor architecture for embedded real-time systems. Journal of Systems Architecture, 54(1-2):265 - 286, 2008. Google Scholar
  30. Martin Schoeberl et al. T-CREST: Time-predictable multi-core architecture for embedded systems. Journal of Systems Architecture, To appear in 2015. Google Scholar
  31. Sanjit A. Seshia and Alexander Rakhlin. Quantitative analysis of systems using game-theoretic learning. ACM Trans. Embed. Comput. Syst., 11(S2):55:1-55:27, August 2012. Google Scholar
  32. Ingmar J. Stein. ILP-based Path Analysis on Abstract Pipeline State Graphs. PhD thesis, Saarland University, May 2010. Google Scholar
  33. Theo Ungerer et al. MERASA: Multi-core execution of hard real-time applications supporting analysability. IEEE Micro, 99, 2010. Google Scholar
  34. Theo Ungerer et al. parMERASA - multi-core execution of parallelised hard real-time applications supporting analysability. In Euromicro Conference on Digital System Design (DSD), pages 363-370, 2013. Google Scholar
  35. Steve Vestal. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In 28th IEEE International Real-Time Systems Symposium (RTSS), pages 239-243, Washington, DC, USA, 2007. IEEE Computer Society. Google Scholar
  36. Petros Voudouris. Analysis and modeling of the timing bahavior of GPU architectures. Master’s thesis, Eindhoven University of Technology, 2014. Google Scholar
  37. Ingomar Wenzel, Raimund Kirner, Bernhard Rieder, and Peter Puschner. Measurement-based timing analysis. 17:430-444, 2008. Google Scholar
  38. Reinhard Wilhelm et al. Memory hierarchies, pipelines, and buses for future architectures in time-critical embedded systems. IEEE Transactions on CAD of Integrated Circuits and Systems, 28(7):966-978, July 2009. Google Scholar
  39. Nicky Williams. WCET measurement using modified path testing. In Workshop on Worst-Case Execution-Time Analysis (WCET), 2005. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact