The Gateway to Computer Science Excellence

+28 votes

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:

- a naive pipeline implementation (NP) with 5 stages and
- an efficient pipeline (EP) where the OF stage is divided into stages OF1 and 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 _________ .

0

As the delay for different stages are different so the time for the first instruction for NP pipelined processor is

5+2+4+2+20+2+10+2+3=50

So time to execute 20 instructions will be

50+19*22=468

But here we are using the following formula

5+19*22=423

Why??

5+2+4+2+20+2+10+2+3=50

So time to execute 20 instructions will be

50+19*22=468

But here we are using the following formula

5+19*22=423

Why??

+3

$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

+31 votes

Best answer

**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, answer is** 1.508**

0

Please, can anyone tell ?

Why we are not taking CPI=1 here ?

Because, A successful pipeline have CPI(Cycles Per Instruction)=1.

Why we are not taking CPI=1 here ?

Because, A successful pipeline have CPI(Cycles Per Instruction)=1.

+2

@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

+11

" 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 .

0

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??

@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??

0

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

0

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

+18 votes

**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**

+2

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

+14 votes

**Answer: 1.51**

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

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

**Speedup** is given by

Time taken without EP / Time taken with EP

526 / 348

0

22ns isnot for easy calculation.

it is because cycle time of synchronous pipeline=the stage with max time + buffer time

it is because cycle time of synchronous pipeline=the stage with max time + buffer time

0

No. In reality 20ns will be cycle time and stage delay (buffer) would be 2ns.

Just in case the question has asked for Frequency, then I found have found not using 1 / 20ns = 50 Mhz

and not 1/22 = 45 Mhz

Right ?

Just in case the question has asked for Frequency, then I found have found not using 1 / 20ns = 50 Mhz

and not 1/22 = 45 Mhz

Right ?

0

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

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

+8 votes

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

+4 votes

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

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

–1 vote

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)

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)

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,271 answers

198,144 comments

104,788 users