GATE CSE 2017 Set 1 | Question: 50

Question

Instruction execution in a processor is divided into $5$ stages, Instruction Fetch (IF), Instruction Decode (ID), Operand fetch (OF), Execute (EX), and Write Back (WB). These stages take 5, 4, 20, 10 and 3 nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of 2 ns. Two pipelined implementation of the processor are contemplated:

1. a naive pipeline implementation (NP) with $5$ stages and
2. an efficient pipeline (EP) where the OF stage is divided into stages $\text{OF1}$ and $\text{OF2}$ with execution times of 12 ns and 8 ns respectively.

The speedup (correct to two decimal places) achieved by EP over NP in executing $20$ independent instructions with no hazards is _________ .

Comments

$Pipeline-1:$ $(1\times 4\times 22)+20+19\times 1\times 22=108+418=526ns$

$Pipeline-2:$ $(1\times 5\times 14)+12+19\times 1\times 14=82+266=348ns$

$Speedup=\dfrac{526}{348}=1.51$

Official answer key $1.49-1.52$

Ref: Arjun sir answer

---

Pipeline−1:Pipeline−1: (1×5×22)+19×1×22

Pipeline−2:Pipeline−2: (1×6×14)+19×1×14

Speedup=P-1/P-2

   where i go wrong if first instruction take 5 stages and 19 can take 1. please help

---

it’s pipeline processor

Answer 1

Case 1:

Stages $5,$ max delay $= 22\text{ (after adding buffer delay), number of instructions}= 20$

Case 2:

Stages $6,$ (since OF is split), max delay $= 14,\text{ number of instructions}=20$

So, execution time is $(K+N-1)\times \text{ Max delay}$

Speed Up $=\dfrac{528}{350}=1.508 ($Execution time case $1/$Execution time case $2)$

So, the answer is 1.508

Comments

if u have written 1.50 also correct ans..bcz they mentioned Speedup (Correct to 2 decimal places)

---

Please, can anyone tell ?
Why we are not taking CPI=1 here ?
Because, A successful pipeline have CPI(Cycles Per Instruction)=1.

---

@Bikram Sir @Debashish @mcjoshi

What is meaning of " The speedup (correct to two decimal places) achieved by EP over NP "

Why is it EP/NP and not NP/EP? Plz tell me. I am doing wrong here.

Isnot speedup value less than 1?

Here speedup value greater than 1. So plz clarify my doubt here

---

" The speedup (correct to two decimal places) achieved by EP over NP "

means NP/ EP .

it means time taken without EP / Time taken with EP = speedup 

because speed up is defined as

=  average instruction  time taken without pipeline /  average instruction time taken with pipeline  

so that's why it is NP / EP and NOT EP/NP .

where , NP = Naive Pipeline, EP = Effective Pipeline .

---

Why hadn't we use here this formula

Execution time = (5+4+20+10+3)+4*2+(20-1)*(22)

---

Why are we considering total time here instead of average time??

@bikram sir  as you defined speed up as

Speed up= average time without pipeline/ average time with pipeline

Do we have to consider total time while comparing or calculating spped up of two pipelines always??

---

speedup is a number that measures the relative performance of two systems processing the same problem

---

why is it n-1 and not just n in the formula?

---

@Prashant Pandey 1, check only for 3 instruction with general pipeline approach. you will understand that why it is not n.

---

 the processor requires buffering between each pair of consecutive stages with a delay of 2 ns.

So for 5 stages, we will have 4 buffers and for 6 stages, we have 5 buffers. The final ratio should be 526/348 = 1.51. It doesn't change the answer by much though 

---

if we use same method for Ep;

$Execution time of ep(Tep) = (5+2+4+2+12+2)_{execution-of-one instruction-till-max-delay-segment} + ( 20-1)\times(12+2)_{time-for-executing-remaining-12ns-segments} + (8+2+10+2+3+2)_{time-to-execute-remaining-segments-in-lst-instruction}$

 

Tep = 318ns

 

Similarly Tnp = 5+4+20+10+3+2*4+(20-1)*(20+2) = 468ns

 

$speedup = \frac{468}{318} = 1.47$

---

Why are we NOT using the formula

Execution time = Time to execute 1^st instruction + (n-1) * max delay.

Execution time = (5+4+20+10+3+ 2+2+2+2)+4*2+(20-1)*(22)

 

The above equation seems the most appropriate to new in this scenario because no of instructions are limited, so we cannot round off the largest stall delay.

 

Any valid explanations?

---

Bikram sir, if we calculate each pipeline’s speed up using general formula : S=[n*tn]/[(k+(n-1))*tp] where tn=cycle time of non-pipeline and tp= cycle time of pipeline, k=stages, n= number of instructions. And then take the ratio as, S(N)/S(EP). I’m getting wrong answer using this method. (Getting correct answer by S(EP)/S(N) ) .

