Subgraph-Based Refinement of Worst-Case Execution Time Bounds

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 6% when a standard IPET approach is used for the analysis.


https://hal-ensta.archives-ouvertes.fr/hal-00978015
Contributor : Florian Brandner <>
Submitted on : Friday, April 11, 2014 - 9:17:53 PM
Last modification on : Monday, April 14, 2014 - 9:02:26 AM
Document(s) archivé(s) le : Friday, July 11, 2014 - 1:10:54 PM

File

iter-wcet-tr.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00978015, version 1

Collections

Citation

Florian Brandner, Alexander Jordan. Subgraph-Based Refinement of Worst-Case Execution Time Bounds. 2014. <hal-00978015>

Export

Share

Metrics

Record views

168

Document downloads

136