Context-sensitive Parametric WCET Analysis

Authors Clément Ballabriga, Julien Forget, Giuseppe Lipari



PDF
Thumbnail PDF

File

OASIcs.WCET.2015.55.pdf
  • Filesize: 0.59 MB
  • 10 pages

Document Identifiers

Author Details

Clément Ballabriga
Julien Forget
Giuseppe Lipari

Cite AsGet BibTex

Clément Ballabriga, Julien Forget, and Giuseppe Lipari. Context-sensitive Parametric WCET Analysis. In 15th International Workshop on Worst-Case Execution Time Analysis (WCET 2015). Open Access Series in Informatics (OASIcs), Volume 47, pp. 55-64, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/OASIcs.WCET.2015.55

Abstract

In this paper, we propose aWCET analysis that focuses on two aspects. First, it supports contextsensitive hardware and software timing effects, meaning that it is sensitive to the execution history of the program and thus can account for effects like cache persistence, triangular loop, etc. Second, it supports the introduction of parameters in both the software model (e.g. parametric loop bounds) and the hardware model (e.g. number of cache misses). WCET computation by static analysis is traditionally handled by the Implicit Path Enumeration Technique (IPET), using an Integer Linear Program (ILP) that is difficult to resolve parametrically. We suggest an alternative tree-based approach. We define a context-sensitive CFG format to express these effects, and we provide an efficient method to process it, giving a parametric WCET formula. Experimental results show that this new method is significantly faster and more accurate than existing parametric approaches.
Keywords
  • Parametric
  • WCET
  • Real-time
  • Static analysis

Metrics

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

References

  1. Clément Ballabriga, Hugues Cassé, and Marianne De Michiel. A Generic Framework for Blackbox Components in WCET Computation. In 9th International Workshop on Worst-Case Execution Time Analysis (WCET), 2009. 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, volume 6399 of Lecture Notes in Computer Science. Springer, 2010. Google Scholar
  3. Michel Berkelaar, Kjell Eikland, and Peter Notebaert. lp_solve 5.5, open source (mixed-integer) linear programming system. URL: http://lpsolve.sourceforge.net/5.5/.
  4. S. Bygde, A. Ermedahl, and B. Lisper. An efficient algorithm for parametric wcet calculation. In Embedded and Real-Time Computing Systems and Applications (RTCSA), 2009. Google Scholar
  5. Stefan Bygde. Parametric WCET Analysis. PhD thesis, Mälardalen University Press, 2013. Google Scholar
  6. Cristina Cifuentes. A structuring algorithm for decompilation. In XIX Conferencia Latinoamericana de Informática, 1993. Google Scholar
  7. Antoine Colin and Guillem Bernat. Scope-tree: A program representation for symbolic worst-case execution time analysis. In 14th Euromicro Conference on Real-Time Systems (ECRTS), Washington, DC, USA, 2002. IEEE Computer Society. Google Scholar
  8. Paul Feautrier. Parametric integer programming. RAIRO Operations Research, 22, 1988. Google Scholar
  9. Christian Ferdinand, Florian Martin, Reinhard Wilhelm, and Martin Alt. Cache behavior prediction by abstract interpretation. Sci. Comput. Program., 35(2):163-189, 1999. Google Scholar
  10. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Björn Lisper. The mälardalen wcet benchmarks - past, present and future. In 10th International Workshop on Worst-Case Execution Time Analysis (WCET), 2010. Google Scholar
  11. Sung-Soo Lim, Young Hyun Bae, Gyu Tae Jang, Byung-Do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, Kunsoo Park, Soo-Mook Moon, and Chong Sang Kim. An Accurate Worst Case Timing Analysis for RISC Processors. In Real-Time Systems Symposium (RTSS), pages 97-108, 1995. Google Scholar
  12. S. Mohan, F. Mueller, W. Hawkins, M. Root, C. Healy, and D. Whalley. Parascale: exploiting parametric timing analysis for real-time schedulers and dynamic voltage scaling. In Real-Time Systems Symposium (RTSS), 2005. Google Scholar
  13. Christine Rochange and Pascal Sainrat. A context-parameterized model for static analysis of execution times. In Transactions on High-Performance Embedded Architectures and Compilers II, volume 5470 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2009. Google Scholar
  14. Yau tsun Steven Li, Sharad Malik, and Andrew Wolfe. Efficient microarchitecture modeling and path analysis for real-time software. In Real-Time Systems Symposium (RTSS), 1995. 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