Instruction Duration Estimation by Partial Trace Evaluation

Hard and soft real time systems require, for each process, the worst-case execution time (WCET), which is needed by the scheduler's admission tests and subsequently limits a task's execution time during operation. A worst-case execution time analysis is usually performed in two distinct steps: first the program is analyzed to extract semantic information and determine maximal bounds on the number of iterations for each basic block. In a second step the duration of the different program's instructions is computed with respect to the used hardware platform. Modern systems with preemption and modern architectures with non-constant instruction duration (due to pipelining, branch prediction and different level of caches) hinder a fast and precise computation of a program's WCET. We present a technique to approximate the instruction duration on modern processors using precise block bounds. Instead of simulating the CPU behavior on all the possible paths we apply the principle of locality limiting the effects of a given instruction to a restricted time allowing us to analyze large applications in linear time