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

• AH96: Gerald Aigner , Urs Hölzle, Eliminating Virtual Function Calls in C++ Programs, Proceedings of the 10th European Conference on Object-Oriented Programming, p.142-166, July 08-12, 1996
• 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.
• CG94: Brad Calder , Dirk Grunwald, Reducing indirect function call overhead in C++ programs, Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.397-408, January 16-19, 1994, Portland, Oregon, United States [doi>10.1145/174675.177973]
• CHP94: Po-Yung Chang , Eric Hao , Tse-Yu Yeh , Yale Patt, Branch classification: a new mechanism for improving branch predictor performance, Proceedings of the 27th annual international symposium on Microarchitecture, p.22-31, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192727]
• CHP95: Po-Ying Chang , Eric Hao , Yale N. Patt, Alternative implementations of hybrid branch predictors, Proceedings of the 28th annual international symposium on Microarchitecture, p.252-257, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• CHP97: Po-Yung Chang , Eric Hao , Yale N. Patt, Target prediction for indirect jumps, Proceedings of the 24th annual international symposium on Computer architecture, p.274-283, June 01-04, 1997, Denver, Colorado, United States
• CK93: Robert F. Cmelik , David Keppel, Shade: A Fast Instruction Set Simulator for Execution Profiling, Sun Microsystems, Inc., Mountain View, CA, 1993
• D+96: Jeffrey Dean , Greg DeFouw , David Grove , Vassily Litvinov , Craig Chambers, Vortex: an optimizing compiler for object-oriented languages, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.83-100, October 06-10, 1996, San Jose, California, United States
• DH96: Karel Driesen , Urs Hölzle, The direct cost of virtual function calls in C++, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.306-323, October 06-10, 1996, San Jose, California, United States
• DH97: Karel Driesen , Urs Holzle, Accurate Indirect Branch Prediction, University of California at Santa Barbara, Santa Barbara, CA, 1998
• EG97: Joel Emer , Nikolas Gloy, A language for describing predictors and its application to automatic synthesis, Proceedings of the 24th annual international symposium on Computer architecture, p.304-314, June 01-04, 1997, Denver, Colorado, United States
• 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 the 23rd annual international symposium on Computer architecture, p.3-11, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 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)
• J+96: Quinn Jacobson , Steve Bennett , Nikhil Sharma , James E. Smith, Control Flow Speculation in Multiscalar Processors, Proceedings of the 3rd IEEE Symposium on High-Performance Computer Architecture, p.218, February 01-05, 1997
• KE91: David R. Kaeli , Philip G. Emma, Branch history table prediction of moving target branches due to subroutine returns, Proceedings of the 18th annual international symposium on Computer architecture, p.34-42, May 27-30, 1991, Toronto, Ontario, Canada
• LS84: J. Lee and A. Smith. Branch prediction strategies and branch target buffer design. IEEE Computer 17(1), January 1984.
• Nair95: Ravi Nair, Dynamic path-based branch correlation, Proceedings of the 28th annual international symposium on Microarchitecture, p.15-23, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• M+94: Scott A. Mahlke , Richard E. Hank , Roger A. Bringmann , John C. Gyllenhaal , David M. Gallagher , Wen-mei W. Hwu, Characterizing the impact of predicated execution on branch prediction, Proceedings of the 27th annual international symposium on Microarchitecture, p.217-227, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192755]
• MMN93: Ole Lehrmann Madsen , Birger Mø-Pedersen , Kristen Nygaard, Object-oriented programming in the BETA programming language, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• McFar93: S. McFarling, Combining Branch Predictors, WRL Technical Note TN-36, Digital Equipment Corporation, June 1993
• P+97: Yale N. Patt , Sanjay J. Patel , Marius Evers , Daniel H. Friendly , Jared Stark, One Billion Transistors, One Uniprocessor, One Chip, Computer, v.30 n.9, p.51-57, September 1997 [doi>10.1109/2.612249]
• SLM95: Stuart Sechrest , Chih-Chieh Lee , Trevor Mudge, The role of adaptivity in two-level adaptive branch prediction, Proceedings of the 28th annual international symposium on Microarchitecture, p.264-269, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• USS97: Augustus K. Uht , Vijay Sindagi , Sajee Somanathan, Branch Effect Reduction Techniques, Computer, v.30 n.5, p.71-81, May 1997 [doi>10.1109/2.589913]
• YP91: Tse-Yu Yeh and Yale N. Patt. Two-level adaptive branch prediction. MICRO 24, November 1991.
• YP93: Tse-Yu Yeh , Yale N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, Proceedings of the 20th annual international symposium on Computer architecture, p.257-266, May 16-19, 1993, San Diego, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES