Question

Computer archieture
1. Given this piece of code fragment:

for (int x = 0; x < 10; x++)

{

    if (x >= 5)

        cout << "OK" << endl;

}

Assuming the branch prediction by default is “TAKEN”,

1. What is the accuracy of branch prediction of the cout statement when we use a 1-bit branch history?

2. What is the accuracy of branch prediction of the cout statement when we use a 2-bit branch history?

Answer 1

1-bit brach predictor:

Iter#	Pred bit	Actual Outcome	Update
5	N	T	T (wrong)
6	T	T	T
7	T	T	T
8	T	T	T
9	T	T	T

Accuracy : (4/5) *100 = 80%

2-bit brach predictor:

Start with N0 and initial prediction is N and when prediction is not correct use above diagram.

Iter#	Pred bit	Predicted Outcome	Actual Outcome	Update
5	N0	N	T	N1(wrong)
6	N1	N	T	T0(wrong)
7	T0	T	T	T0
8	T0	T	T	T0
9	T0	T	T	T0

Accuracy : (3/5) *100 = 60%