[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/192724.192727acmconferencesArticle/Chapter ViewAbstractPublication PagesmicroConference Proceedingsconference-collections
Article
Free access

Branch classification: a new mechanism for improving branch predictor performance

Published: 30 November 1994 Publication History

Abstract

There is wide agreement that one of the most important impediments to the performance of current and future pipelined superscalar processors is the presence of conditional branches in the instruction stream. Speculative execution seems to be one solution of choice to the branch problem, but speculative work is discarded if a branch is mispredicted. Therefore, we need a very accurate branch predictor; 95% accuracy is not good enough. This paper proposes branch classification to help improve the accuracy of branch predictors. Branch classification allows an individual branch instruction to be associated with the branch predictor best suited to predict its direction. Using this approach, a hybrid branch predictor can be constructed such that each component branch predictor predicts those branches for which it is best suited. This paper suggests one classification scheme, analyzes several branch predictors, and proposes a hybrid branch predictor that achieves higher prediction accuracy than any branch predictor previously reported in the literature.

References

[1]
P. Chow and M. Horowitz, "Architecture tradeoffs in the design of MIPS-X," Proceedings of the 14th Annual International Symposium on Computer Architecture, June 1987.
[2]
J.A. DeRosa and H. M. Levy, "An Evaluation of Branch Architectures," Proceedings of the 1.1th International Symposium on Computer Architecture, May 1989.
[3]
J. Emer and D. Clark, "A Characterization of Processor Performance in the VAX-11/780," Proceedings of the 1lib Annual Symposium on Computer Architecture, June 1984.
[4]
P.M. Kogge, The Architecture of Pipelined Computers, pp.237-243, McGraw-Hill, 1981.
[5]
J.K.F. Lee and A.J. Smith, "Branch Prediction Strategies and Branch Target Buffer Design," IEEE Computer, pp.6-22, january 1984.
[6]
S. McFarling, "Combining Branch Predictors", WRL Technical Note TN-36, Digital Equipment Corporation, June 1993.
[7]
S. McFarling and J.L. Hennessey, "Reducing the cost of branches," Proceedings of the 13th international Symposium on Computer Architecture, pp.396-404, June 1986.
[8]
C. Melear, "The design of the 88000 RISC family," IEEE MICRO, pp.26-38, April 1989.
[9]
J.E. Smith, "A Study of Branch Prediction Strategies,'' Proceedings of the 8th International Symposium on Computer Architecture, pp.135-148, June 1981.
[10]
T.-Y. Yeh and Y.N. Patt, "Alternative Implementations of Two-level Adaptive Branch Prediction," Proceedings of the 19th Annual International Symposium on Computer Architecture, pp.124-135, May 1992.
[11]
T.-Y. Yeh and Y.N. Patt, "Two-level Adaptive Branch Prediction," Proceedings of the ~dth ACM/IEEE International Symposium on Microarchitecture, pp.51-61, November 1991.
[12]
T.-Y. Yeh and Y.N. Patt, "A Comparison of Dynamic Branch Predictors that use Two Levels of Branch History", Proceedings of the ~Oth Annual International Symposium on Computer Architecture, pp.257-266, May 1993.

Cited By

View all
  • (2023)BATAGE-BFNP: A High-Performance Hybrid Branch Predictor with Data-Dependent Branches Speculative Pre-execution for RISC-V ProcessorsArabian Journal for Science and Engineering10.1007/s13369-022-07593-948:8(10299-10312)Online publication date: 10-Jan-2023
  • (2020)Energy Efficient On-Demand Dynamic Branch Prediction ModelsIEEE Transactions on Computers10.1109/TC.2019.295671069:3(453-465)Online publication date: 1-Mar-2020
  • (2018)An Alternative TAGE-like Conditional Branch PredictorACM Transactions on Architecture and Code Optimization10.1145/322609815:3(1-23)Online publication date: 28-Aug-2018
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
MICRO 27: Proceedings of the 27th annual international symposium on Microarchitecture
November 1994
233 pages
ISBN:0897917073
DOI:10.1145/192724
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 November 1994

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. branch classification
  2. branch predictor
  3. processor performance
  4. speculative execution
  5. superscalar

Qualifiers

  • Article

Conference

MICRO94
Sponsor:
MICRO94: 27th Annual International Symposium on Microarchitecture
November 30 - December 2, 1994
California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)200
  • Downloads (Last 6 weeks)21
Reflects downloads up to 30 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2023)BATAGE-BFNP: A High-Performance Hybrid Branch Predictor with Data-Dependent Branches Speculative Pre-execution for RISC-V ProcessorsArabian Journal for Science and Engineering10.1007/s13369-022-07593-948:8(10299-10312)Online publication date: 10-Jan-2023
  • (2020)Energy Efficient On-Demand Dynamic Branch Prediction ModelsIEEE Transactions on Computers10.1109/TC.2019.295671069:3(453-465)Online publication date: 1-Mar-2020
  • (2018)An Alternative TAGE-like Conditional Branch PredictorACM Transactions on Architecture and Code Optimization10.1145/322609815:3(1-23)Online publication date: 28-Aug-2018
  • (2018)A survey of techniques for dynamic branch predictionConcurrency and Computation: Practice and Experience10.1002/cpe.466631:1Online publication date: 2-Sep-2018
  • (2017)Linear Branch EntropyIEEE Transactions on Computers10.1109/TC.2016.260132366:3(458-472)Online publication date: 1-Mar-2017
  • (2017)An empirical study on performance of branch predictors with varying storage budgets2017 7th International Symposium on Embedded Computing and System Design (ISED)10.1109/ISED.2017.8303913(1-5)Online publication date: Dec-2017
  • (2015)On-Demand Dynamic Branch PredictionIEEE Computer Architecture Letters10.1109/LCA.2014.233082014:1(50-53)Online publication date: 1-Jan-2015
  • (2015)Micro-architecture independent branch behavior characterization2015 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS.2015.7095792(135-144)Online publication date: Mar-2015
  • (2012)Design space exploration of hybrid ultra low power branch predictorsProceedings of the 25th international conference on Architecture of Computing Systems10.1007/978-3-642-28293-5_16(184-199)Online publication date: 28-Feb-2012
  • (2011)Autocorrelation analysisACM SIGMETRICS Performance Evaluation Review10.1145/2007116.200716939:1(345-346)Online publication date: 7-Jun-2011
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media