Worst Case Execution Time Reduction (Submitted for the degree of Doctor of Philosophy) Real−time Processor Architectures for

In a real-time system, programs must respond to external events in a timely fashion, completing all required subtasks before a deadline elapses. Worst case execution time (WCET) analysis is used to assure that deadlines are always met by determining the maximum period of time required to execute parts of a program. WCET analysis has been extensively studied, but existing techniques do not work well with CPUs that make use of dynamic execution optimisation features such as caches and superscalar out-of-order issue units. These features work well for average case execution time (ACET) reduction, but not for WCET reduction, since software must model the worst possible behaviour of the dynamic features to find the WCET. This thesis explores the architectural issues relating to these problems, then characterises a class of CPU architecture that is explicitly designed for WCET reduction. An implementation of this architecture enables WCET reduction by allowing programs to move worst-case execution paths into a microprogram store, which acts as an scratchpad for parallel microinstructions. The exploitation of instruction-level parallelism (ILP) across basic block boundaries is enabled by the use of a superblock scheduler, which allows the architecture to reduce WCET further than previou