Question

Given this piece of code fragment: (10%)

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

    if ( x % 4 >= 2)

        cout << "OK" << endl;

Assuming the branch prediction by default is “TAKEN”,

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

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

Answer 1

If we use 1 bit branch history then we will have 2 states and they are as below

taken 1 Alway s taken takin ta ken = o 2-

Hence we have if ( x % 4 >= 2) and the values of x are from 0 to 9

for x=0 , 0 % 4 =0 and it is not >= 2 so branch wont take as the defualt prediction is taken

means we are the taken stage hence it will fail.

Now the prediction changed to branch not taken.

for x=1 , 1 % 4 =1 and it is not >= 2 so branch wont take as we are presently at

not taken stage hence it will pass.

Now the prediction wont change and it will be still at branch not taken.

for x=2 , 2 % 4 =2 and it is >= 2 so branch will take but we are presently at

not taken stage hence it will fail.

Now the prediction will change to branch taken.

for x=3 , 3 % 4 = 3 and it is >= 2 so branch will take and we are presently at

taken stage hence it will pass.

Now the prediction wont change and it will be at branch taken.

for x=4 , 4 % 4 = 0 and it is not >= 2 so branch wont take and we are presently at

taken stage hence it will fail.

Now the prediction will change to branch not taken.

for x=5 , 5 % 4 = 1 and it is not >= 2 so branch wont take and we are presently at

not taken stage hence it will pass.

Now the prediction wont change and it will be at branch not taken.

for x=6 , 6 % 4 = 2 and it is >= 2 so branch will take and we are presently at

not taken stage hence it will fail.

Now the prediction will change to branch taken.

for x=7 , 7 % 4 = 3 and it is >= 2 so branch will take and we are presently at

taken stage hence it will pass.

Now the prediction wont change and it will be at branch taken.

for x=8 , 8 % 4 = 0 and it is not >= 2 so branch wont take and we are presently at

taken stage hence it will fail.

Now the prediction will change and it will be branch not taken.

for x=9 , 9 % 4 = 1 and it is not >= 2 so branch wont take and we are presently at

not taken stage hence it will pass.

Now the prediction wont change and it will be at branch not taken.

Out of 10 cases 5 cases are passed hence our accuracy is 50%.

If we use 2 bit branch history then we will have 4 states and they are as below

ta ken Alway Always taten 2- ta Ken 。 tatin = 1 takin taken 3 s, ESgヲstrongly-pred leted States

Hence we have if ( x % 4 >= 2) and the values of x are from 0 to 9

for x=0 , 0 % 4 =0 and it is not >= 2 so branch wont take as the defualt prediction is taken

means we are the taken stage S1 hence it will fail.

Now the prediction changed to branch taken S2.

for x=1 , 1 % 4 =1 and it is not >= 2 so branch wont take as we are presently at

taken stage S2 hence it will fail.

Now the prediction will change to not taken S3.

for x=2 , 2 % 4 =2 and it is >= 2 so branch will take but we are presently at

not taken S3 stage hence it will fail.

Now the prediction will change to branch taken S4.

for x=3 , 3 % 4 = 3 and it is >= 2 so branch will take and we are presently at

taken S4 stage hence it will fail.

Now the prediction will change and it will be at branch taken S1.

for x=4 , 4 % 4 = 0 and it is not >= 2 so branch wont take and we are presently at

taken S1 stage hence it will fail.

Now the prediction will change to branch taken S2.

for x=5 , 5 % 4 = 1 and it is not >= 2 so branch wont take and we are presently at

taken S2 stage hence it will fail.

Now the prediction will change and it will be at branch not taken S3.

for x=6 , 6 % 4 = 2 and it is >= 2 so branch will take and we are presently at

not taken S3 stage hence it will fail.

Now the prediction will change to branch not taken S4.

for x=7 , 7 % 4 = 3 and it is >= 2 so branch will take and we are presently at

not taken S4 stage hence it will fail.

Now the prediction will change and it will be at branch taken S1.

for x=8 , 8 % 4 = 0 and it is not >= 2 so branch wont take and we are presently at

taken S1 stage hence it will fail.

Now the prediction will change and it will be branch taken S1.

for x=9 , 9 % 4 = 1 and it is not >= 2 so branch wont take and we are presently at

taken S2 stage hence it will fail.

Now the prediction wont change and it will be at branch not taken S3.

Out of 10 cases 0 cases are passed hence our accuracy is 0%.