Question

The importance of having a good branch predictor depends on how often conditional branches are executed. Together with branch predictor accuracy, this will determine how much time is spent stalling due to mispredicted branches. In this exercise, assume that the breakdown of dynamic instructions into various instruction categories is as follows:

R-Type	BEQ	JMP	LW	SW
40%	25%	5%	25%	5%

Also, assume the following branch predictor accuracies:

Always-Taken	Always-Not-Taken	2-Bit
45%	55%	85%

4.15.1 [10] Stall cycles due to mispredicted branches increase 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.

4.15.2 [10] Repeat 4.15.1 for the “always-not-taken” predictor.

4.15.3 [10] Repeat 4.15.1 for for the 2-bit predictor.

4.15.4 [10] 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. 4.17 Exercises 367 4.15.5 [10] With the 2-bit predictor, 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.

4.15.6 [10] 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?

Short answer

4.15.1

is 0.41 for the predictor of “always-taken”.

4.15.2

is 0.34 for the predictor of “always-not-taken”.

4.15.3

is 0.113 for the predictor of “2-bit”.

4.15.4

The speed up with the 2-bit predictor will be 1.054.

4.15.5

The speed up with the 2-bit predictor will be 0.94.

4.15.6

The accuracy will be 25%.

Step-by-step solution

Define the concept.

4.15.1

3 stall cycles are caused for each not correctly predicted branch that are predicted by the always-taken predictor.

TheBranch predictor “always-taken”has the accuracy of 45%.

4.15.2

3 stall cycles are caused for each not correctly predicted branch that are predicted by the “always-not-taken” predictor.

TheBranch predictor “always-not-taken”has the accuracy of 55%.

4.15.3

3 stall cycles are caused for each not correctly predicted branch that are predicted by the “2-bit” predictor.

TheBranch predictor “2-bit”has the accuracy of 85%.

4.15.4

CPI of Predicted branches in a correct way was 1.

Now, these are converted into ALU instruction, the CPI of these are also 1.

CPI of converted ALU instructions from the predicted instructions in the incorrect way was also 1.

$\mathrm{Speed}-\mathrm{up}=\frac{{\mathrm{CPI}}_{\mathrm{At}\mathrm{initial}\mathrm{stage}}}{{\mathrm{CPI}}_{\mathrm{After}\mathrm{theconversion}}}$

4.15.5

After converting the branch instruction, these instruction consumes some additional time for execution.

$\mathrm{Speed}-\mathrm{up}=\frac{{\mathrm{CPI}}_{\mathrm{At}\mathrm{initial}\mathrm{stage}}}{{\mathrm{CPI}}_{\mathrm{After}\mathrm{the}\mathrm{conversion}}}$

4.15.6

The accuracy will be on the non-loop back branches =$\frac{\left(\mathrm{B}\times 0.05\right)}{\left(\mathrm{B}\times 0.20\right)}$

Where,$\left(\mathrm{B}\times 0.85\right)$ is for the prediction in a correct way,

$\left(\mathrm{B}\times 0.05\right)$is for the predicted non-loop back in a correct way,

Easily the percentage of the predictable loop-back branches with respect to all executed branch instructions is 80%.

And the remaining branch instruction is 20%.

Determine the calculation.

4.15.1

Given that,

Instruction	The break-down
R-Type	40%
BEQ	25%
JMP	5%
LW	25%
SW	5%

Also given that,

Branch predictor	Accuracy
Always-Taken	45%
Always-Not-Taken	55%
2-Bit	85%

3 stall cycles are caused for each not correctly predicted branch that are predicted by the “always-taken” predictor.

$\begin{array}{rcl}\mathrm{The}\mathrm{additional}\mathrm{CPI}& =& \left(3\times \left(1-0.45\right)\times 0.25\right)\\ & =& \left(3\times 0.55\times 0.25\right)\\ & =& 0.4125\\ & =& 0.41\end{array}$

4.15.2

Given that,

Instruction	The break-down
R-Type	40%
BEQ	25%
JMP	5%
LW	25%
SW	5%

Also given that,

