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

Ans

---

Inthe question say speed up achieve by Ep over Np so why it is not like-- Ep_time/ Np_time

---

Speed up= 1/time(EP) / 1/time(NP)

               =NP/EP

 

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

Thank you @Pranavpurkar ! :)

I understood my mistake.

---

ankit3009

welcome bro!🙌

---

I think , we should not consider the pipeline delay of the last instruction , the delay is only between stages , so

it is not 528/350 , it is 526/348

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

Answer 5

Naive pipeline Implementation:

IF                      ID                     OF                     EX                 WB                    

5ns                  4ns                20ns                  10ns             3ns

delay = 2 ns

Phase time =largest stage delay + delay = 20 + 2  =22 ns

Time to Execute N instructions in pipelined  processor = k * phase time + (N-1)  * phase time                      k=number of stages

                                                                                                 = 5 * 22  + 19 * 22

                                                                                                 = 528 ns

Similarly, Efficient pipeline Implementation:

IF                      ID                     OF1               OF2                     EX                 WB                    

5ns                  4ns                      12ns             8ns                     10ns                3ns

delay = 2 ns

Phase time =largest stage delay + delay = 12 + 2  =14 ns

Time to Execute N instructions in pipelined  processor = k * phase time + (N-1)  * phase time                      k=number of stages

                                                                                = 6 *14   +  19 * 14

                                                                                 = 350 ns

The speedup (correct to two decimal places) achieved by EP over NP =  528 /350 = 1.50

Answer 6

The exact answer is 528/350 = 1.50

In GATE 2017 official answer key, answer is given in range 1.49 to 1.52.

Refer https://drive.google.com/file/d/0ByPcpxjSfRuVM0hkT25GUFpnaHc/view
 Question no. 50(cs set 1)