Dynamic history-length fitting: a third level of adaptivity for branch prediction

Abstract

Accurate branch prediction is essential for obtaining high performance in pipelined superscalar processors that execute instructions speculatively. Some of the best current predictors combine a part of the branch address with a fixed amount of global history of branch outcomes in order to make a prediction. These predictors cannot perform uniformly well across all workloads because the best amount of history to be used depends on the code, the input data and the frequency of context switches. Consequently, all predictors that use a fixed history length are therefore unable to perform up to their maximum potential.We introduce a method---called DHLF---that dynamically determines the optimum history length during execution, adapting to the specific requirements of any code, input data and system workload. Our proposal adds an extra level of adaptivity to two-level adaptive branch predictors. The DHLF method can be applied to any one of the predictors that combine global branch history with the branch address. We apply the DHLF method to gshare (dhlf-gshare) and obtain near-optimal results for all SPECint95 benchmarks, with and without context switches. Some results are also presented for gskewed (dhlf-gskewed), confirming that other predictors can benefit from our proposal.

References

1. 1 P.-Y. Chang, E. Hao, T.-Y. Yeh, and Y. Patt. Branch classification: a new mechanism for improving branch predictor performance. In 27th Int. Symp. on Microarchitecture, pages 22-31, Nov. 1994.
2. 2 A. Eustace and A. Srivastava. ATOM: A flexible interface for building high performance program analysis tools, in Proceedings of the Winter 1995 USENIX Conference, pages 303-314, Jan. 1995.
3. 3 M. Evers, P.-Y. Chang, and Y. N. Patt. Using hybrid branch predictors to improve branch prediction accuracy in the presence of context switches. In 23d Annual Int. Symp. on Computer Architecture, pages 3-11, May 1996.
4. 4 L. Gwennap. Digital 21264 sets new standard. Microprocessor Report, 10(14), Oct. 1996.
5. 5 T. Juan, S. Sanjeevan, and J. J. Navarro. A third level of adaptivity for branch prediction. Technical Report UPC- DAC-1998-4, Computer Architecture Department, UPC, Barcelona, March 1998.
6. 6 C.-C. Lee, I.-C. K. Chen, and T. N. Mudge. The Bi-Mode branch predictor. In 30th Annual Int. Symp. on Microarchitecture, Dec. 1997.
7. 7 S. McFarling. Combining branch predictors. Technical Note TN-36, Western Research Laboratory, DEC, June 1993.
8. 8 E Michaud, A. Seznec, and R. Uhlig. Trading conflict and capacity aliasing in conditional branch predictors. In 24th Annual Int. Symp. on Computer Architecture, pages 292- 303, June 1997.
9. 9 R. Nair. Dynamic path-based branch correlation. In 28th Int. Symp. on Microarchitecture, pages 15-23, Nov. 1995.
10. 10 S.-T. Pan, K. So, and J. T. Rahmeh. Improving the accuracy of dynamic branch prediction using branch correlation. In 5th Int. Conf. on Architectural Support for Programming Languages and Operating Systems, pages 76-84, Oct. 1992.
11. 11 S. Sechrest, C.-C. Lee, and T. Mudge. Correlation and aliasing in dynamic branch predictors. In 23d Annual Int. Symp. on Computer Architecture, pages 22-32, May 1996.
12. 12 J. E. Smith. A study of branch prediction strategies. In 8th Annual Int. Symp. on Computer Architecture, pages 135- 148, May 1981.
13. 13 E. Sprangle, R. S. Chappell, M. Alsup, and Y. N. Patt. The agree predictor: A mechanism for reducing negative branch history interference. In 24th Annual Int. Symp. on Computer Architecture, June 1997.
14. 14 M.-D. Tarlescu, K. B. Theobald, and G. R. Gao. Elastic history buffer: A low cost method to improve branch prediction accuracy. In Proceedings of the 1997 IEEE International Conference on Computer Design, pages 82-87, Oct. 1997.
15. 15 K. C. Yeager. The MIPS R10000 superscalar microprocessor. IEEE Micro, 16(2):28-40, Apr. 1996.
16. 16 T.-Y. Yeh and Y. N. Part. Two-level adaptive training branch prediction. In 24th Annual Int. Symp. on Microarchitecture, pages 51-61, Nov. 1991.
17. 17 T.-Y. Yeh and Y. N. Patt. Alternative implementations of two-level adaptive branch prediction. In 19th Annual Int. Symp. on Computer Architecture, pages 124-134, May 1992.
18. 18 T.-Y. Yeh and Y. N. Patt. A comprehensive instruction fetch mechanism for a processor supporting speculative execution. in 25th Annual Int. Symp. on Microarchitecture, pages 129-139, Nov. 1992.
19. 19 T.-Y. Yeh and Y. N. Patt. A comparison of dynamic branch predictors that use two levels of branch history. In 20th Annual bzt. Symp. on Computer Architecture, pages 257-266, May 1993.

Index Terms

• Computer systems organization

  • Architectures

    • Parallel architectures

• Hardware

  • Hardware validation