retagged by
1,753 views
3 votes
3 votes
Assume that 20 percent of the dynamic count of the instructions executed for a program are branch instructions. Assume further that 75 percent of branches are actually taken. The program is executed in two different processors that have the same clock rate. One uses static branch prediction with the assume-not-taken approach. The other uses dynamic branch prediction based on the states.

(a) With no pipeline stalls due to other causes, what must be the minimum prediction accuracy for the processor using dynamic branch prediction to perform at least as well as the processor using static branch prediction?

(b) If the dynamic prediction accuracy is actually 90 percent, what is the speedup relative to using static prediction?
retagged by

2 Answers

0 votes
0 votes

a) The number of non-branch instructions are more than the branch instruction. Hence, In static branching we will assume that branch will not be taken.

Accuracy of static branch prediction =  Percentage of non-branch instructions + Branch instructions not taken

= $\large 80 + \frac{25}{100}*20 = 85\%$

Hence, minimum prediction accuracy for the processor using dynamic branch prediction to perform at least as well as the processor using static branch prediction is $85\% .$

 

b) Dynamic prediction accuracy = $90\%$

$\large \delta_{branch\ penalty- static} = 0.2 * 0.75 = 0.15$

$\large \delta_{branch\ penalty- dynamic} = 0.2 * 0.5$ (90% of accuracy = 100% accurate on non branch instructions + 50% accuracy on branch instructions )

$\large S = 1 +  \delta_{branch\ penalty}$

$\large S_{static} = 1 +  0.15 = 1.15$

$\large S_{dynamic} = 1 +  0.01 = 1.01$

$ \large Speed \ up =$ $\large \left ( \frac{1.15}{1.01} - 1 \right ) * 100 = 13.86 \%$

 

edited by
0 votes
0 votes

a)  Static Prediction -- Not Taken

     Branch Taken = 75%

     So the Accuracy (Static Prediction)= 25%

     Hence, Accuracy (Dynamic Prediction) >=25%

b)  Static Prediction :-

               δbranch_static = (0.2) (0.75) (1) = 0.15

               Hence, Snew = 1 + 0.15 = 1.15

               Hence, $Tstatic = (1.15) * (N) / R$

     Dynamic Prediction :-

               δbranch_dynamic = (0.2) (0.10) (1) = 0.02              

              Hence, Snew = 1 + 0.02 = 1.02

             Hence, $Tdynamic = (1.02) * (N) / R$

 

  $SpeedUp = Tstatic / Tdynamic$

    SpeedUp = 1.127

Related questions

3 votes
3 votes
0 answers
1
PratikLatve asked Nov 6, 2016
694 views
In this Example of Branch folding I'm not getting how instruction I3 and I5 can Decode in same cycle i.e. cycle 6. and How instruction queue is helping Here to make Execu...