Study of Ahead Branch Prediction Architecture and Algorithm

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.