Timing Validation: WCET Computation

Real-time systems are typically composed of a set of tasks with specified deadlines (mostly dictated by the surrounding physical environment). A schedulability analysis has to be performed in order to guarantee that all timing constraints will be met ("timing validation"). All existing techniques for schedulability analysis require the worst-case execution time (WCET) of each task in the system to be known prior to its execution.

Since this is not computable in general, estimates of the WCET have to be calculated. These estimates have to be safe, i.e., they must never underestimate the real execution time. On the other hand, they should be tight, i.e., the overestimate should be as small as possible.

The WCET determination is composed of several different tasks:

Computation of address ranges for instructions accessing memory by a value analysis
Classification of memory references as cache misses or hits, called cache analysis
Predicting the behavior of the program on the processor pipeline, called pipeline analysis
Determination of the worst-case execution path of the program, called path analysis

Many of these tasks are quite complex for modern microprocessors and DSPs.

The arrangement of the tasks is described in the picture to the right. The results of the value analysis are used by the cache analysis to predict the behavior of the (data) cache. The results of the cache analysis are fed into the pipeline analysis allowing the prediction of pipeline stalls due to cache misses. The combined results of the cache and pipeline analyses are used to compute the execution time of program paths.

The separation of WCET determination into several phases has the additional effect that different methods tailored to subtasks can be used. In our case, the value analysis, the cache analysis, and the pipeline analysis are done by abstract interpretation, a semantics based method for static program analysis. Path analysis is done by integer linear programming.

Next: Reconstruction of the control flow from binaries | Previous: Introduction | Contents | Home