In this exercise, assume that the breakdown of the dynamic instruction count of a program into various instruction categories is as follows:

Also, assume the following branch predictor accuracies:

Assumptions: If prediction is correct, no stall cycles are incurred. If prediction is incorrect, 1 stall cycle is incurred for all 3 branch predictor schemes mentioned above. Note: Here you do not need to know the control point for the branch decision, i.e. ID, EX or MEM, since the number of penalty cycles is already provided.
Also, there are no data hazards in the program. CPI=1 for all instructions where no extra stall cycle is incurred.
A) What is the overall CPI accounting for mispredicted branches with the always-taken predictor? (2.5 pts)
B) What is the overall CPI accounting for mispredicted branches with the always-not-taken predictor?
(2.5 pts)
C) What is the overall CPI accounting for mispredicted branches with the 2-bit predictor?
(2.5 pts)
D) With the 2-bit predictor, what speedup would be achieved if we could convert half of the branch instructions in a way that replaced each branch instruction with two ALU instructions? Assume that correctly and incorrectly predicted instructions have the same chance of being replaced. (2.5 pts)

Q2 (10 pts)
This exercise examines the accuracy of various branch predictors for the following repeating pattern (e.g., in a loop) of branch outcomes: T, NT, T, T, NT. (T=branch taken, NT=branch not taken)
A) What is the accuracy (“score card” in 16-17.ppt) of always-taken and always-not-taken predictors for this sequence of branch outcomes provided we encounter this branch outcome sequence only once?
(2 pts)

B) What is the accuracy (“score card) of the 2-bit predictor for this sequence of branch outcomes provided we encounter this branch outcome sequence only once, assuming that the predictor starts off in the “Strongly Predict Not Taken” state (“SNT”)? (3 pts)