1-bit branch predictor
Consider the following code
Algorithm:
// for (x1=3; x1 != 0; x1=x1-1)
// x2 = x2 + x3
RISC-V code:
0000 addi x1, x0, 3 // x1 = 3
L:
0004 add x2, x2, x3 // x2 = x2 + x3
0008 subi x1, x1, 1 // x1 = x1 - 1
000C bne x1,0,L // if (x1 != 0) branch to L
Complete the following table showing the branch predictor behaviour (ONLY ANSWER ANYTHING DENOTED AS CHOOSE AND CHOOSE ONE OPTION). Note that * indicates an instruction fetch (IF) from a predicted branch. For simplicity, assume that a mis-predicted branch only costs one cycle (the fetch of the instruction following the branch mis-prediction).
Clock Cycle |
IF Address |
x1 | Branch Predictor Value (start of cycle) |
Correct Prediction |
Branch Taken |
---|---|---|---|---|---|
0 | 0000 | ||||
1 |
0004 |
3 | |||
2 |
0008 |
||||
3 |
000C |
2 | 0 | ||
4 | 000E* | 0 | no | yes | |
5 | 0004 | 1 | |||
6 | 0008 | ||||
7 | 000C | 1 | 1 | ||
8 | 0004* | CHOOSE: 1 or 0 | CHOOSE: yes or no | CHOOSE: yes or no | |
9 | 0008 | ||||
10 | 000C | 0 | CHOOSE: 1 or 0 | ||
11 | 0004* | CHOOSE: 1 or 0 | CHOOSE: yes or no | CHOOSE: yes or no | |
12 | 0010 | CHOOSE: 1 or 0 |
【General guidance】The answer provided below has been developed in a clear step by step manner.Step1/2CyclePCX1X2XBranch PredictionReason10000*300Not takenInitial fetch20004*300Not takenPredict not taken30008*200TakenPredict taken4000C*200Not takenMispredict, correct50004*200TakenMispredict, correct60008*100TakenPredict taken7000C*100Not takenMispredict, correct80004*100TakenMispredict, correct90008*000TakenPredict taken10000C*000Not takenMispredict, correct11done0??N/AEnd of programExplanation:At cycle 1, the initial instruction fetch from address 0x0000 is not a branch instruction, so the branch predictor does not make any prediction.At cycle 2, the add instruction at address 0x0004 is not a branch instruction, so the branch predictor does not make any prediction.ExplanationAt cycle 3, the subi instruction at address 0x0008 is a branch instruction. Since th ... See the full answer