A Taxonomy of Branch Mispredictions, and Alloyed Prediction as a Robust Solution to Wrong-History Mispredictions

K. Skadron, M. Martonosi, and D.W. Clark
In Proc. of the 2000 International Conference on Parallel Architectures and Compilation Techniques, Oct., 2000.

The need for accurate conditional-branch prediction is well known: mispredictions waste large numbers of cycles, inhibit out-of-order execution, and waste power on mis-speculated computation. Prior work on branch-predictor organization has focused mainly on how to reduce conflicts in the branch-predictor structures, while relatively little work has explored other causes of mispredictions. Some prior work has identified other categories of mispredictions, but this paper organizes these categories into a broad taxonomy of misprediction types. Using the taxonomy, this paper goes on to show that other categories--especially wrong-history mispredictions--are often more important than conflicts. This is true even if just a very simple conflict-reduction technique is used. Based on these observations, this paper proposes alloying local and global history together in a two-level branch predictor structure. This simple technique, a generalization of the bi-mode predictor, attacks wrong-history mispredictions by making both global and local history simultaneously available. Unlike hybrid prediction, however, alloying gives robust performance for branch-predictor hardware budgets ranging from very large to very small. Finally, this paper shows that individual branch references can also suffer wrong-history mispredictions as they alternate between using global and local history, a phenomenon that favors dynamic rather than static selection in hybrid predictors.

Available in postscript or pdf