Dynamic Branch Prediction

---

Dynamic branch prediction keeps a history for each branch as taken or untaken, and then using the recent past behavior to predict the future. The predictors can correctly predict branches up to more than 90% accuracy. One implementation of this approach is a branch prediction buffer, whose structure is shown in the previous slide. It uses a small memory indexed by the lower portion of the address of the branch instruction. The memory contains a bit that says whether the branch was recently taken or not.

• If the prediction is correct, then continue normal execution—no wasted cycles.


• Otherwise, flush the instructions that were incorrectly fetched—wasted cycles—and update prediction bit and target address for future use.

The 1-bit prediction scheme has a performance shortcoming. For example, a loop branch is almost always taken, except for last iteration. The 1-bit scheme will mispredict twice, on first and last loop iterations, considering the bit is flipped on prior execution of the last iteration of the loop.

To remedy this weakness, 2-bit prediction schemes are often used. By using 2 bits rather than 1, a branch that strongly favors taken or not take will be mispredicted only once. For example, loop branch is mispredicted only once on the last iteration.

The 2 bits can encode four states in the system. A branch prediction buffer can be implemented as a small, special buffer accessed with the instruction address during the IF pipe stage. If the instruction is predicted as taken, fetching begins from the target as soon as the PC is known. Otherwise, sequential fetching and executing continue. If the prediction turns out to be wrong, the prediction bits are changed as shown in the figure, where the blue lines are the predicted actions.