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 8 9
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 9
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.



      “When you make a choice, you change the future.”    
      ― Deepak Chopra