Worst Case Execution Time Analysis Using Abstract Interpretation
Mälardalen University and Uppsala University
As a result of the industrial deployment of real-time systems, there is an
increasing demand for methods to perform safe and tight calculation of the
worst case execution time (WCET) of programs. The WCET is a
necessary prerequisite to be able to guarantee correct timing behaviour of
the real-time system. WCET calculation means to find the path, often
among a huge number of paths, that takes the longest time to execute. The
calculation requires path information for the program, such as the
maximum number of iterations in loops and identification of paths that are
never executed. In most existing WCET analysis methods, this
information is given as manual annotations by the programmer.
In this thesis we present a method which automatically calculates
path information for object-oriented real-time programs by static analysis
of the program. Thus, the method can be used in automating the WCET
by relieving the programmer from the tedious and error-prone manual
The method, which is based on abstract interpretation, generates safe
but not necessarily exact path information. A trade-off between quality and
calculation cost has to be made, since finding the exact information is a
very complex problem. We propose time budgets to guarantee
termination of the analysis for all programs.
We show how the general abstract interpretation theory can be used, in a
structured way, to approximate the semantics of an imperative or
object-oriented programming language.
We have chosen to analyze RealTimeTalk (RTT), an object-oriented
language based on Smalltalk. We have developed a prototype tool which
implements our analysis for a subset of the language. We show that the tool
is capable of analyzing programs with a complexity which would make manual
annotation of the program all but trivial.
We also discuss the role of the method in a WCET analysis tool
May 2, 2000
Place: Information technology, Uppsala University
Room 1549 is in Building 1, Floor 5, room 49
Time: 13.15 - 14.00 (+ coffee and discussion)
(in the northern part of the building).
Help on how get here and
MIC campus drawing.
There will be an extended period for discussions after the seminar nourished by cookies and coffee.
Speakers are encouraged to give an short (5 min) introduction to the subject at the begining of the talk.
Listeners are excused if they have to leave after 1 hour.
Updated 13-Apr-2000 11:19 by Roland Grönroos
e-mail: info -at- astec.uu.se