Static methods in hybrid branch prediction

Abstract

Hybrid branch predictors combine the predictions of multiple single-level or two-level branch predictors. The prediction-combining hardware-the meta-predictor-may itself be large, complex and slow. We show that the combination function is better performed statically, using prediction hints in the branch instructions. The hints are set by profiling or static analysis. Although the meta-predictor is static, the actual predictions remain dynamic, so there is little risk of worst-case performance. An important advantage of our approach is that a branch site only causes interference within a single component predictor reducing capacity demands. We argue that our proposal is implementable, and that it addresses the scaling issues currently facing hardware designers. We show that the static hybrid method we propose is more effective than existing techniques based on dynamic selection, and requires less hardware. For example, one result shows a conventional 4096-bit dynamic selection mechanism getting a 4.7% average miss rate, while our static approach gets 3.6%. These results are obtained with the Instruction Benchmark Suite (IBS), a realistic whole-system benchmark, and the SPECint95 suite, using realistic hardware sizes. All the results we present are based on a cross-validation methodology, in which the profile data used for static selection are based on training inputs that are entirely different from the inputs used to evaluate the performance of the technique.