GATE CSE 2011 | Question: 41

Question

Consider an instruction pipeline with four stages $\text{(S1, S2, S3 and S4)}$ each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Delays for the stages and for the pipeline registers are as given in the figure.

What is the approximate speed up of the pipeline in steady state under ideal conditions when compared to the corresponding non-pipeline implementation?

• A. $4.0$
• B. $2.5$
• C. $1.1$
• D. $3.0$

Comments

why we are not taking register delay in non pipelined system :-
In non pipelined system,  new instruction is fed only when the previous instruction is fully executed. This means none of the stages are busy executing any instruction. Hence we do not need any interstage buffers in non pipelined system.

---

Pipeline =  max (5, 6, 11, 8)  +  1  = 12 ns
Non-pipe = 5+6+11+8 = 30 ns 
speed up =  30 / 12  =  2.5

---

Watch the Detailed Video Solution by clicking the button below..!

Watch Detailed Video Solution   

Answer 1

Answer is (B) 2.5

In pipeline system, Time taken is determined by the max delay at any stage i.e., $11$ $\text{ns}$ plus the delay incurred by pipeline stages i.e., $1$ $\text{ns}$ = $12$ $\text{ns}$. In non-pipeline system,

Delay = $5$ $\text{ns}$ $+$ $6$ $\text{ns}$ $+$ $11$ $\text{ns}$ $+$ $8$ $\text{ns}$ $=$ $30$ $\text{ns}$.

$\therefore$ $\text{The speedup is}$ $\frac{30}{12} = 2.5$ $\text{ns}$.

Comments

In a pipeline system, we must make the delay of all stages equal and in a non-pipeline system there is no need of using pipeline registers. So, 2.5 is the correct answer.

---

how is tp = 12 for one instruction, how could not it be 12*4 ?!

 

do it has to do with ideal conditions CPI = 1 ?

---

what is the meaning combinational circuit only?

sir what would be the answer when stages are synchronized?

---

Sir , i gt the correct answer . but wanted to make sure that ideal condition mean instrcution are coming right ? i mean there are many no of instruction not just a single instruction

if a single instruction need to be exuted then time taken in a non pipleined is less than time taken in pipeline (when stages are not balanced ) .am i correct @arjun sir ?

---

Not only that - no hazards. And yes, for a single instruction, pipeline makes no sense but that has no practical significance either.

---

@Arjun Sir

"steady state under ideal conditions"

means it is for synchronous pipeline?

---

Do the register delay are not taken into account for non pipelined system?

---

@Nit9 yes ideally every instruction need CPI=1 i.e why we write tp=12.

---

@nit9

CPI=1 and time needed  to complete one cycle (cycle time)both are different thing .

CPI (cycle per instruction) Ideal CPI =1 ,means to perform 1 stage ideally i instruction needs only 1 cycle .

When all stages are perfectly balanced then time taken by all stages in 1 cycle will be same . For ex: ID stage and WB stages both will  take same  cycle time if there is no stall cycle  and all stages have same delay, unlike this question .

here all stages are not perfectly balanced, different stages are taking different time delay for completion of 1 cycle .

---

What if the buffer delays were different? Would we add the highest one to the highest stage delay?

---

@saurabh, I think yes.we have to also consider the max buffer delay.

---

@ reena_kandari

Even if the buffer with the max delay is not placed in front of the pipeline stage with the max delay , would we add the highest stage delay to the highest buffer delay to get the net delay of the pipeline?

---

@Arjun sir

what is the CPI in case of non pipeline system??

---

@sushmita

that depends on what time period of clock used for non pipeline processor ..m i right ?

---

@Arjun sir 

kindly tell why we are not taking register delay in non pipelined system

 

---

@val_pro20

What i know - Data dependency problem doesn't occur in non-pipeline. Hence no need of buffers.

---

In a pipelined system interstage buffers are used to store intermediate output when the next stage is still busy performing some operation and is still not yet ready to process the next incoming data. In case of a non pipelined system, a new instruction is fed into the architecture only when the previous instruction is fully executed. This means none of the stages are busy executing any instruction. Hence we do not need any interstage buffers in non pipelined system.

Answer 2

A better way to solve would be

For non pipeline implementation, time to complete each instruction t = 5+6+11+8 = 30ns

For pipeline implementation, max duration for each stage T = 11+1 =12ns

For k instructions,

Total cycles for non-pipeline implementation = k*t

Total cycles for non-pipeline implementation = (k + n - 1)*T, where n = #stages

Consider 100 instructions

i) for non pipeline: C1 = 100 * 30 = 3000ns

ii) for pipeline: C2 = (100 + 4 -1)*12 = 103*12 = 1236ns

iii) Speedup = C1/C2 = 3000/1236 = 2.5 (approx)

Same holds true for 1000 instructions,

Hence answer is B

Comments

here for pipelining, k is the number of stages and n is the number of instructions. 1st instruction takes k cycles and rest n-1 takes 1 cycle. hence the formula is (k+n-1)*Tp. Please correct it in the answer. Your answer is correct but data setting isn't. It will confuse the reader.

It should be ii) for pipleine: C2 = (4 + 100-1)*12 = 103*12 =1236.

---

Your technique. Don't work if we have only 10 instructions

---

yes

Answer 3

Ans

Answer 4

So for this question we need to find speedup which is given as :

SPEEDUP = NON PL/PL (time for both)

Now, for NON PL we can simply add the time taken at each stage = 5 + 11 + 6 + 8 = 30 n (assuming n instructions)

Also, for PL, we must first find the CLOCK CYCLE TIME that is the max(stage + register delay) = 11 + 1 = 12 ns

Now, PL = 4 cycles or 1st instruction and n-1 cycles for remaining instructions assuming total is n

SPEEDUP = 30n/(4 + n-1)12 = 30/12 = 2.5 for large n