ISSN 1000-1239 CN 11-1777/TP

• Paper • Previous Articles     Next Articles

Study of Ahead Branch Prediction Architecture and Algorithm

Jin Wenbing1,2, Shi Feng1, Zuo Qi1, and Zhang Yang1   

  1. 1(School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081) 2(North Automatic Control Technology Institute, Taiyuan 030006)
  • Online:2013-10-15

Abstract: 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 Gem5/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.

Key words: branch prediction, branch speculation, branch target buffer, indirect branch, instruction pipeline