Predicting Program Execution Times by Analyzing Static and Dynamic Program Paths

Predicting Program Execution Times by Analyzing Static and Dynamic Program Paths

Abstract

This paper describes a method to predict guaranteed and tight
deterministic execution time bounds of a program. The basic prediction
technique is a static analysis based on simp[le timing schema for
source-level language constructs, which gives accurate predictions in
many cases. Using powerful user-provided information, dynamic path
analysis refines looser predictions by eliminating infeasible paths
and decomposing the possible execution behaviors in a path wise
manner. Overall prediction cost is scalable with respect to desired
precision, controlling the amount of information provided. We
introduce a formal path model for dynamic path analysis, where user
execution information is represented bu a set of program paths. With a
well-defined practical high-level interface language, user information
can be used in an easy and efficient way. We also introduce a method
to verify given user information with known program verification
techniques. Initial experiments with a timing tool show that safe and
tight predictions are possible for a wide range of programs. The tool
can also provide predictions for interesting subsets of program
executions.