A prerequisite for creating a safe and predictable real time computer system is to have knowledge about its
timing behavior during operation. The Worst Case Execution Time (WCET) is one of the key values to
consider when predicting this timing behavior, since it ensures that every task meets its deadline in the
system. A missed deadline in systems with critical tasks can lead to severe consequences.
Dynamic WCET analysis is a widely used method to derive WCET value in the industry today. The
method is based on using simulation and measurement techniques. The WCET value is derived by
performing a set of automatic tests on the system and measure its execution time. To ensure that a safe
WCET value is derived the automatic tests must cover the worst case scenario, which is tough to find when
the systems increase in size and complexity.
Static WCET analysis is an alternative method, where it is guaranteed that an overestimated WCET value is
obtained. The method uses mathematical models of the system hard and software to calculate WCET.
Therefore, this method has been the main research subject for many research groups. One of the key
components in making a safe and tight WCET value, using static WCET analysis technique, is program
flow information.
The information describes the possible program flows through the program; this information can be either
provided to the WCET analyzer manually, by user, or automatically, by a flow analyzer. Deriving flow
information manually is done by:
Studying and analyzing the program source code, and manually calculating loop bounds,
detecting infeasible paths and making recursion bounds.
Providing the information to a WCET analyzer, usually by writing them in form of
annotations in a program language supported by the analyzer.
The steps above are time consuming and unsafe when the program complexity increases, that makes it
preferable to use flow analysis to provide flow information. This has been shown in a previous study at
Volvo Construction Equipment, where the WCET analysis tool aiT has been used. This work will complete
the study by evaluating an automatic method, using flow analyzers to derive flow information for the
analyzed code.
Flow analyzers use mathematical methods to model and derive flow information of program source code.
This flow information makes deriving WCET estimates safe, simple and requires no or minimum user
interaction. Therefore, Volvo CE is interested in the development of static WCET analysis tools where the
flow information is obtained automatically.
This work evaluated SWEdish Execution time Tool (SWEET), a prototype WCET analysis tool built by a
research group from Malardalens University (MDH). The results are compared to the ones obtained in
previous work using aiT, where the flow information is derived manually.
We have found that SWEET derived the same flow information that was derived manually, but since it is a
prototype tool a lot of manual work was needed. The manual work consisted mainly of adapting the Volvo
CE application to the SWEET analysis environment. This work has also contributed in development of
SWEET, adding new functionality and making it more users friendly.
2007.
This report is a MSc thesis performed at the Department of Electronic, Computer, and Software Systems (ECS) at KTH, but was supervised by Jan Gustafsson, IDE, for the WCET project.