Branch Target Buffers

Branch prediction schemes based on branch history of a single branch or correlation between branches must be applied in the R stage of the pipeline, once the instruction is identified as a branch.

To reduce the branch penalty further, we need to identify a branch and its predicted target in the I stage by using a branch target buffer.

The branch target buffer is a true cache, the full PC value must be conpared to validate that this is a branch instruction before taking any action (we don't want to branch on an add instruction).

The target buffer scheme works as follows:

with penalties:

BTBPredictionActual BranchPenalty
Hit Taken Taken 0
Hit Taken Not Taken Condtion delay
Miss Taken Condition delay
Miss Not Taken 0

Variations

Store target instruction in BTB
This is called branch folding and results in zero-cycle jumps and correctly predicted conditional branches.
Use return address stack
Speculation - fetch from both paths.

Typically, 90% prediction accuracy and buffer hit rate is seen.


[up] to Branch Prediction.