Precise measurement-based worst-case execution time estimation

Abstract

During the development of real-time systems, the worst-case execution time (WCET) of every task or program in the system must be known in order to show that all timing requirements for the system are fulfilled. The increasing complexity of modern processor architectures makes achieving this objective more and more challenging.The incorporation of performance enhancing features like caches and speculative execution, as well as the interaction of these components, make execution times highly dependent on the execution history and the overall state of the system. To determine a bound for the execution time of a program, static methods for timing analysis face the challenge to model all possible system states which can occur during the execution of the program. The necessary approximation of potential system states is likely to overestimate the actual WCET considerably. On the other hand, measurement-based timing analysis techniques use a relatively small number of run-time measurements to estimate the worst-case execution time. As it is generally impossible to observe all potential executions of a real-world program, this approach cannot provide any guarantees about the calculated WCET estimate and the results are often imprecise. This thesis presents a new approach to timing analysis which was designed to overcome the problems of existing methods. By partitioning the analyzed programs into easily traceable segments and by precisely controlling run-time measurements, the new method is able to preserve information about the execution context of measured execution times. After an adequate number of measurements have been taken, this information can be used to precisely estimate the WCET of a program without being overly pessimistic. The method can be seamlessly integrated into frameworks for static program analysis. Thus results from static analyses can be used to make the estimates more precise and perform run-time measurements more efficiently.