A processor uses a 2-bit saturating branch predictor with the states "strongly taken", "weakly taken", "weakly not taken", and "strongly not taken". The symbol T indicates a branch that is taken and an N indicates a branch that is not taken. Suppose that the following sequence of branches is encountered: T T T N N T T N T
a. Starting at the first "not-taken" branch, what would the prediction have been for each branch? How many times was the predictor correct?
b. After this sequence of branches is encountered, what state will the predictor be in, and what will be the prediction for the next branch? Explain your reasoning.