A statistical approach to branch modeling in static program performance prediction

Current static performance prediction methods have been less successful in statistically accounting for program workload distribution due to input data set variability, of which data-dependent branches are usually the most important contributors. While data-dependent basic block execution time is often characterized in terms of, e.g., mean and variance, branching conditions still are typically characterized by only one parameter, usually known as the truth probability. We propose and evaluate three statistical approaches to modeling branching behavior, to be used within a compositional method to predict program execution time distribution. The approaches are coined the empirical, the Bernoulli, and the ARP (Alternating Renewal Processes) approach. While the Empirical approach is based on measuring branching behavior in terms of the surrounding loop construct, the other approaches aim at deriving a statistical model of the branch itself, which enables a higher level of compositionality. Our measurement results, based on synthetic as well as on real programs, show that the Empirical approach delivers the highest accuracy, whereas the alternative approaches trade accuracy for compositionality. For Markovian branches, the compositional approaches deliver high prediction accuracy. In contrast to intuition and our synthetic experiments, in real programs the two-parameter ARP approach does not always outperform the one-parameter Bernoulli approach.