Introduction

There are 7 common prediction schemes:

• 1-bit branch history table

• 2-bit branch history table also known as bimodal predictor

• Local branch predictor

• global branch predictor

• gselect

• gshare

• Tournament predictors

1-bit branch history table

Branch prediction usually involves branch history table (BHT). The entries are indexed by lower bits of program counter (PC). In case of 1-bit branch history table the entry says if the branch was taken (1) or not taken (0) last time. Initially all bits are set to zero and no branch will be taken. The prediction is hint, fetching begins at predicted branch. If it was wrong the instructions are flushed from the pipeline and instruction is fetched from the other branch. In a nested loop 1-bit BHT will cause two mispredictions: first time through loop when exit is predicted and in the end of loop when jump is predicted.

Bimodal predictor

Bimodal predictor adds second bit in which case there are four states: predict taken strongly, predict taken weakly, predict not taken weakly, predict not taken strongly. Can be implemented with 2-bit shift or 2-bit saturating counter.

Local branch predictor

Local history branch predictor keeps track of previous branching decisions in a local history table which is indexed by lower bits of branch PC. Branches may refer to same history entry.

Global branch predictor

Global history branch predictor keeps global history of jumps regardless of branch PC.

gselect n/m

Global history with selected address bits also known as gselect n/m uses n-bits of branch PC and m-bits from global history. One could also say that bimodal predictor is gselect n/0 and global branch predictor is gselect 0/m.

gshare n/n

Global history with index sharing also known as gshare n/n uses XOR operation to mix lower n-bits of branch PC with n-bit global history pattern.

Tournament predictor

Tournament predictor uses multiple predictors, usually one based on local and one based on global information. Tournament predictor selects between them depending on their accuracy.

Branch Target buffer includes branch prediction AND branch target address.

Integrated branch prediction means that branch predictor is part of instruction fetch (IF) unit and constantly predicts branches.

Instruction prefetch means that instructions are fetched ahead (prefetching).

The instruction fetch (IF) unit uses prefetching to hide cost of crossing cache blocks and it provides a buffer that contains instructions in execution order.