Assume that the breakdown of dynamic instructions into various instruction categ

Question

Assume that the breakdown of dynamic instructions into various instruction categorizes is as follows: R-typeBEQ 40% JMP 5% LW 25% SW 5% 25% Also, assume the following branch predictor accuracies Always-Taken Always-Not-Taken 2-bit 45% 55% 85% a) Stall cycles due to mispredicted branches e the CPI. What is the extra CPI due to mispredicted branches with the always-taken predictor? Assume that branch outcomes are determined in the EX stage that there are no data hazards, and that no delay slots are used b) Repeat part a) for the "always-not-taken" predictor. c) Repeat part a) for the 2-bit predictor. d) With the 2-bit predictor what speedup would be achieved if we could convert half of the branch instructions in a way that replaces a branch instruction with an ALU instruction? Assume that correctly and incorrectly predicted instructions have the same chance of being replaced. (Hint: speed up = CPI without conversion/ CPI with conversion) Some branch instructions are much more predictable than others. If we know that 80% of all executed branch instructions are easy-to-predict loop-back branches that are always predicted correctly, what is the accuracy of the 2-bit predictor on the remaining 20% of the branch instructions (Accuracy on non-loop-back branches)? e)

Explanation / Answer

Since the branch decision is made a the EX stage, each mis-prediction causes 2 clock cycles wasted duw to flush. Assuming original CPI = c.

a) With always-taken prediction, 1- 0.45 = 0.55 or 55%. of times a beq instruction will incur 3 additional cycles due to stall. The chances a beq instruction is executed is 25%, thus the additional CPI due to branch stall is 2 * 0.25 * (1 - 0.45) = 0.275 CPI.

b) With always-not taken predictor, 1 - 0.55 = 0.45 or 45% chances a mis-prediction will occur. Thus the extra CPI is 2 * 0.25 * (1 - 0.55) = 0.225 CPI.

c) With 2-bit predictor, the probabilty of mis-prediction is 1 - 0.85 = 0.15 or 15%.

Thus, the extra CPI is 2 * 0.25 * (1 - 0.85) = 0.075 CPI

d) Original CPI with 2-bit predictor is 1.075 i.e., 1 + 0.075

New CPI : Base CPI + (Mispredict * branches * cycles per mispredict)

1 + (1 - 0.85) * (0.5 * 0.25 * 2) = 1.0375

Speed up = 1.075 / 1.0375

= 1.0361 (approx.)

e)

To maintain an average of 85%.

85% = (percentage of easy-to-predict branches * prediction accuracy) + (percentage of other branches * prediction accuracy)

0.85 = (0.8 * 1 ) (0.2 * x)

x = 0.25 or 25% accuracy

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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