I\'ve the answer for the first and third one. Please explain and show your work.

ID: 3853935 • Letter: I

Question

I've the answer for the first and third one. Please explain and show your work.

1. A code section of a program has the branch behavior of N,N,T,T,N,N,N,N,T,N where N is do not take the branch and T is take the branch. What is the %accuracy of a one-bit predictor for this behavior if initially in the TAKE state and the section is only executed once? Answer is 50%

2. A code section of a program has the branch behavior of N,N,T,T,T,T,T,T,T,T where N is do not take tge branch and T is take the branch. What is the %accuracy of a two-bit predictor for this behavior if initially in the strongly NOT TAKE state and the section is only executed once?

3. 1.A pipeline is being designed for a micro-processor. A sample workload consists of 2 million instructions, each with an execution time of 25 ns on a non-pipelined datapath. Approximately how long does this program take to run on an ideally 5-stage pipelined processor? Answer is 10.

Explanation / Answer

one bit predictor will have an initial prediction and if the prediction fails it will change the prediction.

Given branch behavior is N,N,T,T,N,N,N,N,T,N and initial prediction is T.

Hence 1st prediction will fail ------> Prediction is T but branch is N.

Now Prediction will change to N.

2nd prediction will pass ------> Prediction is N and branch is N.

Now Prediction will not change.

3rd prediction will fail ------> Prediction is N but branch is T.

Now Prediction will change to T.

4th prediction will pass ------> Prediction is T and branch is T.

Now Prediction will not change.

5th prediction will fail ------> Prediction is T but branch is N.

Now Prediction will change to N.

6th prediction will pass ------> Prediction is N and branch is N.

Now Prediction will not change.

7th prediction will pass ------> Prediction is N and branch is N.

Now Prediction will not change.

8th prediction will pass ------> Prediction is N and branch is N.

Now Prediction will not change.

9th prediction will fail ------> Prediction is N but branch is T.

Now Prediction will change to T.

10th prediction will fail ------> Prediction is T but branch is N.

Now Prediction will change to N.

Here out of 10 predictions 5 passed and 5 failed.

Hence %accuracy of a one-bit predictor is = Total predictions passed / Total Number of predictions * 100

= 5/10 *100 = 50%

Hence %accuracy of a one-bit predictor is = 50%.

two bit predictor will have an initial prediction and if the prediction fails consecutively

two times then it will change the prediction.

Given branch behavior is N,N,T,T,T,T,T,T,T,T and initial prediction is N (strongly NOT TAKE).

Hence 1st prediction will pass ------> Prediction is N and branch is N.

Now Prediction will not change and it will be in strongly NOT TAKE.

2nd prediction will pass ------> Prediction is N and branch is N.

Now Prediction will not change and it will be in strongly NOT TAKE.

3rd prediction will fail ------> Prediction is N but branch is T.

Now Prediction will not change and it will be in weakly NOT TAKE.

4th prediction will fail ------> Prediction is N and branch is T.

Now Prediction will change and it will be in weakly TAKE.

5th prediction will pass ------> Prediction is T and branch is T.