(Exercise 4.16) [25pt] 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
a. What is the accuracy of always-taken and always-not-taken predictors for this sequence of branch outcomes?
b. What is the accuracy of the two-bit predictor for the first 4 branches in this pattern, assuming that the predictor starts off in the bottom left state from Figure 4.63 (predict not taken)?
c. What is the accuracy of the two-bit predictor if this pattern is repeated forever?
d. Design a predictor that would achieve a perfect accuracy if this pattern is repeated forever. You predictor should be a sequential circuit with one output that provides a prediction (1 for taken, 0 for not taken) and no inputs other than the clock. Just explain in words.
e. What is the accuracy of your predictor from (d) if it is given a repeating pattern that is the exact opposite of this one (NT, T, NT, NT, T)?