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

article

Neural methods for dynamic branch prediction

Authors:

Daniel A. Jiménez,

Calvin LinAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 20, Issue 4

Pages 369 - 397

https://doi.org/10.1145/571637.571639

Published: 01 November 2002 Publication History

Abstract

This article presents a new and highly accurate method for branch prediction. The key idea is to use one of the simplest possible neural methods, the perceptron, as an alternative to the commonly used two-bit counters. The source of our predictor's accuracy is its ability to use long history lengths, because the hardware resources for our method scale linearly, rather than exponentially, with the history length. We describe two versions of perceptron predictors, and we evaluate these predictors with respect to five well-known predictors. We show that for a 4 KB hardware budget, a simple version of our method that uses a global history achieves a misprediction rate of 4.6% on the SPEC 2000 integer benchmarks, an improvement of 26% over gshare. We also introduce a global/local version of our predictor that is 14% more accurate than the McFarling-style hybrid predictor of the Alpha 21264. We show that for hardware budgets of up to 256 KB, this global/local perceptron predictor is more accurate than Evers' multicomponent predictor, so we conclude that ours is the most accurate dynamic predictor currently available. To explore the feasibility of our ideas, we provide a circuit-level design of the perceptron predictor and describe techniques that allow our complex predictor to operate quickly. Finally, we show how the relatively complex perceptron predictor can be used in modern CPUs by having it override a simpler, quicker Smith predictor, providing IPC improvements of 15.8% over gshare and 5.7% over the McFarling hybrid predictor.

References

[1]

Ball, T. and Larus, J. 1993. Branch prediction for free. In Proceedings of the SIGPLAN '93 Conference on Programming Language Design and Implementation, 300--313.

[2]

Block, H. D. 1962. The perceptron: A model for brain functioning. Rev. Mod. Phy. 34, 123--135.

[3]

Burger, D. and Austin, T. M. 1997. The SimpleScalar tool set version 2.0. Tech. Rep. 1342, Computer Sciences Department, University of Wisconsin. June.

[4]

Calder, B., Grunwald, D., Jones, M., Lindsay, D., Martin, J., Mozer, M., and Zorn, B. 1997. Evidence-based static branch prediction using machine learning. ACM Trans. Program. Lang. Syst. 19, 1, 188--222.

[5]

Cormen, T. H., Leiserson, C. E., and Rivest, R. L. 1990. Introduction to Algorithms. McGraw-Hill, New York.

[6]

Eden, A. and Mudge, T. 1998. The YAGS branch prediction scheme. In Proceedings of the 31st Annual ACM/IEEE International Symposium on Microarchitecture, 69--80.

[7]

Emer, J. and Gloy, N. 1997. A language for describing predictors and its application to automatic synthesis. In Proceedings of the 24th International Symposium on Computer Architecture, 304--314.

[8]

Evers, M. 2000. Improving branch prediction by understanding branch behavior. PhD Thesis, University of Michigan, Department of Computer Science and Engineering.

[9]

Evers, M., Patel, S. J., Chappell, R. S., and Patt, Y. N. 1998. An analysis of correlation and predictability: What makes two-level branch predictors work. In Proceedings of the 25th Annual International Symposium on Computer Architecture, 52--61.

[10]

Faucett, L. 1994. Fundamentals of Neural Networks: Architectures, Algorithms and Applications. Prentice-Hall, Englewood Cliffs, N.J.

[11]

Gomez, F., Burger, D., and Miikkulainen, R. 2001. A neuroevolution method for dynamic resource allocation on a chip multiprocessor. In Proceedings of the International Joint Conference on Neural Networks (IJCNN-01), 2355--2360.

[12]

Hennessy, J. L. and Patterson, D. A. 1996. Computer Architecture: A Quantitative Approach, second edition. Morgan Kaufmann, San Francisco.

[13]

Jacobsen, E., Rotenberg, E., and Smith, J. E. 1996. Assigning confidence to conditional branch predictions. In Proceedings of the 29th Annual International Symposium on Microarchitecture, 142--152.

[14]

Jiménez, D. A. and Lin, C. 2001. Dynamic branch prediction with perceptrons. In Proceedings of the Seventh International Symposium on High Performance Computer Architecture, 197--206.

[15]

