AUTHORS: Sang Hoon Lee, Jongsu Park
Download as PDF
ABSTRACT: The demands for high-performance microprocessors have recently increased. Accurate branch prediction is one of the most important factors for high-performance processors. In order to predict branch outcomes, instruction program counter bits and the history of recently executed branch outcomes are used. Among the executed branch outcomes, some histories are useful while others are useless. In addition, these useful/useless histories vary among branch instructions. Numerous studies have shown a method that identifies optimal history. However, little research has been done regarding the treatment of useless history. In this paper, a new method called Instruction Address alloyed History Length Modification branch predictor is proposed to handle the useless history bits. When PHT entries are 4,096, IAaHLM has a prediction accuracy of 93.22% and Gshare has a prediction accuracy of 91.84%.
KEYWORDS: branch prediction, branch predictor, dynamic branch history control, microprocessor
REFERENCES:
[1] J. E. Smith, A study of branch prediction strategies, in Proceedings of the 8th annual symposium on Computer Architecture, Minneapolis, Minnesota, USA, pp. 135-148, 1981.
[2] T.-Y. Yeh and Y. N. Patt, Two-level adaptive training branch prediction, in Proceedings of the 24th annual international symposium on Microarchitecture, New Mexico, Puerto Rico, pp. 51-61, 1991.
[3] T.-Y. Yeh and Y. N. Patt, A comparison of dynamic branch predictors that use two levels of branch history, in Proceedings of the 20th annual international symposium on computer architecture, San Diego, California, USA, pp. 257-266, 1993.
[4] T.-Y. Yeh and Y. N. Patt, Alternative implementations of two-level adaptive branch prediction, in Proceedings of the 19th annual international symposium on Computer architecture 1992, Queensland, Australia. p. 124-134, 1992.
[5] S.-T. Pan, K. So and J. T. Rahmeh, Improving the accuracy of dynamic branch prediction using branch correlation, in Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, Boston, Massachusetts, USA, pp. 76-84, 1992.
[6] M. Evers, S. J. Patel, R. S. Chappell and Y. N. Patt, An analysis of correlation and predictability: what makes two-level branch predictors work, The 25th Annual International Symposium on Computer Architecture, Barcelona, Spain, pp. 52-61, 1998.
[7] M. D. Tarlescu, K. B. Theobald and G. R. Gao, Elastic history buffer: a low-cost method to improve branch prediction accuracy. IEEE International Conference on Computer Design: VLSI in Computers and Processors, Austin, TX, USA, pp. 82-87, 1997.
[8] L. Porter and D. M. Tullsen, Creating artificial global history to improve branch prediction Bzip2 Eon Gcc PARSER Perl Twolf Vortex Vpr Average 4096 PHT Entries Fig. 10. Comparison of IPC in Gshare, DpBHLA, and IAaHLM accuracy, in Proceedings of the 23rd international conference on Supercomputing, Yorktown Heights, NY, USA. p. 266-275, 2009.
[9] T. Juan, S. Sanjeevan and J. J. Navarro, Dynamic history-length fitting: a third level of adaptivity for branch prediction. The 25th Annual International Symposium on Computer Architecture, Barcelona, Spain, pp. 155-166, 1998.
[10] J. W. Kwak and C. S. Jhon, Dynamic perbranch history length adjustment to improve branch prediction accuracy. Microprocess. Microsyst., vol. 31, pp. 63-76, 2007.
[11] D. Burger, T.M.A. and S. Bennett, Evaluating future micro-processors: the SimpleScalar tool set, 1997.
[12] J. L. Henning, SPEC CPU2000: measuring CPU performance in the New Millennium, Computer, vol. 33, pp. 28-35, 2000.
[13] K. C. Breen and D. G. Elliott, Aliasing and anti-aliasing in branch history table prediction SIGARCH Computer Architecture News, vol. 31, pp. 1-4, 2003.
