More Web Proxy on the site http://driver.im/

Article

Free access

A comparative analysis of schemes for correlated branch prediction

Authors:

Michael D. SmithAuthors Info & Claims

ISCA '95: Proceedings of the 22nd annual international symposium on Computer architecture

Pages 276 - 286

https://doi.org/10.1145/223982.224438

Published: 01 May 1995 Publication History

Abstract

Modern high-performance architectures require extremely accurate branch prediction to overcome the performance limitations of conditional branches. We present a framework that categorizes branch prediction schemes by the way in which they partition dynamic branches and by the kind of predictor that they use. The framework allows us to compare and contrast branch prediction schemes, and to analyze why they work. We use the framework to show how a static correlated branch prediction scheme increases branch bias and thus improves overall branch prediction accuracy. We also use the framework to identify the fundamental differences between static and dynamic correlated branch prediction schemes. This study shows that there is room to improve the prediction accuracy of existing branch prediction schemes.

References

[1]

V. Bala, personal communication, Oct. 1994.

[2]

T. Ball and J. Larus, "Branch Prediction for Free," Proc. ACM SIGPLAN 1993 Conf. on Prog. Lang. Destgn and Implementation, Jun. 1993.

Digital Library

[3]

J. Bentley, Programming Pearls, Addison-Wesley, 1986.

[4]

R Chang, E. Hao, T. Yeh, and Y. Patt, "'Branch Classification: a New Mechanism for Improving Branch Predictor Performance," in Proc. 27th Annual A CM/IEEE intl. Syrup. and Workshop on Microarchitecture, November 1994.

Digital Library

[5]

J. Fisher and S. Freudenberger, "Predicting Conditional Branch Directions From Previous Runs of a Program," Proc. 5th Annual Intl. Conf. on Architectural Support for Prog. Lang. and Operating Systems, Oct. 1992.

Digital Library

[6]

W. Hwu and R Chang, "Inlining Function Expansion for Compiling C Programs," Proc. A CM SIGPLAN 1989 Conf. on Prog. Lang. Design and Implementation, Jun. 1989.

Digital Library

[7]

J. Lee and A. Smith, "Branch Prediction Strategies and Branch Target Buffer Design," Computer, 17(1), Jan. 1984.

[8]

S. Mahlke, et al., "Characterizing the Impact of Predicated Execution on Branch Prediction," Proc. 27th Annual Intl. Syrup. on Microarchitecture, Nov, 1994.

Digital Library

[9]

S. McFarling, "Combining Branch Predictors," WRL Technical Note TN-36, June 1993.

[10]

S. McFarling and J. Hennessy, "Reducing the Cost of Branches," Proc. of 13th Annual Intl. Symp. on Computer Architecture, Jun. 1986.

Digital Library

[11]

S. Pan, K. So, and J. Rahmeh, "Improving the Accuracy of Dynamic Branch Prediction Using Branch Correlation," Proc. 5th Annual Intl. Conf. on Architectural Support for Prog. Lang. and Operating Systems, Oct. 1992.

Digital Library

[12]

J. Smith, "A Study of Branch Prediction Strategies," Proc. 8th Annual Intl. Symp. on Computer Architecture, Jun. 1981.

Digital Library

[13]

A. Srivastava and A. Eustace, "ATOM: A System for Building Customized Program Analysis Tools," Proc. SIGPLAN '94 Conf. on Prog. Lang. Design and Implementation, Jun. 1994.

Digital Library

[14]

T. Yeh and Y. Patt, "Two-Level Adaptive Branch Prediction," Proc. 24th Annual A CM/IEEE Intl. Symp. and Workshop on Microarchitecture, Nov. 1991.

Digital Library

[15]

T. Yeh and Y. Part, "A Comparison of Dynamic Branch Predictors that use Two Levels of Branch History," Proc. 20th Annual Intl. Syrup. on Computer Architecture, May 1993.

Digital Library

[16]

T. Yeh, "Two-Level Adaptive Branch Prediction and Instruction Fetch Mechanisms for High Performance Superscalar Processors," Computer Science and Engineering Div. Tech. Report CSE-TR-182-93. Univ. of Michigan, Ann Arbor, MI, Oct. 1993.

[17]

C. Young and M. Smith, "Improving the Accuracy of Static Branch Prediction Using Branch Correlation," Proc. 6th Annual Intl. Conf. on Architectural Support for Prog. Lang. and Operating Systems, October 1994.

Digital Library

[18]

C. Young, N. Gloy, and M. Smith, "A Comparative Analysis of Schemes for Correlated Branch Prediction," Technical Report 06-95, Center for Research in Computing Technology, Harvard University, Cambridge, MA, Mar. 1995.

Digital Library

Cited By

Kuo HChen KLu YWilliams DMohan SXu TBromberg YKermarrec AKozyrakis C(2022)Verified programs can partyProceedings of the Seventeenth European Conference on Computer Systems10.1145/3492321.3519562(283-299)Online publication date: 28-Mar-2022
https://dl.acm.org/doi/10.1145/3492321.3519562
Møller NBossen CPine KNielsen TNeff G(2020)Who does the work of data?Interactions10.1145/338638927:3(52-55)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3386389
Taylor JSherman S(2020)Designing a design-a-hack-a-thonInteractions10.1145/338638727:3(56-60)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3386387
Show More Cited By

Index Terms

A comparative analysis of schemes for correlated branch prediction
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
2. Theory of computation
  1. Logic
  2. Semantics and reasoning
    1. Program constructs

Recommendations

A comparative analysis of schemes for correlated branch prediction
Special Issue: Proceedings of the 22nd annual international symposium on Computer architecture (ISCA '95)

Modern high-performance architectures require extremely accurate branch prediction to overcome the performance limitations of conditional branches. We present a framework that categorizes branch prediction schemes by the way in which they partition ...
Static correlated branch prediction

Recent work in history-based branch prediction uses novel hardware structures to capture branch correlation and increase branch prediction accuracy. Branch correlation occurs when the outcome of a conditional branch can be accurately predicted by ...
Improving branch prediction by understanding branch behavior

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '95: Proceedings of the 22nd annual international symposium on Computer architecture

July 1995

426 pages

ISBN:0897916980

DOI:10.1145/223982

Chairman:
David A. Patterson
Univ. of California, Berkeley

ACM SIGARCH Computer Architecture News Volume 23, Issue 2
Special Issue: Proceedings of the 22nd annual international symposium on Computer architecture (ISCA '95)
May 1995
412 pages
ISSN:0163-5964
DOI:10.1145/225830
Chairman:
David A. Patterson
Univ. of California, Berkeley
Issue’s Table of Contents

Copyright © 1995 ACM.

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

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS\TCCA: TC on Computer Arhitecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISCA95

Sponsor:

SIGARCH
IEEE-CS\TCCA

ISCA95: International Conference on Computer Architecture

June 22 - 24, 1995

S. Margherita Ligure, Italy

Acceptance Rates

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

145
Total Citations
View Citations
1,027
Total Downloads

Downloads (Last 12 months)156
Downloads (Last 6 weeks)18

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kuo HChen KLu YWilliams DMohan SXu TBromberg YKermarrec AKozyrakis C(2022)Verified programs can partyProceedings of the Seventeenth European Conference on Computer Systems10.1145/3492321.3519562(283-299)Online publication date: 28-Mar-2022
https://dl.acm.org/doi/10.1145/3492321.3519562
Møller NBossen CPine KNielsen TNeff G(2020)Who does the work of data?Interactions10.1145/338638927:3(52-55)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3386389
Taylor JSherman S(2020)Designing a design-a-hack-a-thonInteractions10.1145/338638727:3(56-60)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3386387
Bennett CKeyes O(2020)What is the point of fairness?Interactions10.1145/338638327:3(35-39)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3386383
Harrington C(2020)The forgotten marginsInteractions10.1145/338638127:3(24-29)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3386381
Taib RBerkovsky S(2020)Modeling humans via physiological and behavioral signalsInteractions10.1145/338623727:3(30-34)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3386237
Ananthanarayan SBoll S(2020)Physical computing for childrenInteractions10.1145/338623527:3(40-45)Online publication date: 17-Apr-2020
https://dl.acm.org/doi/10.1145/3386235
Garza EMirbagher-Ajorpaz SKhan TJiménez DManne SHunter HAltman E(2019)Bit-level perceptron prediction for indirect branchesProceedings of the 46th International Symposium on Computer Architecture10.1145/3307650.3322217(27-38)Online publication date: 22-Jun-2019
https://dl.acm.org/doi/10.1145/3307650.3322217
Pandey A(2019)Resolving Control Hazard by Reconstituting Processor's Pipeline Organization2019 Third International Conference on Inventive Systems and Control (ICISC)10.1109/ICISC44355.2019.9036414(201-206)Online publication date: Jan-2019
https://doi.org/10.1109/ICISC44355.2019.9036414
Sweety Chaudhary P(2019)Implemented Static Branch Prediction Schemes for the Parallelism Processors2019 International Conference on Machine Learning, Big Data, Cloud and Parallel Computing (COMITCon)10.1109/COMITCon.2019.8862216(79-83)Online publication date: Feb-2019
https://doi.org/10.1109/COMITCon.2019.8862216
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents