WCET - Worst-Case Execution Time analysis

Research Group:


Status:

active

Start date:

1999

Worst-Case Execution Time (WCET) analysis tries to find an upper bound for the time needed to execute a program. Such WCET bounds are very important when designing and verifying real-time systems. Current industrial practice is to estimate these bounds from measurements, something often complicated and error-prone.

Static WCET analysis is an alternative method to estimate the WCET of a program, relying on mathematical models of the software and hardware involved. The estimates are guaranteed never to underestimate the true WCET. To bound the WCET in this way, both the characteristics of the program code and the computer hardware must be considered. The activities in the WCET project focus on the first problem, investigating methods to derive information on the possible execution paths of the analysed program like iteration bounds of loops, and dependencies between conditionals.

We have also performed case studies concerning WCET analysis with end-user companies, using commercial state-of-the-art WCET analysis tools. The result of the case studies have been used to guide both continued research and commercial WCET tool development.

Lately, we have investigated how to create approximate timing models for source code. Such timing models can be used to perform an approximate source-level WCET analysis, which can be useful to support time budgeting and selection of hardware earlier in the development process. We are also working actively with methods for parametric WCET analysis, where the result is a formula with input parameters rather than a single number, and with WCET analysis of explicitly parallel programs.

The WCET project originated as a collaboration between Uppsala University (in Uppsala, Sweden), C-Lab (in Paderborn, Germany) and MDH (in Västerås, Sweden). Since 2003 it has been run exclusively at MDH.

[Show all publications]

Improved Precision in Polyhedral Analysis with Wrapping (Jan 2017)
Stefan Bygde, Björn Lisper, Niklas Holsti
Science of Computer Programming (SCICO)

Early execution time-estimation through automatically generated timing models (Nov 2016)
Peter Altenbernd , Jan Gustafsson, Björn Lisper, Friedhelm Stappert
Real-Time Systems: The International Journal of Time-Critical Computing Systems (RTSJ'15)

TACLeBench: A Benchmark Collection to Support Worst-Case Execution Time Research (Jul 2016)
Heiko Falk , Sebastian Altmeyer , Peter Hellinckx , Björn Lisper, Wolfgang Puffitsch , Christine Rochange , Martin Schoeberl , Rasmus Bo Sorensen , Peter Wägemann , Simon Wegener
Proc. 16th International Workshop on Worst-Case Execution Time Analysis (WCET'2016) (WCET16)

Static Execution Time Analysis of Parallel Systems (May 2016)
Andreas Gustavsson

WCET and Mixed-Criticality: What does Confidence in WCET Estimations Depend Upon? (Jul 2015)
Sebastian Altmeyer , Björn Lisper, Claire Maiza , Jan Reineke , Christine Rochange
15th International Workshop on Worst-Case Execution Time Analysis (WCET'15)

Combining Bound-T and SWEET to Analyse Dynamic Control Flow in Machine-Code Programs (Nov 2014)
Niklas Holsti , Jan Gustafsson, Linus Källberg, Björn Lisper

Björn Lisper, Professor

Email: bjorn.lisper@mdh.se
Room: U1-091
Phone: +46-21-151709