Analysis of correlation and predictability: what makes two-level branch predictors work

Marius Evers, Sanjay Jeram Patel, Robert S. Chappell, Yale N. Patt

Research output: Contribution to journalArticlepeer-review


Pipeline flushes due to branch mispredictions is one of the most serious problems facing the designer of a deeply pipelined, superscalar processor. Many branch predictors have been proposed to help alleviate this problem, including two-level adaptive branch predictors and hybrid branch predictors. Numerous studies have shown which predictors and configurations best predict the branches in a given set of benchmarks. Some studies have also investigated effects, such as pattern history table interference, that can be detrimental to the performance of these predictors. However, little research has been done on which characteristics of branch behavior make predictors perform well. In this paper, we investigate and quantify reasons why branches are predictable. We show that some of this predictability is not captured by the two-level adaptive branch predictors. An understanding of the predictability of branches may lead to insights ultimately resulting in better or less complex predictors. We also investigate and quantify what fraction of the branches in each benchmark is predictable using each of the methods described in this paper.

Original languageEnglish (US)
Pages (from-to)52-61
Number of pages10
JournalConference Proceedings - Annual International Symposium on Computer Architecture, ISCA
StatePublished - 1998
Externally publishedYes

ASJC Scopus subject areas

  • Hardware and Architecture


Dive into the research topics of 'Analysis of correlation and predictability: what makes two-level branch predictors work'. Together they form a unique fingerprint.

Cite this