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.