Jiménez, D. A. and Walsh, N. 1998. Dynamically weighted ensemble neural networks for classification. In Proceedings of the 1998 International Joint Conference on Neural Networks, 753--756.

[16]

Jiménez, D. A., Keckler, S. W., and Lin, C. 2000. The impact of delay on the design of branch predictors. In Proceedings of the 33rd Annual International Symposium on Microarchitecture, 67--76.

[17]

Kessler, R. E. 1999. The Alpha 21264 microprocessor. IEEE Micro 19, 2 (March/April), 24--36.

[18]

Kulkarni, A. D. 1993. Artificial Neural Networks for Image Understanding. Van Nostrand Reinhold, New York.

[19]

Lee, C.-C., Chen, C., and Mudge, T. 1997. The bi-mode branch predictor. In Proceedings of the Thirtieth Annual International Symposium on Microarchitecture, 4--13.

[20]

Lesartre, G. and Hunt, D. 1997. PA-8500: The continuing evolution of the PA-8000 family. In 42nd IEEE International Computer Conference.

[21]

McFarling, S. 1993. Combining branch predictors. Tech. Rep. TN-36m, Digital Western Research Laboratory, June.

[22]

Michaud, P., Seznec, A., and Uhlig, R. 1997. Trading conflict and capacity aliasing in conditional branch predictors. In Proceedings of the 24th International Symposium on Computer Architecture, 292--303.

[23]

Rosenblatt, F. 1962. Principles of Neurodynamics: Perceptrons and the Theory of Brain Mechanisms. Spartan, New York.

[24]

Sechrest, S., Lee, C.-C., and Mudge, T. 1996. Correlation and aliasing in dynamic branch predictors. In Proceedings of the 23rd International Symposium on Computer Architecture, 22--32.

[25]

Setiono, R. and Liu, H. 1995. Understanding neural networks via rule extraction. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, 480--485.

[26]

Smith, J. E. 1981. A study of branch prediction strategies. In Proceedings of the Eighth Annual International Symposium on Computer Architecture, 135--148.

[27]

Sprangle, E., Chappell, R., Alsup, M., and Patt, Y. N. 1997. The Agree predictor: A mechanism for reducing negative branch history interference. In Proceedings of the 24th International Symposium on Computer Architecture, 284--291.

[28]

Stark, J., Evers, M., and Patt, Y. N. 1998. Variable length path branch prediction. In Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems, 170--179.

[29]

Vintan, L. and Iridon, M. 1999. Towards a high performance neural branch predictor. In Proceedings of the International Joint Conference on Neural Networks (IJCNN), vol. 2. 868--873.

[30]

Wang, K. and Franklin, M. 1997. Highly accurate data value prediction using hybrid predictors. In Proceedings of the Thirtieth Annual International Symposium on Microarchitecture, 281--291.

[31]

Widrow, B. and Hoff Jr., M. 1960. Adaptive switching circuits. In IRE WESCON Convention Record, part 4, 96--104.

[32]

Yeh, T.-Y. and Patt, Y. N. 1991. Two-level adaptive branch prediction. In Proceedings of the 24th ACM/IEEE International Symposium on Microarchitecture, 51--61.

Cited By

Olgun ABostanci FFrancisco de Oliveira Junior GTugrul YBera RYaglikci AHassan HErgin OMutlu O(2024)Sectored DRAM: A Practical Energy-Efficient and High-Performance Fine-Grained DRAM ArchitectureACM Transactions on Architecture and Code Optimization10.1145/3673653Online publication date: 14-Jun-2024
https://doi.org/10.1145/3673653
Fiolhais LSousa L(2023)Transient-Execution Attacks: A Computer Architect PerspectiveACM Computing Surveys10.1145/360361956:3(1-38)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/10.1145/3603619
Surya Balasubramanian LRizkalla MLee JYtterdal TKumar M(2023)Towards No Penalty Control Hazard Handling2023 IEEE 66th International Midwest Symposium on Circuits and Systems (MWSCAS)10.1109/MWSCAS57524.2023.10405871(1128-1131)Online publication date: 6-Aug-2023
https://doi.org/10.1109/MWSCAS57524.2023.10405871
Show More Cited By

Index Terms

Neural methods for dynamic branch prediction
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Neural networks
    2. Serial architectures

Recommendations

Merging path and gshare indexing in perceptron branch prediction

