A Framework to Quantify the Overestimations of Static WCET Analysis

Authors Hugues Cassé, Haluk Ozaktas, Christine Rochange



PDF
Thumbnail PDF

File

OASIcs.WCET.2015.1.pdf
  • Filesize: 497 kB
  • 10 pages

Document Identifiers

Author Details

Hugues Cassé
Haluk Ozaktas
Christine Rochange

Cite As Get BibTex

Hugues Cassé, Haluk Ozaktas, and Christine Rochange. A Framework to Quantify the Overestimations of Static WCET Analysis. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/OASIcs.WCET.2015.1

Abstract

To reduce complexity while computing an upper bound on the worst-case execution time, static WCET analysis performs over-approximations. This feeds the general feeling that static WCET estimations can be far above the real WCET. This feeling is strengthened when these estimations are compared to measured execution times: generally, it is very unlikely to capture the worstcase from observations, then the difference between the highest watermark and the proven WCET upper bound might be considerable. In this paper, we introduce a framework to quantify the possible overestimation on WCET upper bounds obtained by static analysis. The objective is to derive a lower bound on the WCET to complement the upper bound.

Subject Classification

Keywords
  • Static WCET analysis
  • uncertainty
  • overestimation
  • cache analysis

Metrics

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

References

  1. Clément Ballabriga and Hugues Cassé. Improving the first-miss computation in set-associative instruction caches. In Euromicro Conf. on Real-Time Systems (ECRTS), 2008. Google Scholar
  2. Clément Ballabriga, Hugues Cassé, Christine Rochange, and Pascal Sainrat. OTAWA: An open toolbox for adaptive wcet analysis. In Software Technologies for Embedded and Ubiquitous Systems, 2010. Google Scholar
  3. Antoine Colin and Isabelle Puaut. Worst case execution time analysis for a processor with branch prediction. Real-Time Systems, 18(2), 2000. Google Scholar
  4. Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys (CSUR), 43(4):35, 2011. Google Scholar
  5. Niklas Holsti et al. WCET Tool Challenge 2008: report. In Workshop on Worst-Case Execution Time Analysis, 2008. Google Scholar
  6. Christian Ferdinand. A fast and efficient cache persistence analysis. Technical report, Saarländische Universität (Germany), 2005. Google Scholar
  7. Christian Ferdinand, Florian Martin, and Reinhard Wilhelm. Applying compiler techniques to cache behavior prediction. In ACM SIGPLAN Workshop on Language, Compiler and Tool Support for Real-Time Systems, 1997. Google Scholar
  8. Christian Ferdinand and Reinhard Wilhelm. On predicting data cache behavior for real-time systems. In Languages, Compilers, and Tools for Embedded Systems, 1998. Google Scholar
  9. Chunho Lee, Miodrag Potkonjak, and William H Mangione-Smith. Mediabench: a tool for evaluating and synthesizing multimedia and communicatons systems. In Intl symposium on Microarchitecture. IEEE Computer Society, 1997. Google Scholar
  10. Y.-T. S. Li, S. Malik, and A. Wolfe. Efficient microarchitecture modelling and path analysis for real-time software. In IEEE Real-Time Systems Symposium (RTSS), 1995. Google Scholar
  11. Thomas Lundqvist and Per Stenstrom. Timing anomalies in dynamically scheduled microprocessors. In Real-time systems symposium (RTSS), 1999. Google Scholar
  12. Fadia Nemer, Hugues Cassé, Pascal Sainrat, and Jean-Paul Bahsoun. Inter-Task WCET computation for A-way Instruction Caches. In Symp. on Industrial Embedded Systems (SIES), 2008. Google Scholar
  13. Christine Rochange and Pascal Sainrat. A context-parameterized model for static analysis of execution times. 2009. Google Scholar
  14. V. Suhendra, T. Mitra, A. Roychoudhury, and Ting Chen. Efficient detection and exploitation of infeasible paths for software timing analysis. In Design Automation Conference (DAC), 2006. 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