Please, I need help on this question. Given the sequence of the actual taken (T)
ID: 3669182 • Letter: P
Question
Please, I need help on this question.
Given the sequence of the actual taken (T)/not taken (N) outcomes of a particular branch:
N, T, N, T, N, T, N, N, N, N.
a) What is the misprediction rate if a one-bit history dynamic branch predictor is used to
predict these 10 branch instances? Assume the initial state is Not Taken.
b) What is the misprediction rate if a two-bit saturation counter branch predictor is used?
Assume the initial instate is weakly not taken.
c) Four pipelined MIPS processors differ from each other only in the way branch is handled.
Assume branch decision and target address are available at the end of the ID stage.
P1: Stall until branch target is clear; branch penalty is 3 cycles.
P2: Predict branch Not Taken; branch penalty is 1 cycle.
P3: Predict branch Taken; branch penalty is 1 cycle.
P4: Delayed Branch; branch penalty is 0.5 cycle.
Assume 4% of unconditional branch, 6% of conditional branch-untaken, and 10% of
conditional branch-taken for a benchmark program. Compute the average CPI (clock
cycles per instruction). Also assume that the ideal CPI is 1.0.
Explanation / Answer
•
Correlating branch predictors also look at other branches for clues.
Consider the following example.
if (aa==2)
-- branch b1
aa = 0;
if (bb==2)
--- branch b2
bb = 0;
if(aa!=bb) { ... ---
branch b3 – Clearly depends on the results of b1 and
b2
Prediction if the last branch is NT
Prediction if the last branch is
T
(1,1) predictor – uses history of 1 branch and uses a 1-bit predictor
8
Another Example
If (d==0)
d=1;
If (d=1) ---
Code Sequence assuming d is assigned to R1:
BNEZ R1, L1
;
branch b1 (d!=0)
DADDU R1,R0,#1
;
d==0, so d=1
L1: DADDIU R3,R1,#-1
BNEZ R3,L2
;
branch b2 (d!=1)
Possible Execution Sequence for the code fragment;
Initial d d==0? B1 d before b2 d==1? b2
0 yes not taken 1 yes not taken
1
no taken 1 yes not taken
2
no taken 2 no taken
f we use 2 branches as histories, then there are 4 possibilities
(T-T, NT-T, NT-NT, NT-T).
•
For each possibility, we need to use a predictor (1-bit or 2-bit).
•
And this repeats for every branch.
(2,2) branch prediction