Autocorrelation analysis: A new and improved method for branch predictability characterization

Branch predictability characterization not only helps to improve branch prediction but also helps to optimize predicated execution. Branch taken rate and branch transition rate have been proposed to characterize the branch predictability. However, these two metrics may misclassify branches with regular history patterns as hard-to-predict branches, causing an inaccurate and ambiguous view of branch predictability. In this paper, we utilize autocorrelation based analysis of branch history patterns and present two orthogonal metrics Degree of Pattern Irregularity (DPI) and Effective Pattern Length (EPL). Unlike the existing taken rate or transition rate, DPI directly measures the regularity of the patterns in per-address branch history, and hence is more accurate in branch classification. On the other hand, EPL reveals the optimum branch history length for the easy-to-predict branches. The proposed metrics are evaluated with PAs, GAs, and Perceptron branch predictors, and the results show that on average, DPI improves the accuracy of hard-to-predict branch classification by up to 17.7% over taken rate and 15.0% over transition rate for the workloads in this study. It is also able to identify 18.9% more easy-to-predict branches compared with taken rate and 12.8% more compared with transition rate. The proposed metrics are valuable extension to the existing metrics for accurately characterizing branch predictability.