Software Timing Analysis

Timing Analysis of software to estimate an upper bound on the execution time is an important problem for designing safety critical  real-time systems. This problem is also known as the worst-case execution time (WCET) analysis -- using program analysis/verification techniques to find an safe upper bound to a program's execution time. The WCET estimate of a program is useful for finding out whether all timing constraints of a real-time embedded system can be met. In this tutorial, we will introduce the problem of WCET analysis and give an overview of the state-of-the art techniques. We will start with timing analysis of a single sequential program. The two main components of this analysis are path analysis (for detecting infeasible paths) and modeling the timing effects of micro-architectural features (cache/pipeline). We will discuss the different existing approaches based on Abstract Interpretation, Linear Constraint solving etc. Pragmatic issues such as scalability and performance of WCET analysis techniques will be discussed. We will conclude with a discussion on open issues and research directions in timing analysis.

Schedule:

1. What is Timing Analysis ?
   　
2. The two steps for performing timing analysis
   • Language level analysis
   • Micro-architectural modeling
     　
3. Integration of the two steps
   • Separation of concerns through abstract interpretation
   • Integrated approach based on Integer Linear Programming (ILP)
   • Issues in adopting a Model Checking based Solution
     　
4. Programming language level analysis
   • Early solutions e.g. Timing schema
   • Detecting infeasible paths in a program
   • Exploiting infeasible path information for WCET Calculation
     　
5. Micro-architectural modeling for a given program
   • Cache modeling by Abstract Interpretation and/or ILP
   • Modeling pipelines (in-order and out-of-order)
   • Difficulty in integrating different features  (Non compositional analysis due to Timing anomaly problem)
   • Existing solutions for integrated modeling
     　
6.  Overall Summary and discussion

Some References:

1. Chang Yun Park: Predicting Program Execution Times by Analyzing Static and Dynamic Program Paths. Real-Time Systems 5(1): 31-62 (1993)
   　

2. Martin Alt, Christian Ferdinand, Florian Martin, Reinhard Wilhelm: Cache Behavior Prediction by Abstract Interpretation. Science of Computer Programming 1998, Initial Version in Static Analysis Symposium (SAS) 1996.
   　

3. C. Healy and D. Whalley. Automatic Detection and Exploitation of Branch Constraints for Timing Analysis, IEEE Transactions on Software Engineering, August 2002, pages 763-781.
   　

4. Xianfeng Li, Abhik Roychoudhury, Tulika Mitra: Modeling Out-of-Order Processors for Software Timing Analysis. IEEE Real-Time Systems Symposium (RTSS) 2004: 92-103