Taxonomy of branch mispredictions, and alloyed prediction as a robust solution to wrong-history mispredictions

Kevin Skadron, Margaret Rose Martonosi, Douglas W. Clark

Research output: Contribution to journalConference articlepeer-review

23 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)199-206
Number of pages8
JournalParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
StatePublished - 2000
Event2000 International Conference on Parallel Architectures and Compilation Techniques - Philadelphia, PA, USA
Duration: Oct 15 2000Oct 19 2000

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Taxonomy of branch mispredictions, and alloyed prediction as a robust solution to wrong-history mispredictions'. Together they form a unique fingerprint.

Cite this