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

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 2

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)

Answer 3

Naive Pipeline implementation:
The stage delays are 5, 4, 20, 10 and 3. And buffer delay = 2ns
So clock cycle time = max of stage delays + buffer delay
= max(5, 4, 20, 10,3)+2
= 20+2
= 22ns
Execution time for n-instructions in a pipeline with k-stages = (k+n-1) clock cycles
= (k+n-1)* clock cycle time
In this case execution time for 20 instructions in the pipeline with 5-stages
= (5+20-1)*22ns
= 24*22
= 528ns
Efficient Pipeline implementation:
OF phase is split into two stages OF1, OF2 with execution times of 12ns, 8ns
New stage delays in this case = 5, 4, 12, 8, 10, 3
Buffer delay is the same 2ns.
So clock cycle time = max of stage delays + buffer delay
= max(5, 4, 12, 8, 10,3) + 2
= 12+2
= 14ns
Execution time = (k+n-1) clock cycles
= (k+n-1)* clock cycle time
In this case no. of pipeline stages, k = 6
No. of instructions = 20
Execution time = (6+20-1)*14 = 25*14 = 350ns
Speed up of Efficient pipeline over native pipeline
= Naive pipeline execution time / efficient pipeline execution time
= 528 / 350
≌ 1.51

Answer 4

We have 5 stages having delay 5 4 20 10 3  with buffer of 2 ns

so Exe time of P1= (5+19)*(20+2)=528

 

when we improve the processor we have six stages with day 5 4 12 8 10 3 with buffer of 2ns

so Exe time of P2=(6+19)*(12+2)=350

 

speedup=P1/P2=528/350 = 1.508