Pipeline

Question

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?

Comments

https://gateoverflow.in/35999/calculating-branch-frequency-when-speedup-is-given

---

The explanation is not clear
Need more explanation Please!

---

Speed Up= Number of stages/(1+ percentage of branch cycles*(Branch Penalty))

5=6/(1+(1-x)*(3))

Solve it yoursef.

200 will not be used.

---

@Lucky sunda  that can not be accepted as answer. I have made it as comment. 

Answer 1

• 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*}$

Comments

"target address is available at 4th stage" This means we can do Instruction Fetch at 4th stage and hence stall sycles should be 2

Answer 2

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

For 200 instructions, Time_{without pipeline} = Number of instructions * Number of stages * T_CLK 

= 200 * 6 *T_CLK

Time_{with pipeline} =  [(Number of non branch instructions * CPI_{non branch}) + (Number of branch instrutions * CPI_branch )] * T_CLK 

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

$\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

Comments

your answer will be correct only for n is very large, although you have written 200 in the expression.it plays no role there.

---

stall states should be 3 I think

---

@Debashish saw your answer. How did you derive the formula for limited small instructions?

---

Yes stall = cpi-1