Problem 3: Dynamic Branch Prediction (16 points)

Consider the following MIPS code. The register R0 is always 0.

DADDI R1, R0, 2

L1: DADDI R12, R0, 4

L2: DSUBI R12, R12, 1

BNEZ R12, L2 -- Branch 1

DSUBI R1, R1, 1

BNEZ R1, L1 -- Branch 2

Each table below refers to only one branch. For instance, branch 1 will be executed 8 times. Those 8 times should be recorded in the table for branch 1. Similarly branch 2 is executed only 2 times.

Now assume that 2 level correlating predictors of the form (2,1) are used. Also assume that the branch predictor table has only 1 row. When the processor starts to execute the above code, the outcome of the previous two branches is not taken (N). Also assume that the initial state of predictors of all branches is not taken (N). What is the number of correct predictions? Use the following table to record your steps. Record the "New State" of predictors in the form W/X/Y/Z where,

W - state corresponds to the case where the last branch and the branch before the last are both TAKEN

X - state corresponds to the case where the last branch is TAKEN and the branch before the last is NOT TAKEN

Y - state corresponds to the case where the last branch is NOT TAKEN and the branch before the last is TAKEN

Z - state corresponds to the case where the last branch and the branch before the last are both NOT TAKEN The first entry is filled in for you.

Branch 1 Actual Branch 1 New State Step Branch 1 Prediction Action Branch 2 Actual Branch 2 New State Step Branch 2 Prediction Action n begins? Show your work