Design and Implementation of Efficient Multi-branch Predictor

doi:10.3778/j.issn.1673-9418.2207069

Abstract

Abstract: Branch prediction is a momentous technology guarantee for processor performance, especially for the widely used superscalar processor. The properties of the branch predictor significantly affect the overall performance, power consumption, and area of the processor. To obtain a more cost-effective branch predictor in the superscalar processor, an attempt is made to use a single TAGE (tagged geometric history length) predictor to predict the branches within the fetch width. The championship branch prediction platform is used to evaluate the performance of the predictor, and its prediction ability is sufficient to meet the prediction conditions. However, in practice, conflicts in both the predictor and branch target buffer affect its performance. To solve the above problem, this paper adds additional prediction paths based on a single TAGE branch predictor and independently saves and predicts additional branch instruction information. This predictor is implemented in the processor using hardware description language and compared with a single TAGE branch predictor to perform standard benchmark programs for embedded processors, dhrystone, coremark and embench. Experimental results show that the performance of the optimized branch predictor is improved by 14.1 percentage points, while the storage overhead is only increased by 9.06%. Finally, through the analysis of the experimental data, it is found that this scheme is not only conducive to the prediction of additional branch instructions, but also can achieve more accurate prediction of single branch instruction through more accurate acquisition of branch history information.

Key words: branch prediction, tagged geometric history length (TAGE), embedded, superscalar, processor

摘要： 分支预测是保证处理器性能的重要技术，尤其在当今广泛应用的超标量处理器中，分支预测器的各项属性极大地影响着处理器的整体性能、功耗和面积。为了在超标量处理器中获得具有较高性价比的分支预测器，尝试使用了TAGE预测器对取指宽度内的所有分支进行预测，并利用分支预测竞赛平台对预测器的理想性能进行了评估，发现其预测能力是足以满足预测条件的。但在实践过程中发现多分支取指时分支预测器和分支目标缓存内均会存在冲突的情况，这严重影响了预测器的性能。为了解决以上问题，在单个TAGE分支预测器的基础上增加了额外的预测通路，独立地保存和预测额外的分支指令信息。并利用硬件描述语言在超标量处理器中实现了这一预测器，同时将其与单个TAGE分支预测器进行了嵌入式处理器常用基准程序dhrystone、coremark和embench的性能对比实验。实验结果表明，优化后的分支预测器性能提高了14.1个百分点，而存储开销只增加了9.06%。最后通过实验数据分析，发现这一方案不仅有利于额外的分支指令预测，而且可以通过更加准确的分支历史信息获取实现更加准确的单分支取指预测。

关键词: 分支预测, TAGE, 嵌入式, 超标量, 处理器

YANG Ling, ZHOU Jinwen, WANG Jing, LAN Mengqiao, DING Zijian, YANG Shi, WANG Yongwen, HUANG Libo. Design and Implementation of Efficient Multi-branch Predictor[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(8): 1842-1851.

杨凌, 周锦文, 王京, 兰孟桥, 丁梓坚, 杨实, 王永文, 黄立波. 高效多分支预测器设计与实现[J]. 计算机科学与探索, 2023, 17(8): 1842-1851.

References

[1] SMITH J E, SOHI G S. The microarchitecture of supersca-lar processors[J]. Proceedings of the IEEE, 1995, 83(12): 1609-1624.
[2] YEH T Y, MARR D T, PATT Y N. Increasing the instruction fetch rate via multiple branch prediction and a branch address cache[C]//Proceedings of the 7th International Con-ference on Supercomputing, Tokyo, Jul 20-22, 1993. New York: ACM, 1993: 67-76.
[3] MITTAL S. A survey of techniques for dynamic branch pre-diction[J]. Concurrency and Computation: Practice and Ex-perience, 2019, 31(1): e4666.
[4] WALLACE S, BAGHERZADEH N. Multiple branch and block prediction[C]//Proceedings of the 3rd International Symposium on High-Performance Computer Architecture, San Antonio, Feb 1-5, 1997. Washington: IEEE Computer Society, 1997: 94-103.
[5] PERAIS A, SEZNEC A. BeBoP: a cost effective predictor infrastructure for superscalar value prediction[C]//Procee-dings of the 2015 IEEE 21st International Symposium on High Performance Computer Architecture, Burlingame, Feb 7-11, 2015. Washington: IEEE Computer Society, 2015: 13-25.
[6] HWANG S L, CHEN C C, LAI F. Multiple branch predic-tion for wide-issue superscalar[J]. IEICE Transactions on Infor-mation and Systems, 1999, 82(8): 1154-1166.
[7] SEZNEC A, MICHAUD P. A case for (partially) tagged geo-metric history length branch prediction[J]. The Journal of Instruction-Level Parallelism, 2006, 8: 23.
[8] SEZNEC A. A 64 Kbytes ISL-TAGE branch predictor[C]// Proceedings of the 2nd JILP Workshop on Computer Archi-tecture Competitions (JWAC-2): Championship Branch Predic-tion, San Jose, Jun 2011.
[9] SEZNEC A. A new case for the tage branch predictor[C]//Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture, Porto Alegre, Dec 3-7, 2011. New York: ACM, 2011: 117-127.
[10] SEZNEC A. TAGE-SC-L branch predictors[C]//Proceedings of the 4th JILP Workshop on Computer Architecture Com-petitions (JWAC-4): Championship Branch Prediction, Min-neapolis, Jun 2014.
[11] SEZNEC A. TAGE-SC-L branch predictors again[C]//Pro-ceedings of the 5th JILP Workshop on Computer Architec-ture Competitions (JWAC-5): Championship Branch Prediction, Seoul, Jun 2016.
[12] SEZNEC A. Exploring branch predictability limits with the MTAGE+SC predictor[C]//Proceedings of the 5th JILP Workshop on Computer Architecture Competitions (JWAC-5): Championship Branch Prediction (CBP-5), Seoul, Jun 2016: 4.
[13] SUGGS D, SUBRAMONY M, BOUVIER D. The AMD “Zen 2” processor[J]. IEEE Micro, 2020, 40(2): 45-52.
[14] EVERS M, BARNES L, CLARK M. The AMD next genera-tion Zen 3 core[J]. IEEE Micro, 2022, 42(3): 7-12.
[15] SEZNEC A. Storage free confidence estimation for the TAGE branch predictor[C]//Proceedings of the 2011 IEEE 17th International Symposium on High Performance Com-puter Architecture, San Antonio, Feb 12-16, 2011. Wa-shington: IEEE Computer Society, 2011: 443-454.
[16] JIMENEZ D A. Multiperspective perceptron predictor[C]// Proceedings of the 5th JILP Workshop on Computer Archi-tecture Competitions (JWAC-5): Championship Branch Pre-diction (CBP-5), Seoul, Jun 2016.
[17] SCHLAIS D J, LIPASTI M H. BADGR: a practical GHR implementation for TAGE branch predictors[C]//Procee-dings of the 2016 IEEE 34th International Conference on Computer Design, Scottsdale, Oct 2-5, 2016. Washington: IEEE Computer Society, 2016: 536-543.
[18] MICHAUD P. An alternative TAGE-like conditional branch predictor[J]. ACM Transactions on Architecture and Code Optimization, 2018, 15(3): 30.