Employing Variable Cross-Reference Prediction and Iterative Dispatch to Raise Dynamic Branch Prediction Accuracy

Po-Jen Chuang; Yue-Ter  Liau; Young-Tzong Hsiao; Yu-Shian Chiu

doi:10.6180/jase.2008.11.1.06

Employing Variable Cross-Reference Prediction and Iterative Dispatch to Raise Dynamic Branch Prediction Accuracy

Po-Jen Chuang This email address is being protected from spambots. You need JavaScript enabled to view it.¹, Yue-Ter Liau¹, Young-Tzong Hsiao¹ and Yu-Shian Chiu¹

¹Department of Electrical Engineering, Tamkang University, Tamsui, Taiwan 251, R.O.C.

Received: September 15, 2006
Accepted: March 13, 2007
Publication Date: March 1, 2008

Download Citation: ||https://doi.org/10.6180/jase.2008.11.1.06

ABSTRACT

To improve branch prediction accuracy for the two-level adaptive branch predictor, two schemes - dealing respectively with the prediction and dispatch parts, are presented in this paper. The proposed VCR prediction scheme is able to achieve desirable prediction accuracy, with reasonably low time complexity and no extra hardware cost, by variably cross-referring traces in the PHT to make predictions. The Iterative dispatch approach utilizes the PHT history to do dispatching for an additional layer of pattern history which helps providing more information for making better predictions. To attain desirable prediction accuracy at reduced cost, a combined predictor formed by the proposed VCR scheme and the optimal PPM algorithm is also considered. Extensive trace-driven simulation runs have been conducted to evaluate the performance of our proposed schemes and other predictors. As the results indicate, our proposed schemes compare favorably in most of the situations in terms of prediction accuracy.

Keywords: Branch History, Dynamic Branch Prediction, Performance Evaluation, Prediction Accuracy, Trace-driven Simulation, Two-level Adaptive Branch Predictor

REFERENCES

[1] Boggs, D. et al., “The Microarchitecture of the Intel Pentium 4 Processor on 90 nm Technology,” Intel Technology Journal, Vol. 8, Feb. (2004).
[2] Yeh, T.-Y. and Patt, Y. N., “Alternative Implementations of Two-Level Adaptive Branch Prediction,” Proc. 19th Annual Int’l Symp. on Computer Architecture, May, pp. 124134 (1992).
[3] McFarling, S., “Combining Branch Predictors,” Technical Report, TN-36, Digital Western Research Laboratory, June (1993).
[4] Sprangle, E., Chappell, R. S., Alsup, M. and Patt, Y. N., “The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference,” Proc. 24th Annual Int’l Symp. on Computer Architecture, May, pp. 284291 (1997).
[5] Chen, I.-C. K., Coffey, J. T. and Mudge, T. N., “Analysis of Branch Prediction via Data Compression,” Proc. 7th Int’l Conf. on Architectural Support for Programming Languages and Operating Systems, Oct., pp. 128137 (1996).
[6] Sechrest, S., Lee, C.-C. and Mudge, T., “Correlation and Aliasing in Dynamic Branch Predictors,” Proc. 23rd Annual Int’l Symp. on Computer Architecture, May, pp. 2232 (1996).
[7] Lee, C.-C., Chen, I.-C. K. and Mudge, T. N., “The Bi-Mode Branch Predictor,” Proc. 30th Int’l Symp. on Microarchitecture, Dec., pp. 413 (1997).
[8] Eden, A. N. and Mudge, T., “The YAGS Branch Prediction Scheme,” Proc. 31st Int’l Symp. on Microarchitecture, Dec., pp. 6977 (1998).
[9] Juan, T., Sanjeevan, S. and Navarro, J. J., “Dynamic History-Length Fitting: A Third Level of Adaptivity for Branch Prediction,” Proc. 25th Annual Int’l Symp. on Computer Architecture, May, pp. 155166 (1998).
[10] Yeh, T.-Y. and Patt, Y. N., “Two-Level Adaptive Branch Prediction,” Proc. 24th annual Int’l Symp. on Microarchitecture, Nov., pp. 5161 (1991).
[11] Ross, S. M., Introduction to Probability Models, London, United Kingdom: Academic Press (1985).
[12] SPEC CPU’95, Technical Manual, Aug. (1995).
[13] Burger, D. and Austin, T. M., “The SimpleScalar Tool Set, Version 2.0,” Univ. of Wisconsin-Madison CS Dept. Technical Report #1342, June (1997).