Accurate indirect branch prediction

Abstract

Indirect branch prediction is likely to become increasingly important in the future because indirect branches occur more frequently in object-oriented programs. With misprediction rates of around 25% on current processors, indirect branches can incur a significant fraction of branch misprediction overhead even though they remain less frequent than the more predictable conditional branches. We investigate a wide range of two-level predictors dedicated exclusively to indirect branches. Starting with predictors that use full-precision addresses and unlimited tables, we progressively introduce hardware constraints and minimize the loss of predictor performance at each step. For programs from the SPECint95 suite as well as a suite of large C++ applications, a two-level predictor achieves a misprediction rate of 9.8% with a 1K-entry table and 7.3% with an 8K-entry table, representing more than a threefold improvement over an ideal BTB. A hybrid predictor further reduces the misprediction rates to 8.98% (1K) and 5.95% (8K).

References

1. AH96 Gerald Aigner and Urs H61zle. Eliminating Virtual Function Calls in C++ Programs. ECOOP '96 Proceedings, Springer Verlag, July 1996.
2. CGZ94 Brad Calder, Dirk Grunwald, and Benjamin Zorn. Quantifying Behavioral Differences Between C and C++ Programs. Technical Report CU-CS-698-94, University of Colorado, Boulder, January 1994.
3. CG94 Brad Calder and Dirk Grunwald. Reducing indirect function call overhead in C++ programs. In 21st Symposium on Principles of Programming Languages, pages 397- 408, 1994.
4. CHP94 Po-Yung Chang, Eric Hao, Yale N. Patt. Branch classification: A new mechanism for improving branch predictor performance. MICRO '27 Proceedings, November 1994.
5. CHP95 Po-Yung Chang, Eric Hao, Yale N. Patt. Alternative implementations of Hybrid Branch Predictors. MICRO '28 Proceedings, November 1995.
6. CHP97 Po-Yung Chang, Eric Hao, Yale N. Patt. Target Prediction for Indirect Jumps. ISCA '97 Proceedings.
7. CK93 Robert F. Cmelik and David Keppel. Shade: A Fast Instruction-Set Simulator for Execution Profiling. Sun Microsystems Laboratories, Technical Report SMLI TR- 93-12, I993. Also published as Technical Report CSE- TR 93-06-06, University of Washington, 1993.
8. D+96 Jeffrey Dean, Greg DeFouw, David Grove, Vassily Litvinov, and Craig Chambers. Vortex: An Optimizing Compiler for Object-Oriented Languages. Proceedings of OOPSLA '96, San Jose, CA, October, 1996.
9. DH96 Karel Driesen and Urs H~lzle. The Direct Cost of Virtual Function Calls in C++. In OOPSLA '96 Conference proceedings, October 1996.
10. DH97 Karel Driesen and Urs Htilzle. Accurate Indirect Branch Prediction. Technical Report TRCS97-19, University of California, Santa Barbara, 1997.
11. EG97 Joel Emer and Nikolas Gloy. A language for describing predictors and its application to automatic synthesis. ISCA '97 Proceedings, July 1997.
12. ECP96 Marius Evers, Po-Yung Chang, Yale N. Patt. Using Hybrid Branch Predictors to Improve Branch Prediction Accuracy in the presence of context switches. Proceedings of ISCA '96.
13. Intel97 Intel press release. The Next Generation of Microprocessor Architecture: A 64-bit instruction Set Architecture (ISA) Based on EPIC Technology. Intel Corporation October 1997 (http://www.intel.com/pressroom/archive/ backgrnd/sp 101497.HTM)
14. J+96 Quinn Jacobson, Steve Bennet, Nikhil Sharma, and James E. Smith. Control flow speculation in multiscalar processors. HPCA-3 proceedings, February 1996.
15. KE91 David Kaeli and P. G. Emma. Branch history table prediction of moving target branches due to subroutine retiarns. ISCA "91 Proceedings, May 1991.
16. LS84 J. Lee and A. Smith. Branch prediction strategies and branch target buffer design. IEEE Computer 17(1), January 1984.
17. Nair95 Ravi Nair. Dynamic Path-Based Branch Correlation. Proceedings of MICRO-28, 1995.
18. M+94 S.A. Mahlke, R. E. Hank, R. A. Bringmann, J. C. Gyllenhaal, D. M. Gallagher, and W, W. Hwu. Characterizing the Impact of Predicated Execution on Branch Prediction. Proceedings of the 27th International Symposium on Microarchitecture. December 1994, pp. 217-227
19. MMN93 Ole Lehrmann Madsen, Birger Moller-Pedersen, Kristen Nygaard. Object-Oriented Programming in the Beta Programming Language. Addison-Wesley 1993.
20. McFar93 S. McFarling, Combining Branch Predictors, WRL Technical Note TN-36, Digital Equipment Corporation, June 1993
21. P+97 Yale N.Patt, Sanjay j. Patel, Marius Evers, Daniel H. Friendly, Jared Stark. One Billion Transistors, One Uniprocessor, One Chip. IEEE Computer, September 1997
22. SLM95 Stuart Sechrest, Chich-Chieh Lee, and Trevor Mudge. The role of adaptivity in two-level adaptive branch prediction. Proceedings of MICRO-29, November 1995.
23. USS97 Augustus K. Uht, Vijay Sindagi, Sajee Somanathan. Branch Effect Reduction Techniques. IEEE Computer, May 1997.
24. YP91 Tse-Yu Yeh and Yale N. Patt. Two-level adaptive branch prediction. MICRO 24, November 1991.
25. YP93 Tse-Yu Yeh and Yale N. Patt. A Comparison of Dynamic Branch Predictors that use Two Levels of Branch History. Proceedings of lSCA '93.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

• Hardware

  • Hardware validation