Consider the following sequence of outcomes for a particular branch instruction:
T, NT, T, NT, T, NT, T, NT….
Assume this sequence repeats indefinitely.
Part A: The Easy Part
What is the
long-term
(steady-state) accuracy of the predict-taken predictor? What about predict-not-taken?
Part B: 1-bit predictor
What is the long-term (steady-state) accuracy of the 1-bit predictor? If its initial state matters, explain.
Part C: 2-bit predictor
What is the long-term (steady-state) accuracy of the 2-bit predictor? If its initial state matters, explain.
Part D: Custom Predictor
Design your own predictor that uses no more than 2 bits of state to maximize prediction accuracy for this pattern. Show the state diagram, and give the long-term accuracy of your predictor. If its initial state matters, explain.