MRTC research projects

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.

Latest project publications [ Show all publications ]

A prototype tool called SWEET (SWedish Execution Time Tool) has been developed, in a modular fashion supporting different phases of WCET analysis. We have a large number of research results in the areas mentioned above.

We plan to continue to do research in the WCET analysis area for the forseeable future. Some challenges that we plan to take on:

• Timing analysis of multi/many-core processors
• Timing analysis with incomplete information (e.g., missing pieces of software, unlinked code, ...)
• Increased precision, and level of automation, of program flow analysis

We also plan to develop our tool SWEET to the point that it can be publically released.