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

 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