1. Branch history tables: execute a program that contains the following high-level code segment:
A[8] = {5,3,4,9,2,1,8,4}
for (i = 0; i<8; i++) {
if (A[i] < 6) {
//fall - through code goes here
}
else {
//branch taken code goes here
}
}
When compiled, this code contains two branches, as shown below. The BNE is part of the IF statement above - if the condition is true,the branch is not taken; if the condition is false, the branch is taken. The BEQ controls the loop.
Branch Address
Dec Hex
20 0*14 Loop: ...
....
40 0*28 BNE R3, RO, ELSE #if (false) jump to Else, i.e. A[I]>=6
....
52 0*34 BEQ R6, R7, Loop #if (i<8) jump to loop
....
The processor contains an eight-entry, 2-bit branch history table (BHT), its state when the processor reaches this code segment is as follows:
Entry # Value
0 10
1 11
2 01
3 00
4 01
5 00
6 11
7 10
Determine the overall misprediction rae (#mispred / #total-branches ) of the branch predictor for this code.
2.Correlating branch predictors: now suppose you have a 4-line (2,2) correlating branch predictor, with all entries initially set to 11, and the initial global history is 11. Determine the overall accuracy (#good-preds) / #total-branches ) of this predictor using the same code as in problem 1