We introduce the hashed perceptron predictor, which merges the concepts behind the gshare, path-based and perceptron branch predictors. This predictor can achieve superior accuracy to a path-based and a global perceptron predictor, previously the most ...
Generalizing neural branch prediction

Improved branch prediction accuracy is essential to sustaining instruction throughput with today's deep pipelines. Traditional branch predictors exploit correlations between pattern history and branch outcome to predict branches, but there is a stronger ...
Improved latency and accuracy for neural branch prediction

Microarchitectural prediction based on neural learning has received increasing attention in recent years. However, neural prediction remains impractical because its superior accuracy over conventional predictors is not enough to offset the cost imposed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 20, Issue 4

November 2002

133 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/571637

Issue’s Table of Contents

Copyright © 2002 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2002

Published in TOCS Volume 20, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

117
Total Citations
View Citations
3,484
Total Downloads

Downloads (Last 12 months)121
Downloads (Last 6 weeks)16

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Olgun ABostanci FFrancisco de Oliveira Junior GTugrul YBera RYaglikci AHassan HErgin OMutlu O(2024)Sectored DRAM: A Practical Energy-Efficient and High-Performance Fine-Grained DRAM ArchitectureACM Transactions on Architecture and Code Optimization10.1145/3673653Online publication date: 14-Jun-2024
https://doi.org/10.1145/3673653
Fiolhais LSousa L(2023)Transient-Execution Attacks: A Computer Architect PerspectiveACM Computing Surveys10.1145/360361956:3(1-38)Online publication date: 6-Oct-2023
https://dl.acm.org/doi/10.1145/3603619
Surya Balasubramanian LRizkalla MLee JYtterdal TKumar M(2023)Towards No Penalty Control Hazard Handling2023 IEEE 66th International Midwest Symposium on Circuits and Systems (MWSCAS)10.1109/MWSCAS57524.2023.10405871(1128-1131)Online publication date: 6-Aug-2023
https://doi.org/10.1109/MWSCAS57524.2023.10405871
Villon LSusskind ZBacellar AMiranda Ide Araújo LLima PBreternitz MJohn LFrança FDutra D(2023)A conditional branch predictor based on weightless neural networksNeurocomputing10.1016/j.neucom.2023.126637555(126637)Online publication date: Oct-2023
https://doi.org/10.1016/j.neucom.2023.126637
Nain SChaudhary P(2022)A Hybrid Branch Prediction Approach For High-Performance ProcessorsRecent Advances in Computer Science and Communications10.2174/266625581466621021016361615:6Online publication date: Jul-2022
https://doi.org/10.2174/2666255814666210210163616
Hudoud A(2021)Combining the Forwarding with Delay Slots Operations to Avoid the Branch Misprediction Penalty in Superscalar Processorsمجلة الجامعة الأسمرية10.59743/aujas.v6i5.10596:5(816-827)Online publication date: 31-Dec-2021
https://doi.org/10.59743/aujas.v6i5.1059
Sim M(2021)Boosting CPU Performance using Pipelined Branch and Jump Folding Hardware with Turbo Module2021 IEEE 14th International Symposium on Embedded Multicore/Many-core Systems-on-Chip (MCSoC)10.1109/MCSoC51149.2021.00060(359-365)Online publication date: Dec-2021
https://doi.org/10.1109/MCSoC51149.2021.00060
Sweety Chaudhary P(2021)Improving branch prediction by combining perceptron with learning vector quantization neural network in embedded processorInternational Journal of Information Technology10.1007/s41870-021-00764-1Online publication date: 22-Aug-2021
https://doi.org/10.1007/s41870-021-00764-1
Chen LPenney DJiménez D(2020)AI for Computer Architecture: Principles, Practice, and ProspectsSynthesis Lectures on Computer Architecture10.2200/S01052ED1V01Y202009CAC05515:5(1-142)Online publication date: 6-Nov-2020
https://doi.org/10.2200/S01052ED1V01Y202009CAC055
Navarro OYudi JHoffmann JHernandez HHübner M(2020)A Machine Learning Methodology for Cache Memory Design Based on Dynamic InstructionsACM Transactions on Embedded Computing Systems10.1145/337692019:2(1-20)Online publication date: 11-Mar-2020
https://dl.acm.org/doi/10.1145/3376920
Show More Cited By

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents