Problem #5 (a) Assume that a branch has the following sequence of actual outcomes, where I means branch is taken and N means branch is not taken (T): T, T, T, N, N, T, T, T, N, N, T, T, T, N, N What is the prediction accuracy for a 2-bit predictor for the above branch sequence if the predictor starts off in the bottom left state (predict not taken)? Show all your work to get full credit. Taken Not taken Predict taken Predict taken Taken Not takon Takon Not taken Predict not taken Predict not taken Taken taken (b) Consider the following code segment within a loop body: if (x is even) then ;(branch bl) increment a ;(branch b1 taken) if ( x is multiple of 10) then ;(branch b2) increment b ; (branch b2 taken) Assume that 2-bit state machine (see above) is used as the prediction algorithm for predicting the execution of the two branches in this loop. Indicate the predicted and actual branch directions of the bl and b2 branch instructions for each iteration of this loop. Assume initial state of 00, i.e., NT, for the predictor. Assuming that the following list of 9 values of x is processed by 9 iterations of this loop. X= 8 10 11 12 20 29 30 31 bl predicted: bl actual: b2 predicted: 62 actual: 9 What are the prediction accuracies for bl and b2? What is the overall prediction accuracy? Problem #5 (a) Assume that a branch has the following sequence of actual outcomes, where I means branch is taken and N means branch is not taken (T): T, T, T, N, N, T, T, T, N, N, T, T, T, N, N What is the prediction accuracy for a 2-bit predictor for the above branch sequence if the predictor starts off in the bottom left state (predict not taken)? Show all your work to get full credit. Taken Not taken Predict taken Predict taken Taken Not takon Takon Not taken Predict not taken Predict not taken Taken taken (b) Consider the following code segment within a loop body: if (x is even) then ;(branch bl) increment a ;(branch b1 taken) if ( x is multiple of 10) then ;(branch b2) increment b ; (branch b2 taken) Assume that 2-bit state machine (see above) is used as the prediction algorithm for predicting the execution of the two branches in this loop. Indicate the predicted and actual branch directions of the bl and b2 branch instructions for each iteration of this loop. Assume initial state of 00, i.e., NT, for the predictor. Assuming that the following list of 9 values of x is processed by 9 iterations of this loop. X= 8 10 11 12 20 29 30 31 bl predicted: bl actual: b2 predicted: 62 actual: 9 What are the prediction accuracies for bl and b2? What is the overall prediction accuracy
