Static Worst Case Execution Time Analysis for Pipelined Processor Architectures

Abstract

Worst Case Execution Time (WCET) estimation is substantial for scheduling analysis of real-time systems. Performing static WCET estimation requires performing program analysis as well as modeling the impact of complex micro-architectural features of modern processors such as; pipelining, instruction/data caching, dynamic branch prediction, out-of-order execution, speculative execution, and fine-grained chip multi-threading. The results of program analysis and of modeling can then be combined to obtain linear constraints which in turn can be solved by an Integer Linear Programming (ILP) solver. Automatically generating the integer linear equations that are used as input for the solvers remains a challenging task. This thesis proposes a Domain Specific Language (DSL) called Constraint Generation Language (CGL) that can be used to describe the general constraints in a concise manner. The thesis also illustrates how CGL can be extended to automate the constraints generation from a program’s branch flow graph and control flow graph. CGL’s flexibility is demonstrated by using it with different ILP solvers. Estimating the number of mispredictions is critically important for estimating the WCET for real-time systems. This thesis generalizes and improves over previous attempts to provide a safe and tight mispredication count estimate for various kinds of dynamic branch predictors. Finally, the thesis proposes an automatic method for calculating tight upper bounds on the number of loop iterations.