Copyright and Licensing
Articles accepted for publication will be licensed under the Creative Commons BY-NC-SA. Authors must sign a non-exclusive distribution agreement after article acceptance.
Improving the O-GEHL branch prediction accuracy using analytical results
Keywords:
branch predictor, perceptron, predictor analysis, O-GEHL, neural networksAbstract
The O-GEHL branch predictor has outperformed other prediction schemes using the same set of benchmarks in an international branch prediction contest, CBP-1. In this paper, we present the analysis results on each of the OGEHL branch predictor tables and also on the optimal number of predictor tables. Two methods are subsequently proposed to help increase the O-GEHL prediction accuracy. The first one aims to increase the space utilization of the first predictor table by dynamically adjusting the lengths of branch history regarding to the type of a benchmark currently in execution. The second one adds an extra table into the O-GEHL predictor using the space saved from the sharing of hysteresis bits. Experimental results have confirmed that both schemes improve the accuracy of two different predictor configurations, leading to two promising research directions for future explorations.
Downloads
Download data is not yet available.
References
[1] The 1st JILP Championship Branch Prediction Competition (CBP-1), Journal of Instruction-Level Parallelism, 2004, http://www.jilp.org/cbp/.
[2] P-Y. Chang, M. Evers, and Y. N. Patt, “Improving Branch Prediction Accuracy by Reducing Pattern History Table Interference”, Proceedings of the 1996 ACM/IEEE Conference on Parallel Architectures and Compilation Techniques,October 1996.
[3] A. N. Eden and T. N. Mudge, “The YAGS Branch Prediction Scheme”, Proceedings of the 31st ACM/IEEE International Symposium on Microarchitecture, November 1998, pp. 69-77.
[4] M. Evers, P.Y. Chang, and Y.N. Patt, “Using Hybrid Branch Predictors to Improve Branch Prediction Accuracy in the Presence of Context Switches”, Proceedings of the 23rd International Symposium on Computer Architecture, 1996, pp. 3–11.
[5] H. Gao and H. Zhou,” Adaptive Information Processing: An Effective Way to Improve Perceptron Predictors”, The 1st JILP Championship Branch Prediction Competition (CBP-1) in conjunction with MICRO-37, December 2004.
[6] D. A. Jimenez, “Fast Path-Based Neural Branch Prediction”, Proceedings of the 36th International Symposium on Microarchitecture, December 2003, pp. 243–252.
[7] D. Jimenez and C. Lin, “Dynamic branch prediction with perceptrons”, Proceedings of the 7th International Symposium on High Performance Computer Architecture, 2001.
[8] C-C Lee, I-C. K. Chen, and T. N. Mudge, “The Bi-mode Branch Predictor”, Proceedings of the 30th ACM/IEEE International Symposium on Microarchitecture, December 1997, pp. 4-13.
[9] G. H. Loh, D. S. Henry, and A. Krishnamurthy, “Exploiting Bias in the Hysteresis Bit of 2-bit Saturating Counters in Branch Predictors”, Journal of Instruction-Level Parallelism, vol. 5, June 2003, pp. 1-32.
[10] S. McFarling, “Combining Branch Predictors”, Technical Report TN-36, Digital Western Research Laboratory, June 1993.
[11] P. Michaud, A. Seznec, and R. Uhlig, “Trading Conflict and Capacity Aliasing in Conditional Branch Predictors”, In Proceedings of the 24th International Symposium on Computer Architecture, May 1997, pp. 292-303.
[12] A. Seznec, “The O-GEHL Branch Predictor”, The 1st JILP Championship Branch Prediction Competition (CBP-1) in conjunction with MICRO-37, December 2004.
[13] A. Seznec, S. Felix, V. Krishnan, and Y. Sazeides, “Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor”, In Proceedings of the 29th International Symposium on Computer Architecture, May 2002.
[14] E. Sprangle, R. S. Chappell, M. Alsup, and Y. N. Patt, “The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference”, Proceedings of the 24th International Symposium on Computer Architecture, June 1997, pp. 284–291.
[2] P-Y. Chang, M. Evers, and Y. N. Patt, “Improving Branch Prediction Accuracy by Reducing Pattern History Table Interference”, Proceedings of the 1996 ACM/IEEE Conference on Parallel Architectures and Compilation Techniques,October 1996.
[3] A. N. Eden and T. N. Mudge, “The YAGS Branch Prediction Scheme”, Proceedings of the 31st ACM/IEEE International Symposium on Microarchitecture, November 1998, pp. 69-77.
[4] M. Evers, P.Y. Chang, and Y.N. Patt, “Using Hybrid Branch Predictors to Improve Branch Prediction Accuracy in the Presence of Context Switches”, Proceedings of the 23rd International Symposium on Computer Architecture, 1996, pp. 3–11.
[5] H. Gao and H. Zhou,” Adaptive Information Processing: An Effective Way to Improve Perceptron Predictors”, The 1st JILP Championship Branch Prediction Competition (CBP-1) in conjunction with MICRO-37, December 2004.
[6] D. A. Jimenez, “Fast Path-Based Neural Branch Prediction”, Proceedings of the 36th International Symposium on Microarchitecture, December 2003, pp. 243–252.
[7] D. Jimenez and C. Lin, “Dynamic branch prediction with perceptrons”, Proceedings of the 7th International Symposium on High Performance Computer Architecture, 2001.
[8] C-C Lee, I-C. K. Chen, and T. N. Mudge, “The Bi-mode Branch Predictor”, Proceedings of the 30th ACM/IEEE International Symposium on Microarchitecture, December 1997, pp. 4-13.
[9] G. H. Loh, D. S. Henry, and A. Krishnamurthy, “Exploiting Bias in the Hysteresis Bit of 2-bit Saturating Counters in Branch Predictors”, Journal of Instruction-Level Parallelism, vol. 5, June 2003, pp. 1-32.
[10] S. McFarling, “Combining Branch Predictors”, Technical Report TN-36, Digital Western Research Laboratory, June 1993.
[11] P. Michaud, A. Seznec, and R. Uhlig, “Trading Conflict and Capacity Aliasing in Conditional Branch Predictors”, In Proceedings of the 24th International Symposium on Computer Architecture, May 1997, pp. 292-303.
[12] A. Seznec, “The O-GEHL Branch Predictor”, The 1st JILP Championship Branch Prediction Competition (CBP-1) in conjunction with MICRO-37, December 2004.
[13] A. Seznec, S. Felix, V. Krishnan, and Y. Sazeides, “Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor”, In Proceedings of the 29th International Symposium on Computer Architecture, May 2002.
[14] E. Sprangle, R. S. Chappell, M. Alsup, and Y. N. Patt, “The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference”, Proceedings of the 24th International Symposium on Computer Architecture, June 1997, pp. 284–291.
Downloads
Published
2007-04-02
Issue
Section
Original Articles
License
How to Cite
[1]
“Improving the O-GEHL branch prediction accuracy using analytical results”, JCS&T, vol. 7, no. 02, pp. p. 171–176, Apr. 2007, Accessed: Jan. 14, 2026. [Online]. Available: https://journal.info.unlp.edu.ar/JCST/article/view/788
