We have a program core consisting of five conditional branches. This program cor

Question

We have a program core consisting of five conditional branches. This program core is part of a larger application program and will be executed thousands of times. Below are the outcomes of each branch for one execution of the program core (T for taken and N for not taken). Branch 1: T-T-T Branch 2: N-N-N-N Branch 3: T-N-T-N-T-N Branch 4: T-T-T-N-T Branch 5: T-T-N-T-T-N-T Assume the behavior of each branch remains the same for each execution of the program core. For dynamic branch prediction schemes, assume each branch has its own prediction buffer and each buffer is initialized to the same state before execution. List the prediction accuracies for the following branch prediction schemes: Always taken Always not taken 1-bit predictor, initialized to predict taken 2-bit predictor, initialized to weakly predict taken

Explanation / Answer

The Prediction accuracy is given by

Prediction accuracy = 100% * Correct Predictions / Total Branches

a)
   Branch 1: prediction: T-T-T, right = 3, wrong = 0
   Branch 2: prediction: T-T-T-T, right = 0, wrong = 4
   Branch 3: prediction: T-T-T-T-T-T, right = 3, wrong = 3
   Branch 4: prediction: T-T-T-T-T, right = 4, wrong = 1
   Branch 5: prediction: T-T-T-T-T-T-T, right = 5, wrong = 2
   Total right = 15, Total wrong = 10,
   Prediction Accuracy = 100% * 15/25 = 60%

b)
   Branch 1: prediction: N-N-N, right = 0, wrong = 3
   Branch 2: prediction: N-N-N-N, right = 4, wrong = 0
   Branch 3: prediction: N-N-N-N-N-N, right = 3, wrong = 3
   Branch 4: prediction: N-N-N-N-N, right = 1, wrong = 4
   Branch 5: prediction: N-N-N-N-N-N-N, right = 2, wrong = 5
   Total right = 10, Total wrong = 15,
   Prediction Accuracy = 100% * 10/25 = 40%

c)
   Branch 1: prediction: T-T-T, right = 3, wrong = 0
   Branch 2: prediction: T-N-N-N, right = 3, wrong = 1
   Branch 3: prediction: T-T-N-T-N-T, right = 1, wrong = 5
   Branch 4: prediction: T-T-T-T-N, right = 3, wrong = 2
   Branch 5: prediction: T-T-T-N-T-T-N, right = 3, wrong = 4
   Total right = 13, Total wrong = 12,
   Prediction Accuracy = 100% * 13/25 = 52%

d)
   Branch 1: prediction: T-T-T, right = 3, wrong = 0
   Branch 2: prediction: T-N-N-N, right = 3, wrong = 1
   Branch 3: prediction: T-T-T-T-T-T, right = 3, wrong = 3
   Branch 4: prediction: T-T-T-T-T, right = 4, wrong = 1
   Branch 5: prediction: T-T-T-T-T-T-T, right = 5, wrong = 2
   Total right = 18, Total wrong = 7,
   Prediction Accuracy = 100% * 18/25 = 72%
     

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.