Comparison of Branch History and branch Correlated Prediction Techniques

摘要

Conditional branch instructions are recognized as major impediments for high performance processors. These branches are control dependencies that cause stalls in a processor's execution and keep the processor from reaching maximum performance. The goal of branch prediction is to allow the processor to resolve the outcome of a branch early. This prediction prevents a branch from cauisng a stall and allows the processor to perform speculative execution before the outcome of a branch is determined. Branch prediction plays an important role in the processor because a single issue processor will encounter one branch approximately every five instructions. In a n-issue processor, branches will arrive up to n times faster requiring a multiple issue processor to predict a branch every issue cycle. The goal of this paper is to provide a comparative study of two dynamic branch prediction techniques: branch history based prediction and correlated branch prediction. The details of these techniques will be explained and copared. Results of prgram trace simulations from a study done by McFarling are presented to show the effectiveness of these prediction techniques. It will be shown the effectiveness of these prediction techniques. It will be shown that overall the correlated techniques perform better than simple history based techniques but require higher implementation costs to be effective.