Branch predictor	Accuracy
Always-Taken	45%
Always-Not-Taken	55%
2-Bit	85%

3 stall cycles are caused for each not correctly predicted branch that are predicted by the “always-not-taken” predictor.

role="math" localid="1655195714378" $\begin{array}{rcl}\mathrm{The}\mathrm{additional}\mathrm{CPI}& =& \left(3\times \left(1-0.55\right)\times 0.25\right)\\ & =& \left(3\times 0.45\times 0.25\right)\\ & =& 0.3375\\ & =& 0.34\end{array}$

4.15.3

Given that,

Instruction	The break-down
R-Type	40%
BEQ	25%
JMP	5%
LW	25%
SW	5%

Also given that,

Branch predictor	Accuracy
Always-Taken	45%
Always-Not-Taken	55%
2-Bit	85%

3 stall cycles are caused for each not correctly predicted branch that are predicted by the “2-bit” predictor.

$\begin{array}{rcl}\mathrm{The}\mathrm{additional}\mathrm{CPI}& =& \left(3\times \left(1-0.85\right)\times 0.25\right)\\ & =& \left(3\times 0.15\times 0.25\right)\\ & =& 0.1125\\ & =& 0.113\end{array}$

4.15.4

Let’s consider whether the predicted instruction in a correct way or not has a no different chance of being interchanged.

If the half branch is replaced by the ALU instructions.

$\begin{array}{rcl}{\mathrm{CPI}}_{\mathrm{At}\mathrm{initial}\mathrm{stage}}& =& \left(1+\left(3\times \left(1-0.85\right)\times 0.25\right)\right)\\ & =& \left(1+\left(3\times 0.15\times 0.25\right)\right)\\ & =& \left(1+0.1125\right)\\ & =& 1.1125\\ & =& 1.113\\ & & \end{array}$

$\begin{array}{rcl}{\mathrm{CPI}}_{\mathrm{After}\mathrm{the}\mathrm{conversion}}& =& \left(1+\left(3\times \left(1-0.85\right)\times 0.25\times 0.5\right)\right)\\ & =& \left(1+\left(3\times 0.15\times 0.25\times 0.5\right)\right)\\ & =& \left(1+0.05625\right)\\ & =& 1.056\end{array}$

Then the speed up with the 2-bit predictor will be $\frac{1.113}{1.056}=1.054$

4.15.5

Let’s consider whether the predicted instruction in a correct way or not has a no different chance of being interchanged.

If the half branch is converted in such a way that each branch instruction is interchanged by the two ALU instructions.

$\begin{array}{rcl}{\mathrm{CPI}}_{\mathrm{At}\mathrm{initial}\mathrm{stage}}& =& \left(1+\left(3\times \left(1-0.85\right)\times 0.25\right)\right)\\ & =& \left(1+\left(3\times 0.15\times 0.25\right)\right)\\ & =& \left(1+0.1125\right)\\ & =& 1.1125\\ & =& 1.113\end{array}$

$\begin{array}{rcl}{\mathrm{CPI}}_{\mathrm{After}\mathrm{the}\mathrm{conversion}}& =& \left(1+\left(1+\left(3\times \left(1-0.85\right)\right)\right)\times 0.25\times 0.5\right)\\ & =& \left(1+\left(1+\left(3\times 0.15\right)\right)\times 0.25\times 0.5\right)\\ & =& \left(1+\left(1+0.45\right)\times 0.25\times 0.5\right)\\ & =& \left(1+0.18125\right)\\ & =& 1.181\end{array}$

Then the speed up with the 2-bit predictor = $\frac{1.113}{1.181}=0.94$

4.15.6

Given information: The percentage of the easily predictable loop-back branches with respect to all executed branch instructions is 80%.

For the prediction in a correct way,

$\left(B\times 0.85\right)$

For the predicted non-loop back in a correct way,

$\left(B\times 0.05\right)$

Hence, the accuracy will be on the non-loop back branches =

$\frac{\left(B\times 0.05\right)}{\left(B\times 0.20\right)}=0.25$

So, the percentage of the accuracy will be on the non-loop back branches 25%.