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

Simple Solution :-
Given Non-pipeline clock frequency = 100MHz ,
cycle time = 1 / clock frequency = 1/10MHz = 10 nsec
So tn = 10nsec

for Pipelines prcoess = cycle time = Max (  stages delay ) + latch delay time = 2.5 + 5 = 3nsec

Speedup = slower./faster = non-pipeline / pipeline = n * tn / ( k + n-1) tp

for large value of n :- (k+ n-1 ) = n

so Speedup  = n * tn / n * tp = tn/tp = 10 / 3 = 3.33

---

Remember to convert freq to clock time in proper units (in powers of 10) rest all just like usual

---

Need to watch for the conversation of rate to nsec

Also here since n is very large the speedup will be ideal (n>>k) because we ignore k-1 from the formula 

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

Answer 5

https://www.youtube.com/watch?v=UlOMwknlnf4

Answer 6

Ans