Improving branch predictors by correlating on data values

ABSTRACT

Branch predictors typically use combinations of branch PC bits and branch histories to make predictions. Recent improvements in branch predictors have come from reducing the effect of interference, i.e. multiple branches mapping to the same table entries. In contrast, the branch difference predictor (BDP) uses data values as additional information to improve the accuracy of conditional branch predictors. The BDP maintains a history of differences between branch source register operands, and feeds these into the prediction process.

An important component of the BDP is a rare event predictor (REP) which reduces learning time and table interference. An REP is a cache-like structure designed to store patterns whose predictions differ from the norm.

Initially, ideal interference-free predictors are evaluated to determine how data values improve correlation. Next, execution driven simulations of complete designs realize this potential. The BDP reduces the misprediction rate of five SPEC95 integer benchmarks by up to 33% compared to gshare and by up to 15% compared to Bi-Mode predictors.

References

1. 1.David L. August, Daniel A. Connors, John C, Gyilenhaal, Wen-mei W. Hwu, "Architectural Support for Compiler- Synthesized Dynamic Branch Prediction, Strategies: Rational and Initial Results," 3rd Intl. Syrup. on High Performance Comp. Arch., pp. 84-93, Feb. 1997.
2. 2.Douglas C. Burger, Todd M. Austin, "The SimpleScalar Tool Set, Version 2.0," Univ. of Wisconsin - Madison Comp. Sci. Tech. Report #1342, June 1997.
3. 3.Po-Yung Chang, Eric Hao, Yale N. Putt, "Alternative Implementations of Hybrid Branch Predictors," 28th Intl. Symp. on Microarchitecture, pp. 252-257, Nov. 1995.
4. 4.i-Cheng K. Chen, John T. Coffey, Trevor N. Mudge, "Analysis of Branch Prediction via Data Compression," 7th Intl, Conf. on Arch. Support for Prog. Lang. and Op. Sys., pp. 128- 137, Oct, 1996.
5. 5.Avinoam Nomik Eden, Trevor Mudge, "The YAGS Branch Prediction Scheme," 31st Intl. Syrup. on Microarchitecture, pp, 69-77, Dec. 1998.
6. 6.Alexandre Farcy, O!ivier Temam, Roger Espasa, Toni Juan, "Datafiow Analysis of Branch Mispredictions and Its Applications to Early Resolution of Branches," 31nd Intl. Syrup. on Microarchitecture, pp. 59-68, Nov. 1998.
7. 7.Jose Gonzalez, Antonio Gonzalez, "Control-Flow Speculation through Value Prediction for Superscalar Processors," Intl. Conf. on Parallel Arch. and Comp. Tech., Oct. 1999.
8. 8.Linley Gwenmap, "Intel Discloses New IA-64 Features," Microprocessor Report, pp. 16-19, March 1999.
9. 9.Timothy H. Heil, "Branch Difference Prediction and the Rare Event Predictor," Univ. of Wisonsin - Madison Tech. Rep. #ECE-99-4.
10. 10.Toni Juan, Sanji Sanjeevan, Juan J. Navarro, "Dynamic History-Length Fitting: a third level of adaptivity for branch" prediction," 25th Intl. Syrup. on Computer Architecture, pp. 155-166, June 1998.
11. 11.John Kalamatianos, David R. Kaeti, "Predicting Indirect Branches via Data Compression," 31st Intl. Syrup. on Microarchitecture, pp. 272-280, Dec. 1998.
12. 12.Chih-Chieh Lee, l-Cheng K. Chen, Trevor N. Mudge, "The Bi-Mode Branch Predictor," 30th Intl. Syrup. on Microarchitecture, pp. 4-13, Dec. 1997.
13. 13.Mikko H. Lipasti, John Paul Shen, "Exceeding the Dataflow Limit via Value Prediction," 29th Intl. Syrup. on Microarchitecture, pp. 226-237, Dec. 1996.
14. 14.Cathy May, ed., The PowerPC Architecture, 2nd ed., Morgan Kaufmann, May 1994.
15. 15.Scott M. McFarling, "Combining Branch Predictors," Technical Report TN-36, Digital Western Research Laboratory, June 1993.
16. 16.Pierre Michaud, Andre Seznec, Richard Uhlig, "Trading Conflict and Capacity Aliasing in Conditional Branch Predictors,'' 24th Intl. Syrup. on Computer Architecture, pp. 292-303, June 1997.
17. 17.A. Moffat, "Implementing the PPM data compression scheme," IEEE Trans. on Communications, vol. 38, no. 11, pp. 1917-1921, Nov. 1990.
18. 18.Andreas Moshovos, Gurindar S. Sohi, "Streamlining Interoperation Memory Communication via Data Dependence" Prediction,'' 30th Intl. Syrup. on Microarchitecture, pp. 235-245, Dec. 199'7.
19. 19.Ravi Nair, "Dynamic path-based branch correlation," 28th Intl. Syrup. on Microarchitecture, pp. 15-23, Nov. 1995.
20. 20.Bohuslav Rychlik, John Faistl, Bryon King, John P. Shen, "Efficacy and Performance Impact of Value Prediction," Intl. Conf. on Parallel Arch. and Comp. Tech., Oct. 1998.
21. 21.Yiannakis Sazeides, James E. Smith, "The Predictability of Data Values," 30th Intl. Syrup. on Microarchitecture, pp. 248- 258, Dec. 1997.
22. 22.Stuart Sechrest, Chih-Chieh Lee, Trevor Mudge, "Correlation and Aliasing in Dynamic Branch Predictors," 23rd Intl. Syrup. on Computer Architecture, pp. 22-31, May 1996.
23. 23.James E. Smith, "A study of branch prediction strategies," 8th Intl. Syrup. on Computer Architecture, pp. 135-148, May 1981
24. 24.Jared Stark, Marius Evers, Yale N. Putt, "Variable Length Path Branch Prediction," 8th Intl. Conf. on Arch. Support for Prog. Lang. and Op. Sys., pp. 170-179, Oct. 1998.
25. 25.Stefanos Kaxiras, James R. Goodman, "Improving CC- NUMA Performance Using Instmction.Based Prediction," To appear in 5th Intl. Symp. on High Performance Comp. Arch., 1999.
26. 26.Kai Wang, Manoj Franklin, "Highly Accurate Data Value Prediction using Hybrid Predictors," 30th Intl. Syrup. on Microarchitecture, pp. 281-290, Dec. 1997.
27. 27.Tse-Yu Yeh, Yale N. Putt, ~'A Comparison of Dynamic Branch Predictors that use Two Levels of Branch History," 20th Intl. Syrup. on Computer Architecture, pp. 257-266, May. 1993.

Index Terms

• Computer systems organization

  • Embedded and cyber-physical systems

    • Embedded systems

• Hardware

  • Electronic design automation

    • Logic synthesis

      • Circuit optimization

  • Hardware validation