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

ACM SIGARCH Computer Architecture News, Volume 23, Issue 2

Pages 276 - 286

https://doi.org/10.1145/225830.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

Alajmi AAlSarraf BAbualhassan ZFairouz AAhmad I(2024)TinyBERT for branch prediction in modern microprocessorsNeural Computing and Applications10.1007/s00521-024-10535-137:4(1771-1782)Online publication date: 20-Nov-2024
https://doi.org/10.1007/s00521-024-10535-1
Khan TUgur MNathella KSunwoo DLitz HJiménez DKasikci BHardavellas NCampanoni SGrot BKarpuzcu U(2022)Whisper: Profile-Guided Branch Misprediction Elimination for Data Center ApplicationsProceedings of the 55th Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO56248.2022.00017(19-34)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/MICRO56248.2022.00017
Nain SChaudhary P(2021)Implementation and comparison of bi-modal dynamic branch prediction with static branch prediction schemesInternational Journal of Information Technology10.1007/s41870-021-00631-zOnline publication date: 11-Mar-2021
https://doi.org/10.1007/s41870-021-00631-z
Show More Cited By

Recommendations

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

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 SIGARCH Computer Architecture News

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

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

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 May 1995

Published in SIGARCH Volume 23, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

147
Total Citations
View Citations
1,050
Total Downloads

Downloads (Last 12 months)164
Downloads (Last 6 weeks)22

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Alajmi AAlSarraf BAbualhassan ZFairouz AAhmad I(2024)TinyBERT for branch prediction in modern microprocessorsNeural Computing and Applications10.1007/s00521-024-10535-137:4(1771-1782)Online publication date: 20-Nov-2024
https://doi.org/10.1007/s00521-024-10535-1
Khan TUgur MNathella KSunwoo DLitz HJiménez DKasikci BHardavellas NCampanoni SGrot BKarpuzcu U(2022)Whisper: Profile-Guided Branch Misprediction Elimination for Data Center ApplicationsProceedings of the 55th Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO56248.2022.00017(19-34)Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1109/MICRO56248.2022.00017
Nain SChaudhary P(2021)Implementation and comparison of bi-modal dynamic branch prediction with static branch prediction schemesInternational Journal of Information Technology10.1007/s41870-021-00631-zOnline publication date: 11-Mar-2021
https://doi.org/10.1007/s41870-021-00631-z
Chang PEvers MPatt Y(1997)Improving branch prediction accuracy by reducing pattern history table interferenceInternational Journal of Parallel Programming10.1007/BF0269988225:5(339-362)Online publication date: 1-Oct-1997
https://dl.acm.org/doi/10.1007/BF02699882
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
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

Figures

Tables

Media

View Issue’s Table of Contents