The Framework

Since the execution time of a program is affected by both the data input, which determines the program path taken, and the underlying processor, which affects the instruction timing, Static WCET analysis generally involves three sub-tasks:
  • Program path analysis
  • Microarchitecture modeling
  • WCET calculation
Program path analysis
It works on either the source program or the compiled code or both to derive program flow information, such as what are the feasible/infeasible execution paths. Infeasibl paths will be disregarded during the search for the worst case path/execution time.
Microarchitecture modeling
It is concerned with instruction timing. Modern processors employ aggressive microarchitectural features such as pipelining, caching and branch prediction to improve the performance of the applications. These features make the execution time of individual instructions non-constant (e.g., an instruction experiencing a cache miss executes much longer than the case with a cache hit) and dependent on execution history. Microarchitecture modeling employs static techniques to study the behavior of these features and provides instruction timing information(e.g., the places or number of times cache misses occur) for the determination of the execution time of program paths.
WCET calculation
With the program path information and instruciton timing information obtained from aforementioned sub-tasks, the costs of program paths can be evaulated and the maximum one will be taken as the estimated WCET.

The Workflow


Our tool makes use of SimpleScalar toolset to compile and simulate the applications, and the processor model we modeled is a simplification of the processor model used in SimpleScalar sim-outorder simulator. Let the source program to be analyzied be denoted as <benchmark>.c. Our tool works as follows:

  1. First, <benchmark>.c is compiled into the binary code <benchmark> by the GCC came with SimpleScalar toolset. This GCC version yields code of an instruction set architecture (ISA) which is a superset of MIPS ISA
  2. Our tool reads in the binary code, reconstructs the control flow graphs (CFG) for the functions in <benchmark>. The CFGs can be dumped into a file named <benchmark> in the same directory as the source program. The program flow paths are reprensented as linear constraints which are called "flow constraints". In addition, our tool allows the user to input constraints such as loop bounds and some other flow facts through a graphical interface, and these constraints are called "user constraints". This step corresponds to the program path analysis introduced earlier (the "PA" in the corresponding circle on the diagram stands for Path Analysis).
  3. Based on the processor model, which can be configured by user via the graphical interface, our tool performs microarchitecture modeling, which (1) yields timing information for basic blocks of the program subject to some execution contexts; (2) constraints on the occurrences of execution contexts (instruction cache state, branch prediction information, etc.). Combined with the flow constraints and user constaints, a complete Integer Linear Programming (ILP) problem is formualted by our tool, and the corresponding output is <benchmark>.lp.
  4. The tool invokes either CPLEX, a high-performance commercial ILP solver, or lp_solve, a free LP solver
    5. , to solve the ILP problem and yields a result, which is the estimated WCET.
  5. In addition to the estimated WCET, an observed WCET can be obtained via simulation using the sim-outorder simulator in the SimpleScalar toolset using the same processor configuration used in the estimation. Note we have made some changes to the original sim-outorder simulator since (1) some of the simplifications assumed in our estimation cannot be simply realized via the configuration of the processor model (some of the processor configurations have been hardcoded into the sim-outorder simulator so we have to change the code to ensure that the simulation and the estimation are consistent in regard to the processor models); (2) the timing information as well as other statistics by sim-outorder also take into account the library code befor/after the execution of the program, but our estimation does not consider such library code, thus sim-outorder needs to be modified to exclude them from the simulation time.