OASIcs.WCET.2015.1.pdf
- Filesize: 497 kB
- 10 pages
Document
A Framework to Quantify the Overestimations of Static WCET Analysis
Authors
-
Part of:
Volume:
15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015)
Series: Open Access Series in Informatics (OASIcs)
Conference: Workshop on Worst-Case Execution Time Analysis (WCET) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-07-06
Cite AsGet 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
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.
Keywords
- Static WCET analysis
- uncertainty
- overestimation
- cache analysis
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
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.
-
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.
-
Antoine Colin and Isabelle Puaut. Worst case execution time analysis for a processor with branch prediction. Real-Time Systems, 18(2), 2000.
-
Robert I. Davis and Alan Burns. A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys (CSUR), 43(4):35, 2011.
-
Niklas Holsti et al. WCET Tool Challenge 2008: report. In Workshop on Worst-Case Execution Time Analysis, 2008.
-
Christian Ferdinand. A fast and efficient cache persistence analysis. Technical report, Saarländische Universität (Germany), 2005.
-
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.
-
Christian Ferdinand and Reinhard Wilhelm. On predicting data cache behavior for real-time systems. In Languages, Compilers, and Tools for Embedded Systems, 1998.
-
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.
-
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.
-
Thomas Lundqvist and Per Stenstrom. Timing anomalies in dynamically scheduled microprocessors. In Real-time systems symposium (RTSS), 1999.
-
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.
-
Christine Rochange and Pascal Sainrat. A context-parameterized model for static analysis of execution times. 2009.
-
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.