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