3) Branch prediction 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 A's 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 predictedi? 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? ii) 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. 3) Branch prediction 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 A's 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 predictedi? 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? ii) 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
