Please Explain how to they got that answer [2] A program includes a branch instr
ID: 3912556 • Letter: P
Question
Please Explain how to they got that answer
[2] A program includes a branch instruction. The branch instruction is executed 13 times. The outcome for each execution of the branch instruction is given below Determine the number of correct predictions when using the following prediction methods: Predict NT One-bit prediction (initialized to "Predict NT") (a) Predict NT13/13 (b) Predict NT=6/13 (c) Predict NT = 7/13 one-bit prediction 5/13 One-bit prediction - 6/13 One-bit prediction5/13 One-bit prediction 11/13 One-bit prediction-5/13 Predict NT-6/13 (e),J Predict NT = 6/13Explanation / Answer
The first method is a static branch prediction. The prediction doesn't change dynamically based on the history of branch condition. If the prediction is taken as not taken, it is the prediction considered throughout the branches execution.
In first method, branch prediction is: Predict NT,
Hence with the outcome of the each branch execution, the branch is taken 7 times in a total of 13. Only 6 times(i.e., in 3rd ,4th, 6th, 10th, 11th and13th iteration) the branch is not taken, which is the correct prediction. Therefore the correction prediction with Predict NT = 6/13
The second method One-bit prediction is a dynamic prediction method. The prediction changes based on the branch history. If the last branch is taken, then prediction changes to taken if the prediction is not taken. If the last branch is not taken, then prediction changes to not taken if the prediction is taken otherwise no change in the prediction.
In the given branch execution, with the prediction initialized to not taken:
The bolded letters denote the dynamic prediction changes based on branch history. For example, on 1st iteration, the prediction is NT(not taken) but actually it is taken. Hence there is a misprediction, therefore, the prediction is changed to T(taken) in the 2nd iteration.
If we see the total number of correct predictions in this method are at iterations 2,4,8,9 and 11. In total 5 correct predictions out of 13. Therefore in one-bit prediction = 5/13.
Prediction/Iteration 1 2 3 4 5 6 7 8 9 10 11 12 13 Actual condition T T NT NT T NT T T T NT NT T NT Branch Prediction NT T T NT NT T NT T T T NT NT T