0
\$\begingroup\$

I was solving below exercise problem from book Computer Architecture and Design by Patterson at al. This could be more mathematical / logical doubt than electronics related doubt.

Breakdown of dynamic instructions into various instruction categories: enter image description here
2 bit branch predictor accuracy is 85%.
What speedup would be achieved if we could convert half of the branch instructions in a way that replaced each branch instruction with two ALU instructions? Assume that correctly and incorrectly predicted instructions have the same chance of being replaced.

The solution given was:

Each branch that is not correctly predicted will cause 3 stall cycles.
CPI of non branch instructions: 1
CPI of correctly predicted branch instructions: 1
CPI of ALU instructions: 1
% of branch instructions: 25%
% of reduced branch instructions (after half of them getting converted to ALU): 25% * 50%
% incorrectly predicted branch instructions: 100-85% = 15%
Total stall cycles added due to misprediction: 3×.15×.25×.5
Extra ALU is added for replaced branch instructions. % of extra ALU = 25%*(100-50)% = 25% * 50%
CPI for extra ALU: 1* 25% * 50% =1×.25×.5
Total CPI = 1 + (3×.15×.25×.5) + (1×.25×.5) =1.181

I solved it as follows:

If we ignore % and interpret the % values as absolute count, then revised branch instruction will be 12.5. We remove 12.5 branch instructions add 25 ALU instructions making total instructions = 112.5. This will make total branch instructions = 12.5 / 112.5 = 11.11 % So CPI = 1 + (3 * 0.15 * 0.11) = 1.05

Though I can appreciate book's approach, I am still not getting where exactly I went wrong "logically". What is exact logical / mathematical mistake in my approach?

\$\endgroup\$
  • \$\begingroup\$ You start with 100 instructions and replace 12.5 of them with 25 ALU instructions. This makes 112.5 instructions. In addition, there are still the remaining 12.5 branch instructions with a 15% chance of misprediction. So the total execution time is \$112.5 + 3\times 15\%\times \frac12\times 25=118.125\$. \$\endgroup\$ – jonk Apr 21 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.