(by E. Collins, S. Carpenter, and N. Thomas) in the Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics (SCI'98) and the 4th International Conference on Informatics Systems Analysis and Synthesis (ISAS'98), Orlando, FL, July, 1998, Vol. 2, pp. 658-663.
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 causing 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 compared. Results of program trace simulations from a study done by McFarling are presented to show 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.
[ Published listings ] [ Top ]