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

ABSTRACT

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.

REFERENCES

• 1: Po-Yung Chang , Eric Hao , Tse-Yu Yeh , Yale Patt, Branch classification: a new mechanism for improving branch predictor performance, Proceedings of the 27th annual international symposium on Microarchitecture, p.22-31, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192727]
• 2: S. McFarling, "Combining branch predictors," Technical Report TN-36, Digital Western Research Laboratory, June 1993.
• 3: Ravi Nair, Dynamic path-based branch correlation, Proceedings of the 28th annual international symposium on Microarchitecture, p.15-23, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 4: Shien-Tai Pan , Kimming So , Joseph T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.76-84, October 12-15, 1992, Boston, Massachusetts, United States
• 5: Stuart Sechrest , Chih-Chieh Lee , Trevor Mudge, The role of adaptivity in two-level adaptive branch prediction, Proceedings of the 28th annual international symposium on Microarchitecture, p.264-269, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 6: Stuart Sechrest , Chih-Chieh Lee , Trevor Mudge, Correlation and aliasing in dynamic branch predictors, Proceedings of the 23rd annual international symposium on Computer architecture, p.22-32, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 7: Pierre Michaud , André Seznec , Richard Uhlig, Trading conflict and capacity aliasing in conditional branch predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.292-303, June 01-04, 1997, Denver, Colorado, United States
• 8: James E. Smith, A study of branch prediction strategies, Proceedings of the 8th annual symposium on Computer Architecture, p.135-148, May 12-14, 1981, Minneapolis, Minnesota, United States
• 9: Adam R. Talcott , Mario Nemirovsky , Roger C. Wood, The influence of branch prediction table interference on branch prediction scheme performance, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.89-98, June 27-29, 1995, Limassol, Cyprus
• 10: Tse-Yu Yeh , Yale N. Patt, Two-level adaptive training branch prediction, Proceedings of the 24th annual international symposium on Microarchitecture, p.51-61, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123475]
• 11: Tse-Yu Yeh , Yale N. Patt, Alternative implementations of two-level adaptive branch prediction, Proceedings of the 19th annual international symposium on Computer architecture, p.124-134, May 19-21, 1992, Queensland, Australia
• 12: Cliff Young , Nicolas Gloy , Michael D. Smith, A comparative analysis of schemes for correlated branch prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.276-286, June 22-24, 1995, S. Margherita Ligure, Italy

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Modeling of computer architecture
  C.1 PROCESSOR ARCHITECTURES