Slide 14.16: Branch prediction schemes

Branch Prediction Schemes

There are many methods to deal with the pipeline stalls caused by branch delay. Four simple schemes are given as follows.

Pipeline Stalling

The simplest scheme to handle branches is to freeze or flush the pipeline, holding or deleting any instructions after the branch until the branch destination is known.

Prediction of Not Taken

This method is described in the previous slides. It predicts the branch as not taken, simply allowing the hardware to continue as if the branch were not executed. This scheme behaves as shown in the following two tables. When branch is not taken, we have fetched the fall-through and just continue. If the branch is taken, restart the fetch at the branch target.

Clock cycle	1	2	3	4	5	6	7
Untaken branch	IF	ID	EX	MEM	WB
Branch successor		IF	ID	EX	MEM	WB
Branch successor+1			IF	ID	EX	MEM	WB

Clock cycle	1	2	3	4	5	6	7	8
Taken branch	IF	ID	EX	MEM	WB
Branch successor		IF (stall)	stall	stall	stall	stall
Branch target			IF	ID	EX	MEM	WB
Branch target+1				IF	ID	EX	MEM	WB

Delayed Branch

Compilers and assemblers try to place an instruction that always executes after the branch in the branch delay slot.

Dynamic Branch Prediction

For example, look up the address of the instruction to see if a branch was taken the last time this instruction was executed, and, if so, to begin fetching new instructions from the same place as the last time.