Alloyed Global and Local Branch History: A Robust Solution to Wrong-History Misprediction

Abstract:

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.

Wrong-history mispredictions arise because current two-level,
history-based predictors provide only global or only local history.
Their contribution to the overall misprediction rate is substantial
because most programs have some branches that require global history
and also some that require local history. If only one or the other type of
history is available, many branches are therefore penalized. For
SPECint95 programs using a global-history predictor, wrong-history
mispredictions account for 35--50% of the total
misprediction rate. By comparison, conflicts only account for
15-20%. Hybrid predictors are one proposed solution; they use both a
global-history and a local-history component. Unfortunately, hybrid
predictors only work well with large hardware budgets, because they
must subdivide the available area into subcomponents.

Based on these observations, this paper proposes alloying local
and global history together in a two-level branch predictor structure.
This is a simple but superior technique for making global and local
history simultaneously available and eliminating wrong-history
mispredictions. Unlike hybrid prediction, alloying gives robust
performance for branch-predictor hardware budgets ranging from very large
to very small. Alloying also consistently outperforms other two-level
organizations. In fact, a small alloyed predictor often performs as
well as a much larger global-history predictor.