1. (9 marks) Suppose that a particular loop body is executed 10 times. There are three branches that are each executed a number of times whenever the loop body is executed. On each of the 10 executions of the loop body, the sequence of outcomes of each of these branches is as follows (N not taken; T taken):

Branch 1: T N T N T N

Branch 2: N N N N T

Branch 3: T T N T T N T

(a) Give the branch prediction accuracy (i.e., the percentage of times for which the branch outcome is predicted correctly) for each branch, assuming a scheme in which branches are always predicted as not taken.

(b) Repeat part (a), but now assuming use of a 1-bit branch predictor that predicts the branch outcome to be whatever the previous outcome was (for that same branch), with state initialized to predict not taken.

(c) Repeat part (a), but now assuming the 2-bit predictor discussed in class, initialized to strongly predict not taken (i.e., such that two consecutive incorrect predictions are required before it would change its prediction to taken).