Software Timing Analysis 



Presenter: 

Abhik Roychoudhury
School of
Computing
National University of
Singapore 


Date: 

1 November, 2005 (Afternoon session) with ICFEM'05


Outline: 

Timing Analysis of software to
estimate an upper bound on the execution time is an important
problem for designing safety critical realtime systems. This
problem is also known as the worstcase 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 realtime embedded system can be met. In this
tutorial, we will introduce the problem of WCET analysis and give an
overview of the stateofthe 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
microarchitectural 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: 

What is Timing Analysis
?

The two
steps for performing timing analysis

Language level
analysis

Microarchitectural
modeling

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

Programming language level analysis
 Early solutions e.g. Timing
schema
 Detecting infeasible paths in a program
 Exploiting infeasible path information for WCET
Calculation

Microarchitectural modeling for a
given program
 Cache modeling by Abstract Interpretation and/or ILP
 Modeling pipelines (inorder and
outoforder)
 Difficulty in integrating different features (Non compositional analysis due to
Timing anomaly
problem)
 Existing solutions for integrated
modeling
 Overall
Summary and discussion


Some
References: 

Chang Yun
Park: Predicting Program Execution Times by Analyzing Static and Dynamic Program
Paths. RealTime Systems 5(1): 3162 (1993)

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.

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

Xianfeng Li,
Abhik Roychoudhury, Tulika Mitra:
Modeling
OutofOrder Processors for Software Timing Analysis. IEEE RealTime
Systems Symposium (RTSS) 2004: 92103

