GATE IT 2008 | Question: 40

Question

A non pipelined single cycle processor operating at $100\;\text{MHz}$ is converted into a synchro­nous pipelined processor with five stages requiring $2.5\;\text{nsec}, 1.5\;\text{nsec}, 2\;\text{nsec}, 1.5\;\text{nsec}$ and $2.5\;\text{nsec}$, respectively. The delay of the latches is $0.5\;\text{nsec}$. The speedup of the pipeline processor for a large number of instructions is:

• A. $4.5$
• B. $4.0$
• C. $3.33$
• D. $3.0$

Comments

Check this also u may get idea

---

It may help

https://youtu.be/UlOMwknlnf4

---

@Raghav Khajuria bro, you are slightly incorrect in your approach because you are adding times of different stages to find “the time of executing of one instruction in non-pipelined scenario” . But in question, it is cleared specified about time for one instruction, observe this phrase “non pipelined single cycle processor”, that’s why time of executing of one instruction in non-pipelined scenario = 1cycle, and to get in terms of nano-seconds, multiply this by “time period of clock”.

Note :- time period of clock can be find by doing reciprocal of frequency i.e T = (1/f)

Answer 1

Here we have to keep in mind the phrase: 

A non-pipelined single cycle processor

This signifies that instruction in a non pipelined scenario is incurring only a single cycle to execute entire instruction. Hence no concept of stage comes in case of single cycle non pipelined system.

The cycle time can be calculated from clock frequency given in non pipelined system $=100\text{ MHz}$

Therefore clock cycle time in non pipelined system $=\dfrac{1}{(100\times 10^6)} \text{s} =10 \text{ ns}$

Now cycle time in pipelined system $=\text{max(stage delay + interface delay)}$

$=2.5 + 0.5 =3\text{ ns}$

Therefore, 

Speedup $=\dfrac{\text{CPI}_{\text{non pipeline}}\times \text{Cycle time}_{\text{non pipeline}}}
{(\text{CPI}_{\text{pipeline}}\times \text{Cycle time}_{\text{pipeline}})}$

$=\dfrac{1\times 10}{(1\times 3)} =3.33$

 [Since in case of non pipeline we have single cycle processor, so $\text{CPI}_{\text{non pipeline}}=1 \text{ and } \text{CPI}_{\text{pipeline}}$ by default $=1$]

Hence, (C) is the correct answer.

Comments

then we can safely assume CPI = 1, for non-pipelined organization

---

@Habibkhan sir if last stage has max. delay then also we will add the buffer delay to stage delay or not?? 

---

Since it is mentioned in the question that the non pipelined processor is a single cycle processor, so time taken to execute one instruction is 1 clock cycle i.e 10ns;

But for a large no.of instructions is the catch here, and many of the users have calculated the speedup w.r.t one instruction in both pipeline and non-pipelined processor.

I just want to add a correction to that!

• Let us say total no.of instructions is equal to k.
• Since large no.of instructions is there, k approaches to infinity.
• Non pipeline execution time=k*10 ns.
• Pipeline execution time=(5+(k-1)) clock cycles=(4+k)*3ns=(12+3k)ns.

Thus speedup=10k/(12+3k)=10/((12+3k)/k)=10/(12/k+3)=10/(0+3)=10/3 (Ans.)

Note: when k tends to infinity,12/k becomes 0.

Answer 2

Answer is C.

explanation:

for non pipeline system time required $= 2.5 + 1.5 + 2.0 + 1.5 + 2.5 = 10$

for pipelined system $=\text{max(stage delay) + max(latch delay)} = 2.5 + 0.5 = 3$

speedup $=\dfrac{\text{time in non pipelie}}{\text{time in pipeline}}=\dfrac{10}{3}=3.33$

Comments

I agree with u @srestha ..Yes should I give corrected answer??

---

For non-pipelined 'single cycle' processor, we have 1/100 MHz as cycle time i.e. 10ns, which is same as sum of delays here. Coincidence?

I'm  also having this doubt..But it is holding true because we are given CPI = 1 for non pipeline..

we know for non pipeline processor time for 1 instruction = sum of all delays(X) ....so after X time one instruction gets out on non pipeline processor

If we set this time X as time period of clock for non-pipeline processor then CPI = 1.

This is the only way fot CPI = 1 in nonpipeline i,e sum of delays = Tclock

If they have given CPI for non pipeline >1 ==> More than on clocks for 1 instruction ==> Time X should be elapsed in more that one clocks hence Tclock < X(sum of all delays )

correct me if wrong

@Shaik Masthan sir

@Habibkhan sir

---

For coincidence https://gateoverflow.in/2143/gate2011-41

Answer 3

Answer C.

Synchronous pipeline - take longest time period

So in pipeline processor t= (3*5)+3*(n-1)

in non-pipeline - 2.5+1.5+2+1.5+2.5 = 10 ns

so speed-up = 10 n / t = 3.333

Answer 4

we know that speed up = Time taken by non pipeline / Time taken by Pipeline

=ntn/(k+n-1)*tp

where Tn is time  taken by task to complete in non pipleine sytem

and n is no of instructio

k = no of stages

Tp= max ( 2.5+3 . 1.5+.5,2+.5,1.5+.5,2.5+.5) = 3

Now they said that we need to exceute for large number of instrustion so assume n --> infinity

so term (k+n-1) boils down to n

So speed up now beacome ntn/ntp=10/3=3.33

Comments

This soln is wrong. Tp is not equal to 3 , tp = 3. And speed up = n*Tn /(k+n-1)*tp.

And if n is very large then the formula will drop down to Tn/tp. but here we dont need it or it will be not applied.

for Non pipelined processor the execution time will be n *Tn . But here in the question it is mentioned that “A non-pipelined single cycle processor” that means it will take 1 cycle for each instruction so execution time of Non pipelined processor = 10ns i.e. the time period of the non pipelined processor.

now speedup will be = 10/3 =3.3