提前分支预测结构及算法研究  

Study of Ahead Branch Prediction Architecture and Algorithm

作　　者：靳文兵[1,2] 石峰[1] 左琦[1] 张杨[1] 

机构地区：[1]北京理工大学计算机学院,北京100081 [2]北方自动控制技术研究所,太原030006

出　　处：《计算机研究与发展》2013年第10期2228-2238,共11页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60973010)

摘　　要：在理论上,越来越复杂的分支预测算法和更大的存储结构会使分支预测精度不断提高,但当前复杂算法和庞大数据结构所引发的分支预测时延已无法满足流水线单周期运行要求.针对分支预测精度和时延的矛盾,设计提出提前分支预测结构(ahead branch prediction architecture,ABPA).ABPA为流水线前端取指部件提供简单的分支预测表,以实现快速分支预测;复杂的预测算法和较大的存储结构均被移至流水线后端实现,从而保证了分支预测精度.对于一直难以准确预测的多目标间接分支指令,设计提出基于分支历史和目标路径的间接分支预测算法(indirect branch prediction algorithm based on branch history and target path,BHTP algorithm).提前分支预测算法采用改进的高精度分支预测算法和BHTP算法的混合.嵌入提前分支预测算法的分支预测引擎实现流水线后端的分支推测和目标预测,以及流水线前端的分支预测表更新.实验结果表明:采用ABPA结构和BHTP算法的分支预测系统平均精度达到94.27%.设计不仅实现了快速、高精度分支预测,更为分支预测的深入研究提供了条件.Modern computers rely on branch prediction to boost instruction-level parallelism. Theoretically, branch predictors with more complicated algorithms and larger data structures provide more accurate branch predictions. Unfortunately, overly large structures and excessively complicated algorithms cannot be implemented in reality because of their overlong response time. Up to now, many strategies have been proposed to trade-off delay versus accuracy, but none of them has been accepted by industry institutes. Ahead branch prediction architecture （ABPA） presents a short table with branch-target pairs in the front end of the pipeline, which makes the branch prediction brief enough even for some aggressive processors. At the same time, hybrid algorithms and data structures for accurate prediction are all moved to the back end of the pipeline. An effective mechanism for branch prediction ahead in the back end and updating the branch-target table in the front end in time is proposed, and an indirect branch prediction algorithm based on branch history and target path （BHTP） is also implemented in ABPA. Experimental results with SPEC benchmarks on GemS/ SimpleScalar show that ABPA improves branch prediction rate by 4.72% compared with a commonly used branch target buffer-based predictor. In addition, the mispredictions for indirect branches under hybrid algorithms with BHTP reduce by an average of 32% compared with the traditional algorithms.

关 键 词：分支预测 分支推测 分支目标缓存 间接分支指令 指令流水线 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]