GATE CSE 2020 | Question: 43

Question

Consider a non-pipelined processor operating at $2.5$ GHz. It takes $5$ clock cycles to complete an instruction. You are going to make a $5$- stage pipeline out of this processor. Overheads associated with pipelining force you to operate the pipelined processor at $2$ GHz. In a given program, assume that $30\%$ are memory instructions, $60 \%$ are ALU instructions and the rest are branch instructions. $5 \%$ of the memory instructions cause stalls of $50$ clock cycles each due to cache misses and $50 \%$ of the branch instructions cause stalls of $2$ cycles each. Assume that there are no stalls associated with the execution of ALU instructions. For this program, the speedup achieved by the pipelined processor over the non-pipelined processor (round off to $2$ decimal places) is_____________.

Comments

Ans

---

bro in non pipeline why u not add base cpi 1 ??

---

Because in non-pipeline, we already know each instruction will take five cycles,

Answer 1

Time taken by non-pipelined processor to finish executing the $n$ instructions $: \frac{5n}{2.5}=2n\;\text{ns}$

Now, for pipelined processor,

$\small \begin{array}{|c|c |c| c|} \hline  \text{Instruction type} & \text{Number of such instructions} & \% \text{Causing stalls} & \text{Number of stall cycles} \\\hline  \text{Memory}  & 0.3n & 5\% \;\text{of}\; 0.3n & 50  \\\hline \text{ALU}  & 0.6n & \text{None} & 0    \\\hline  \text{Branch} & 0.1n & 50\% \;\text{of}\;0.1n & 2 \\\hline \end{array}$

Therefore, time taken by pipelined processor:

$0.6n(1) + 0.3n[0.05(1+50) + 0.95(1)] + 0.1n[0.5(1+2) + 0.5(1)]$ cycles

$= 1.85n$ cycles

$= \frac{1.85n}{2}\;\text{ns}$

$= 0.925n\;\text{ns}$

Speedup $= \frac{2n}{0.925n} = 2.162 \approx 2.16.$

Comments

Why haven't we considered the stalls in non pipelined cpu , due to cache misses ? Should it not be there irrespective of pipelining?

---

Stalls mean the condition in which the actual pipeliened execution is not executed. Stall only comes in case with pipelined processor. non-pipeline mei we execute instruction one by one and each takes 2ns

---

Even for pipeline i took CPIideal = 5 instead of 1 thinking each stage will need 5 cycles for a instruction

Answer 2

Non-pipelined processor operates at 2.5GHz ==> T$_{Non-pipelined}=\frac{1}{2.5GHz}= 0.4 ns $

CPI of Non-pipelined processor = 5 clocks.

 

pipelined processor operates at 2GHz ==> T$_{Pipelined}=\frac{1}{2GHz}= 0.5 ns $

Memory instructions = 30 %

in those memory instructions 5 %, each creating stalls of 50 cycles

 

ALU instructions = 60%, these are creating no stalls

 

Branch instructions = 10%

in those branch instructions 50 %, each creating stalls of 2 cycles.

 

CPI of Pipelined processor = 1 + extra cycles. = 1 + stalls by memory instructions + stalls by Branch instructions.

= $1 + (\frac{30}{100}*\frac{5}{100}*50) + (\frac{10}{100}*\frac{50}{100}*2)$ = 1.85

 

Execution time = no.of instructions * No.of clock cycles * clock time = CPI * clock time.

Speed up achieved = $\frac{5*0.4}{1.85*0.5}$ = 2.16

Comments

This is the approach I was looking for. Thank you sir.:)

---

GopiChand

CPI(cycles per instruction) = (K+n-1)/n   (where K=stages , n= total number of instructions ) .Now , if there are some stall cycles due to memory or any other instructions then we have to add those extra cycles also   CPI= [(K+n-1)+x]/n  and considering n>>>>K  we will get  CPI=(n+x)/n and by simplifying further you will get  CPI=1+x/n (where x/n  refers to the number of instructions which are causing the stall cycles out of n instructions) so we can write it as f*c ( f=frequency of instructions and c=stall cycles caused by them). that's how the +1 came into the picture.

hope it helps:)

---

a silly mistake would be dividing 5/1.85

because frequency is different so clock cycle time will be different,

so we need to compute execution time separately then find the speed up.

 

Answer 3

Speedup = $\frac{\frac{5}{2.5*{10^{9}}}}{\frac{1 \space \space + \space \space 0.3*0.05*50 \space  \space + \space \space 0.1*0.5*2}{2*{10^{9}}}}$

which is 2.16

Comments

Very detailed explanation.

---

thanks a lot bro.

---

yo?? 😭

Answer 4

Just wanted to share the visualization of the types if instruction to calculate avg cycles:

Answer 5

Ans

Comments

INTRESTING