Of course, the prediction could be wrong. We cannot determine this until the ID phase, however. Remember, in the IF phase, we do not know what kind of instruction we are executing - this is only determined in the ID phase. Therefore, in the ID phase, we calculate the branch target anyway. We then compare the calculated branch target with the predicted PC (by comparing it to the PC register). If the prediction is correct, all is well, but if it is wrong (or if we did not predict the target address because of a BTB miss), we need to stall the pipeline and update the BTB (connections 3, 4 and 5).
So there are 3 different situations:
| 1. | The branch is not in the BTB We update the PC with PC+4. When the branch gets to the ID phase, we stall the pipeline to update the BTB. |
| 2. | The branch is in the BTB, but the prediction is wrong We update the PC with the predicted PC. When the branch gets to the ID phase, we stall the pipeline to update the BTB. |
| 3. | The branch is in the BTB and the prediction is correct We update the PC with the predicted PC. When the branch gets to the ID phase, no action is taken. |
Try it out. See a demonstration of branch prediction. Notice that all three situations listed above occur when the program is executed.
Conditional Branches
The MIPS processor supports two conditional branches: beqz (branch if equal to zero) and bnez (branch if not equal to zero). Both these instructions take an arbitrary register as a source operand. This yields another data hazard:
| add r1, r2, r3 | |
| bneq l1, r1 | |
| sub r2, r3, r1 | |
| l1: | :xor r3, r2, r1 |
| ori r3, r1, 10 |
Consider the execution of this program in the pipeline:
| Cycle | IF | ID | EX | MA | WB | |
|---|---|---|---|---|---|---|
| 1 | add | |||||
| 2 | bneq | add | We could use a BTB here, or predict-not-taken | |||
| 3 | sub | bneq | add | Now we need to check if our prediction was correct |
advertisement
advertisement