Branch Prediction

Previous: Pipelining Next: Superscalar

In order to make pipelining work efficiently, it is necessary to keep all the stages full. However, there is a problem whenever an instruction is encountered that alters the sequential flow of control in the program. If statements, loop statements, and procedure statements cause problems with the pipeline. Consider the following code,

if (x > 0) {
     a=0;
     b=1;
     c=2;
}
d=3;

Cycle Fetch Decode Execute Save
1 if (x>0)
2 a=0 if (x>0)
3 b=1 a=0 if (x>0)
4 c=2 b=1 a=0 if (x>0)
5 c=2 b=1 a=0
6 c=2 b=1
7 c=2
If x is greater than 0, then the instructions in the pipeline are correct, since the body of the if statement would get executed.
Cycle Fetch Decode Execute Save
1 if (x>0)
2 a=0 if (x>0)
3 b=1 a=0 if (x>0)
4 d=3 squash b=1 squash a=0 if (x>0)
5 d=3 squash b=1 squash a=0
6 d=3 squash b=1
7 d=3
However, if x is less than or equal to 0, then the body of the if will not be executed. In this case, the next instruction in the pipeline should be d=3, and the instructions involving a, b, and c should not be in the pipeline. In this case, it would be necessary to cancel any efffects that these instructions had on the state of the processor, and to remove these instructions from the pipeline. This is known as squashing the instruction. Assuming that this could be done, then the instruction d=3 would be fetched at the start of cycle 4, when the result of the comparison x>0 is known. In this case, the pipeline is less efficient, since some of the stages are not being used to execute valid instructions. It would take 7 cycles to complete these two instructions.
Cycle Fetch Decode Execute Save
1 if (x>0)
2 d=3 if (x>0)
3 d=3 if (x>0)
4 d=3 if (x>0)
5 d=3
If it were possible to look into the future, and to know what the result of the comparison would be, then it would be possible to keep the pipeline full. For instance, if it were known ahead of time that the result of the comparision would be false, then the computer could load the instruction d=3 instead of the instruction a=0. If this were the case, then these two instructions would take only 5 cycles.

This is the idea behind branch prediction. Try to guess ahead of time which way a branch instruction will go. If the guess is correct, then the pipeline will remain full. If the guess is incorrect, then some squashing will take place and the pipeline will be less efficient. It is possible to get 90% of the guesses correct using branch prediction.

Previous: Pipelining Next: Superscalar