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

Let number of instructions be n.

For non-pipelined, time taken will be equal to 30n

For pipelined, time taken will be equal to (4+n-1)*12 = 36 + 12n

When n tends to infinity, the ratio becomes 30/12, which is 2.5.

---

No data dependency in non-pipeline implementation as we will always have the result of previous instruction when we are fetching the operands of next instruction.

So no need of buffers for storing intermediate results. Moreover, we don't need to synchronise all the stages by setting equal delays. They can have different delays.

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

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