Alloying Global and Local Branch History: Taxonomy, Performance, and Analysis

Abstract:

The need for accurate conditional-branch prediction is well known;
mispredictions waste large numbers of cycles and also waste power on
mis-speculated computation. A number of studies have explored ways to
improve the prediction accuracy of two-level predictors, but have
considered exclusively global or local history. Because most programs
benefit from having both global and local history available, other
work has proposed hybrid predictors that combine a global-history with
a local-history component.

Building on prior work that categorizes the types of branch
mispredictions, this paper presents a taxonomy of
mispredictions. Using the taxonomy, the paper shows why a two-level
predictor that alloys local and global history in the same
predictor index provides superior performance. By making both types of
history available all the time, an alloyed scheme obtains accuracies
competitive with hybrid schemes, even though organized like
conventional two-level predictors. Alloying has the advantage that it
eliminates the need to make a choice between components, since the
history types are merged. For large predictors used in
high-performance processors, an alloyed organization provides
competitive performance that suffers less variation from program to
program than alternatives. For the smaller predictors needed in
space- and power-constrained environments, alloying outperforms alternative
organizations.