Please assist srestha ma’am, Rajesh Pradhan sir. Is this method wrong? 

---

Why can’t we use Tavg = Number of instructions x CPI x cycle time?

for me it’s coming :

Pipeline(NP) = 20 x 1 x 22 = 440 ns      &       Pipeline(EP) = 20 x 1 x 14 = 280 ns

So, speedup = 440/280 = 1.57.

Please let me know where I am doing wrong.

---

 ankit3009

for me it’s coming :

Pipeline(NP) = 20 x 1 x 22 = 440 ns      &       Pipeline(EP) = 20 x 1 x 14 = 280 ns

So, speedup = 440/280 = 1.57.

the mistake you did is,

tp here is one cycle time  and we have to calculate the time taken by all the cycles so why are you multiplying it with the number of instructions?

first ,we have to find the number of cycles in EP , which are (k+n-1) as here stages=5 (i.e k) and n=20, so the total cycles will be (5+20-1 =24)..then we will multiply it with one cycle time which is = 22ns  so that we will get the total time of EP.

similar with NP. 

---

Thank you @Pranavpurkar ! :)

I understood my mistake.

---

ankit3009

welcome bro!🙌

Answer 2

NP=5,4,20,10,3    ,latch=2  ,clock cycle time=20+2=22

EP=5,4,12,8,10,3 ,latch=2 ,clock cycle time=12+2=14

For 20 instructions

NP=(5+19)*22=528

EP=(6+19)*14=350

speedup=NP/EP=528/350=1.508

Comments

I rounded it off to 1.51. Will my answer be correct?

---

i have written 1.50 in exam.

i think they will have range from 1.50 to 1.51 like below gateoverflow key,so don't worry.

https://docs.google.com/spreadsheets/d/1Om8XPOkfV28706O3r0DQEevfJ6reCDC5Gn6XqnomfHU/edit#gid=0

Answer 3

Answer: 1.51

Case -1 Naive Pipeline

Since the cycle time is chosen as the largest stage time, so here the cycle time would be 20ns. 

We are given that there is an interstage delay of 2ns after each stage. So effectively each stage would take 22ns.  (Except the last stage of last instruction being executed)

So, let us choose the cycle time as 22ns

So, 20 instructions would take

[1st instruction x (20ns max stage time + 2ns stage delay) x total stages] +

[Rest 19 instructions x (20ns max stage + 2ns stage delay)] - 2ns (as last stage would not take buffering time)

[22 x 5] + [19 x 22 ] - 2

110 + 418 - 2

526

Case - 2 Efficient Pipeline

Here cycle time is chosen as the largest stage time (i.e of stage OF2), so here the cycle time would be 12ns. 

We are given that there is an interstage delay of 2ns after each stage. So effectively each stage would take 14ns.  (Except the last stage of last instruction being executed)

So, let us choose the cycle time as 22ns

So, 20 instructions would take

[1st instruction x (12ns max stage time + 2ns stage delay) x total stages] +

[Rest 19 instructions x (12ns max stage + 2ns stage delay)] - 2ns (as last stage would not take buffering time)

[14 x 6] + [19 x 14 ] - 2

84 + 266 - 2

348

Speedup is given by

Time taken without EP / Time taken with EP

526 / 348

1.51

Comments

why do u think 1/22 ns. is not correct?

---

Sorry.. I gave a thought on it.. It has to be 22ns. Delay of 2ns has to be added to 20ns. This is because each stage must complete in a single clock cycle. If I take as 20 ns, then after 20ns, other cycle will start and would only end after 20ns. So next stage would be able to start at 40th ns.

This is not desired and this is not intended. So, I was wrong. Thanks for pointing out

---

why are we considering naive pipeline answer in numerator of speedup formula?

Speedup= avg. Instruction execution time without pipeline/avg.instruction execution time with pipeline

naive pipeline has pipeline execution and we want without pipeline in numerator.??

Answer 4

For Naive pipelined CPU

K = 5, Tseg = max(5,4,20,10,3) + 2(delay) = 22 ns, n = 20.

Total time needed for 20 instructions

T_NP =(k+n-1) x Tseg = (5 + 20 –1) x 22 ns = 24 x 22 ns = 528 ns

For Efficient pipelined processor

K = 6,Tseg = max(5,4,12,2,10,3) + 2(delay) = 14 ns; k = 6, n = 20

Total time for 20 instructions

T_EP =(k+n-1) x Tseg = (6 + 20 – 1)  x 14 ns = 350 ns.

Speed up =528/350 =1.508