Forming Virtual Traces for WCET Analysis and Reduction


It is notoriously difficult to model superscalar out-of-order
CPUs for the purposes of worst-case execution time (WCET) analysis,
which can mean that simpler CPUs must be used in hard real-time systems.
To address this problem, it has been suggested that traces
could be used to capture the timing properties of a complex CPU
operation scheduler as it runs a sequence of basic blocks. In previous work,
traces have been implemented using application-specific microcode.

This paper proposes restrictions to a dynamic superscalar
out-of-order CPU to implement virtual traces. These have the same
timing properties as the traces in previous work, but microcode
is not used. Instead, CPU modifications implement the same
functionality. This allows
traces to be used throughout a program because space requirements
are minimal. To take advantage of this, a new allocation algorithm 
is proposed and evaluated for virtual traces.