retagged by
1,973 views
4 votes
4 votes

Assume that execution of 200 instructions on a 6 staged pipeline where the target address is available at 4th stage.Let X be the probability of an instruction not being branch. The value of X such that speedup is atleast 5 is?

retagged by

2 Answers

Best answer
10 votes
10 votes
  • Assume all stage balanced and assume equal clock speed both in pipelined and non-pipelined (no speeds given)
  • i.e. $T_{pipe} = T_{non-pipe}$
  • PC updated at the end of kth stage : $\Rightarrow$ stall cycles  = $k-1$

We need  $S \geq 5$

if no of instructions is very large :

$\begin{align*} &S = \frac{\text{One instruction execution time in non-pipeLine}}{\text{One instruction execution time in pipeLine}} \\ &S = \frac{6*T_{\text{non-pipe}}}{\text{Effective CPI}*T_{\text{pipe}}} \\ &S = \frac{6*T_{\text{non-pipe}}}{\left [ \text{default CPI+stall cycle per instn} \right ]*T_{\text{pipe}}} \\ &\text{default CPI} = 1 \\ &\text{and stall cycles per instruction} = \left ( \text{branch probability in one instruction} \right )*\left ( \text{stall cycles in one instruction} \right ) \\ &\text{and stall cycles per instruction} = \left ( 1-x \right )*\left ( 3 \right ) \\ &S = \frac{6*T_{\text{non-pipe}}}{\left [ \text{1}+\left ( 1-x \right )*3 \right ]*T_{\text{pipe}}} \\ &\Rightarrow \frac{6*T_{\text{non-pipe}}}{\left [ \text{1}+\left ( 1-x \right )*3 \right ]*T_{\text{pipe}}} \geq 5 \\ &\Rightarrow x \geq \frac{14}{15} \\ &\Rightarrow x \geq 0.933 \\ \end{align*}$

For limited small no of instructions :

$\begin{align*} &\text{S} = \frac{n*stage*T_{non-pipe}}{\left ( \text{stage}+n-1 \right )*T_{pipe} + \text{ Total stall cycles}*T_{pipe}}\\ &\Rightarrow \text{S} = \frac{200*6*T_{non-pipe}}{\left ( 6+200-1 \right )*T_{pipe} + \underbrace{200*(1-x)}*\underbrace{(4-1)}*T_{pipe}}\\ &\Rightarrow \text{S} = \frac{200*6}{\left ( 205 \right ) + 200*(1-x)*(3)} \\ &\text{Given S} \geq 5 \\ &\Rightarrow\frac{200*6}{\left ( 205 \right ) + 200*(1-x)*(3)} \geq 5\\ &\Rightarrow\frac{200*6 - 205*5}{200*3} \geq (1-x)\\ &\Rightarrow 0.058333 \geq (1-x)\\ &\Rightarrow x \geq 0.94167\\ \end{align*}$

edited by
3 votes
3 votes

Speedup = $\frac{Time_{without pipeline}}{Time_{pipeline}}$

For 200 instructions, Timewithout pipeline = Number of instructions * Number of stages * TCLK 

= 200 * 6 *TCLK

Timewith pipeline =  [(Number of non branch instructions * CPInon branch) + (Number of branch instrutions * CPIbranch )] * TCLK 

=  [x * 1 + (1 - x) * 4] * 200 *TCLK

$\because$ Next instruction address is know after 4th stage. So, stall cycles for each branch instruction is 3 and hence CPI for branch instructions is 4. CPI for non branch instruction is 1.

So, $\frac{200 * 6}{[x * 1 + (1 - x) * 4]*200}$ $\geqslant 5$

Solving, x = 0.93

edited by

Related questions

0 votes
0 votes
0 answers
1
rishabhdevsingh1 asked Nov 10, 2018
690 views
consider a5 stage pipeline processor, 20% load instructions, 25% branches, 20% stores, 20% of all instructions are data dependent on instructions in front of them and bra...
0 votes
0 votes
1 answer
2
Na462 asked Sep 3, 2018
856 views
Its a snapshot from hamacher.According to me there should be stall of 2 cycles why 3 ??Because after Write stage the data will be available in register file so why extra ...
0 votes
0 votes
1 answer
4
Jaggi asked Jul 7, 2018
953 views
A computer with a 5 stage pipeline deals with conditional branches by stalling for the next 3 cycle after hitting one. how much does stalling hurt the performance is 20% ...