Two-Level Alloyed Branch Predictor based on Genetic Algorithm for Deep Pipelining

Full Text (PDF, 723KB), PP.27-33

Views: 0 Downloads: 0


Shivam Goyal 1,* Jaskirat Singh 1

1. JECRC University, Jaipur, Rajasthan 303905, India

* Corresponding author.


Received: 15 Jan. 2017 / Revised: 25 Feb. 2017 / Accepted: 8 Mar. 2017 / Published: 8 May 2017

Index Terms

Control hazard, Branch prediction, Alloying, hybrid branch predictors, dynamic, robust


To gain improved performance in multiple issue superscalar processors, the increment in instruction fetch and issue rate is pretty necessary. Evasion of control hazard is a primary source to get peak instruction level parallelism in superscalar processors. Conditional branch prediction can help in improving the performance of processors only when these predictors are equipped with algorithms to give higher accuracy. The Increment in single miss-prediction rate can cause wastage of more than 20% of the instructions cycles, which leads us to an exploration of new techniques and algorithms that increase the accuracy of branch prediction. Alloying is a way to exploit the local and global history of different predictors in the same structure and sometimes also called hybrid branch prediction. In this paper, we aim to design a more accurate and robust two-level alloyed predictor, whose behavior is more dynamic on changing branch direction.


Cite This Paper

Shivam Goyal, Jaskirat Singh, "Two-Level Alloyed Branch Predictor based on Genetic Algorithm for Deep Pipelining Processors", International Journal of Modern Education and Computer Science(IJMECS), Vol.9, No.5, pp.27-33, 2017. DOI:10.5815/ijmecs.2017.05.04


[1]Huang, Mingkai, Dan He, Xianhua Liu, Mingxing Tan, and Xu Cheng. "An Energy-Efficient Branch Prediction with Grouped Global History". In Parallel Processing (ICPP), 2015 44th International Conference on, pp. 140-149. IEEE, 2015.
[2]Wu, Di. "High Performance Branch Predictors for Soft Processors." PhD diss., University of Toronto, 2014.
[3]Lu, Z., Lach, J., Stan, M. R. & Skadron, K. “Alloyed branch history: Combining global and local branch history for robust performance”. International Journal of Parallel programming, 31(2), pp.137-177, 2003
[4]Eden, Avinoam Nomik. "Of limits and myths in branch prediction." PhD diss., University of Michigan, 2001.
[5]Jiménez, Daniel A., and Calvin Lin. "Dynamic branch prediction with perceptrons." In High-Performance Computer Architecture, 2001. HPCA. The Seventh International Symposium on, pp. 197-206. IEEE, 2001.
[6]Skadron, Kevin, Margaret Martonosi, and Douglas W. Clark. "A taxonomy of branch mispredictions, and alloyed prediction as a robust solution to wrong-history mispredictions." Parallel Architectures and Compilation Techniques, 2000. Proceedings. International Conference on. IEEE, 2000.
[7]Lee, Chih-Chieh, I-CK Chen, and Trevor N. Mudge. "The bi-mode branch predictor." In Microarchitecture, 1997. Proceedings. Thirtieth Annual IEEE/ACM International Symposium on, pp. 4-13. IEEE, 1997.
[8]Emer, Joel, and Nikolas Gloy. "A language for describing predictors and its application to automatic synthesis." In ACM SIGARCH Computer Architecture News, vol. 25(2), pp. 304-314. ACM, 1997.
[9]McFarling, Scott. Combining branch predictors. Vol. 49. Technical Report TN-36, Digital Western Research Laboratory, 1993.
[10]Porter, Leo, and Dean M. Tullsen. "Creating artificial global history to improve branch prediction accuracy." In Proceedings of the 23rd international conference on Supercomputing, pp. 266-275. ACM, 2009.
[11]Yeh, T. Y., & Patt, Y. N. “Alternative implementations of two-level adaptive branch prediction”. In ACM SIGARCH Computer Architecture News Vol. 20(2), pp. 124-134. , May 1992
[12]Mudge, T., Lee, C. C., & Sechrest, S. “Correlation and aliasing in dynamic branch predictors”. In Computer Architecture, 1996 23rd Annual International Symposium on pp. 22-22, IEEE. May 1996
[13]Lee, C. C., Chen, I. C., & Mudge, T. N. “The bi-mode branch predictor”. In Microarchitecture, 1997. Proceedings., Thirtieth Annual IEEE/ACM International Symposium on pp. 4-13. IEEE, December 1997
[14]Thomas, R., Franklin, M., Wilkerson, C., & Stark, J. “Improving branch prediction by dynamic dataflow-based identification of correlated branches from a large global history”. In ACM SIGARCH Computer Architecture News Vol. 31(2), pp. 314-323. ACM, June 2003
[15]Chang, P. Y., Evers, M., & Patt, Y. N. “Improving branch prediction accuracy by reducing pattern history table interference”. International journal of parallel programming, 25(5), pp.339-362, 1997
[16]Eden, A. N., & Mudge, T. “The YAGS branch prediction scheme”. In Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture pp. 69-77, November 1998
[17]Yeh, T. Y., Marr, D. T., & Patt, Y. N. “Increasing the instruction fetch rate via multiple branch prediction and a branch address cache”. In ACM International Conference on Supercomputing 25th Anniversary Volume pp. 183-192, June 2014
[18]Evers, M., Chang, P. Y., & Patt, Y. N. “Using hybrid branch predictors to improve branch prediction accuracy in the presence of context switches”. In ACM SIGARCH Computer Architecture News Vol. 24(2), pp. 3-11, May 1996