Brad Calder
ABSTRACT
Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The name program-based branch prediction is given to static branch prediction techniques that base their prediction on a program's structure. In this paper, we investigate a new approach to program-based branch prediction that uses a body of existing programs to predict the branch behavior in a new program. We call this approach to program-based branch prediction, evidence-based static prediction, or ESP. The main idea of ESP is that the behavior of a corpus of programs can be used to infer the behavior of new programs. In this paper, we use a neural network to map static features associated with each branch to the probability that the branch will be taken. ESP shows significant advantages over other prediction mechanisms. Specifically, it is a program-based technique, it is effective across a range of programming languages and programming styles, and it does not rely on the use of expert-defined heuristics.
In this paper, we describe the application of ESP to the problem of branch prediction and compare our results to existing program-based branch predictors. We also investigate the applicability of ESP across computer architectures, programming languages, compilers, and run-time systems. Averaging over a body of 43 C and Fortran programs, ESP branch prediction results in a miss rate of 20%, as compared with the 25% miss rate obtained using the best existing program-based heuristics.
- 1.R. Alverson, D. Callahan, D. Cummings, B. Koblenz, A. Porterfield, and B. Smith. The tera computer system. In International Conference on Supercomputing, pages 1-6, June 1990. Google Scholar
Digital Library
- 2.Vasanth Balasundaram, Geoffrey Fox, Ken Kennedy, and Ulrich Kremer. A static performance estimator to guide data partitioning decisions. In Third ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, pages 213-223, July 199 I. Google ScholarDigital Library
- 3.Thomas Ball and James R. Larus. Branch prediction for free. In Proceedings of the SIGPLAN'93 Conference on Programming Language Design and Implementation, pages 300-313, June 1993. Google ScholarDigital Library
- 4.M. Berry. The Perfect Club Benchmarks: Effective performance evaluation of supercomputers. The International Journal of Supercomputer Applications, 3(3):5-40, Fall 1989.Google ScholarDigital Library
- 5.Brad Calder and Dirk Grunwald. Fa~at & accurate instruction fetch and branch prediction. In 21st Annual International Symposium on Computer Architecture, pages 2-11. ACM, April 1994. Google ScholarDigital Library
- 6.Brad Calder and Dirk Grunwald. Reducing branch costs via branch alignment. In Six International Conference on Architectural Support for Programming Languages and Operating Systems, pages 242-251. ACM, 1994. Google ScholarDigital Library
- 7.Brad Calder, Dirk Grunwald, and Benjamin Zorn. Quantifying behavioral differences between C and C++ programs. Journal of Programming Languages, 2(4), 1995. Also available as University of Colorado Technical Report CU-CS-698-94.Google Scholar
- 8.P. P. Chang and W. W. Hwu. Profile-guided automatic inline expansion for C programs. Software Practice and Experience, 22(5):349-376, 1992. Google ScholarDigital Library
- 9.P. P. Chang, S. A. Mahlke, and W. W. Hwu. Using profile information to assist classic compiler code optimizations. Software Practice and Experience, 21(12):1301-1321, 1991. Google ScholarDigital Library
- 10.A.P. Dempster, A generalization of bayesian inference. Journal of the Royal Statistical Society, 30:205-247,1968.Google Scholar
- 11.J. A. Fisher and S. M. Freudenberger. Predicting conditional branch directions from previous runs of a program. In Proceedings of the Fifth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-V), pages 85-95, Boston, Mass., October 1992. ACM. Google ScholarDigital Library
- 12.Joseph A. Fisher. Trace scheduling: A technique for global microcode compaction. IEEE Transactions on Computers, C- 30(7):478-490, July 1981.Google ScholarDigital Library
- 13.Wen-mei W. Hwu and Pohua P. Chang. Achieving high instruction cache performance with an optimizing compiler. In 16thAnnual International Symposium on Computer Architecture, pages 242-251. ACM, 1989. Google ScholarDigital Library
- 14.Scott McFarling and John Hennessy. Reducing the cost of branches. In 13th Annual International Symposium of Computer Architecture, pages 396-403. Association for Computing Machinery, 1986. Google ScholarDigital Library
- 15.Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Mateo, CA, 1988. Google ScholarDigital Library
- 16.D.E. Rumelhart, G. E. Hinton, and R J. Williams. Parallel distributed processing: Explorations in the microstructure of cognition. Volume h Foundations, chapter Learning internal representations by error propagation, pages 318-362. MIT Press/Bradford Books, Cambridge, MA, 1986. D. E. Rumelhart and J. L. Mc- Clelland, editors. Google ScholarDigital Library
- 17.G. Shafer. A Mathematical Theory of Evidence. Princeton University Press, Princeton, NJ, 1976.Google Scholar
- 18.J.E. Smith. A study of branch prediction strategies. In 8thAnnual international Symposium of Computer Architecture, pages 135- 148. ACM, 1981. Google ScholarDigital Library
- 19.P. Smolensky, M. C. Mozer, and D. E. Rumelhart, editors. Mathemattcal perspectives on neural networks. Erlbaum, 1994. In press. Google ScholarDigital Library
- 20.Amitabh Srivastava and Alan Eustace. ATOM: A system for building customized program analysis tools. In Proceedings of the SIGPLAN'94 Conference on Programming Language Design and lmplementatton, pages 196-205. ACM, 1994. Google ScholarDigital Library
- 21.Tim A. Wagner, Vance Maverick, Susan Graham, and Michael Harrison. Accurate static estimators for program optimization. In Proceedings of the SIGPLAN'94 Conjerence on Programming Language Design and Implementation, pages 85-96, Orlando, Florida, June 1994. ACM. Google ScholarDigital Library
- 22.Youfeng Wu and James R. tams. Static branch frequency and program profile analysis. In 27th International Symposium on Microarchitecture, San Jose, Ca, November 1994. IEEE. Google ScholarDigital Library
- 23.Tse-Yu Yeh and Yale N. Patt. A comparison of dynamic branch predictors that use two levels of branch history. In 20th Annual International Symposium on Computer Architecture, pages 257- 266, San Diego, CA, May 1993. ACM. Google ScholarDigital Library
Index Terms
- Corpus-based static branch prediction
Recommendations
Corpus-based static branch prediction
Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The name program-based branch prediction is given to static branch prediction techniques that base their prediction on a ...
Evidence-based static branch prediction using machine learning
Correctly predicting the direction that branches will take is increasingly important in today's wide-issue computer architectures. The name program-based branch prediction is given to static branch prediction techniques that base their prediction on a ...
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 ...
Comments