Assume that you have a simple bimodal branch predictor (table of 2-bit [N,n,t,T] state machines indexed by the PC) and that all predictors are initially in the t state.

a)If, for a given branch A, the sequence of (actual) directions is T, N, N, T, N, N, T, N, N

i)For each dynamic instance of A, give the corresponding prediction.

ii)What is the total hit count for the 9 predictions above? If As pattern repeats forever, and no other branches alias to the same state machine, what will the final prediction rate converge to?

b)Consider another branch B where the code containing B is only executed on the taken path of A, and B is consistently in the pattern T,T,T,N for each taken instance of A, and no dynamic instances of A will be seen within the code containing B.

i) If A and B do not alias to the same table entry and are the only two branches encountered, what is the overall branch prediction accuracy after the 9th dynamic instance of A has been predicted?

ii) If A and B do alias to the same table entry and are the only two branches encountered, what is the overall branch prediction accuracy after the 9th dynamic instance of A has been predicted?

c)Assume that, instead of a simple bimodal branch predictor, you have a 2-level predictor of the following form: each PC indexes into a 4-entry table of state machines indexed by a 2-bit per-branch history. Assuming that all state machines are initially at n and that history is assumed to begin with NN, repeat 3a for the 2-level predictor.