Static performance prediction of data-dependent programs
Hasyim Gautama, Arjan J. C. van Gemund · 2000
Static program performance prediction has been less successful in providing information on the distribution of execution times when considering a large space of input data sets. Typically, low-cost performance analysis techniques model system parameters in terms of deterministic variables, ignoring the fact that most of these parameters are stochastic due to data dependencies in programs. In this paper we present a symbolic program performance prediction approach based on characterizing loop bounds and branch probabilities, as well as basic block execution time delays in terms of their statistical moments, which reect the data-dependent behavior of these parameters. Our compositional approach allows for a low-cost analysis yielding the statistical moments of the overall program execution time distribution. We present the approach and report on its application to two small example codes.