Predictable Out-of-order Execution Using Virtual Traces


The problem of worst-case execution time (WCET) analysis of
complex CPUs is addressed in this paper using a proposed architectural 
modification. The virtual trace controller (VTC) constrains execution
to follow only the paths that have been considered by the WCET
analysis model, allowing the WCET to be determined safely by 
measurement. Each path has a constant execution time regardless
of CPU complexity because the VTC enforces predictable operation.
This paper evaluates the VTC using benchmark programs and
the M5 simulator.

The results show that guaranteed throughput is increased for
many programs using the constrained CPU model versus an 
idealised in-order design, indicating that the VTC can make complex
CPU designs operate predictably without reducing throughput
to the level of a simple CPU design. Additional results provide
more information about the implications of each of the VTC features.
Of all the restrictions introduced for predictability,
disabling memory forwarding has the greatest effect on the
maximum throughput, although conditional branches can also be
significant.  This paper suggests ways to improve the VTC
to increase the guaranteed throughput.