Branch Predictors

Branching is a common occurrence in programs. Any if/else statements and for/while-loops are coding practices based on conditional branching. However, in a pipelined processor, instructions are constantly being fed into the pipeline; and the processor does not know what direction the branch is. Thus, if the wrong direction is taken, then some work has effectively been lost, since the processor now needs to flush out the pipeline and retrieve the correct instructions from memory.

Branch predictors mitigate the problem by essentially "guessing" the direction of a branch instruction. The performance of a predictor rests on the correctness of the predictor or how early the branch is resolved. There are numerous techniques in improving predictor performances. For my project, my team utilized three techniques: a branch target buffer (BTB), a 2-level global predictor, and early resolution in execute stage.

Early Branch Resolution in Execute Stage

Normally, the branch is resolved after the EX stage and during the MEM stage, when the results of the comparator is stored in the stage barrier. This means that, as opposed to the normal 3-cycle penalty, resolving the branch in EX stage would only result in a 2-cycle penalty.

Predictors

Branch Target Buffer

Branch predictors only contain information about the predicted direction of a branch. Without a target PC value to jump to, a prediction is fairly useless.
To solve this, one must use a branch target buffer. A branch target buffer is a type of cache that stores the address of branch instructions along with their target PC value.