salle A. Turing CE4
3 April 2014 - 14h00
Refinement of Worst-Case Execution Time Bounds by Graph Pruning
by Florian Brandner from ENSTA-ParisTech
Abstract: As real-time systems increase in complexity to provide more and more
functionality and perform more demanding computations, the problem of
statically analyzing the Worst-Case Execution Time bound (WCET) of real-time
programs is becoming more and more time-consuming and imprecise.
The problem stems from the fact that with increasing program size also the
number of potentially relevant program and hardware states to be considered
during the WCET analysis increases. However, only a relatively small portion
of the program actually contributes to the final WCET bound. Large parts of the
program are thus irrelevant and are analyzed in vain. In the best case this
only leads to increased analysis time. Very often, however, the analysis of
irrelevant program parts interferes with the analysis of those program parts
that turn out to be relevant.
We explore a novel technique based on graph pruning that promises to reduce
the analysis overhead and, at the same time, increase the analysis' precision.
The basic idea is to eliminate those program parts from the analysis problem
that are known to be irrelevant for the final WCET bound. This reduces the
analysis overhead, since only a subset of the program and hardware states
have to be tracked. Consequently, more aggressive analysis techniques can be
applied to the smaller problem, effectively reducing the overestimation of the
WCET. As a side-effect, interference from irrelevant program parts are
eliminated, e.g., on addresses of memory accesses, on loop bounds, or on the
cache or processor state.
First experiments using a commercial WCET analysis tool show that our approach
is feasible in practice and leads to reductions of up to 12% when a standard
IPET approach is used for the analysis.
