GATE CSE 2015 Set 1 | Question: 38

Question

Consider a non-pipelined processor with a clock rate of $2.5$ gigahertz and average cycles per instruction of four. The same processor is upgraded to a pipelined processor with five stages; but due to the internal pipeline delay, the clock speed is reduced to $2$ gigahertz. Assume that there are no stalls in the pipeline. The speedup achieved in this pipelined processor is_______________.

Comments

Speedup = ExecutionTime

_Old / ExecutionTime_New ExecutionTime_Old = CPI_Old * CycleTime_Old [Here CPI is Cycles Per Instruction] = CPI_Old * CycleTime_Old = 4 * 1/2.5 Nanoseconds = 1.6 ns Since there are no stalls, CPU_new can be assumed 1 on average. ExecutionTime_New = CPI_new * CycleTime_new = 1 * 1/2 = 0.5 Speedup = 1.6 / 0.5 = 3.2

---

In non-pipelined processor for each 1.6ns one instruction will be processed.
In the equivalent pipelined processor, when pipeline is full, for each .5ns one instruction will be processed.

Speedup of pipeline processing over non-pipeline processing = $1.6/.5 = 3.2$

Pipeline processing is $3.2$ time faster than non-pipelining processing.

---

$\underline{\textbf{Answer:}\Rightarrow}$

$\underline{\textbf{Explanation:}\Rightarrow}$

$\color{blue}{\underline{\textbf{For Non-Pipelined System:}\Rightarrow}}$

Given frequency $\mathbf{ = 2.5 GHz}$

$\therefore 1\; \text{Cycle time} = \mathbf{\dfrac{1}{2.5Gs} }= \dfrac{1}{2.5}\;\text{nano seconds}$

$\therefore \text{Total Time}  = 4\times \frac{1}{2.5} \text{nano seconds} =\dfrac{4}{2.5}\;\text{nano seconds}$

$\color{blue}{\underline{\textbf{For Pipelined System:}\Rightarrow}}$

 $\textbf{Average CPI} = 1\;\;[\because \text{It is given that pipeline has no stalls.}]$

This also proves the fact that pipeline is also $\color{magenta}{\text{independent of the number of phases}}$, [so there would be $\color{red}{\text{no change}}$ if the question was asked for $\mathbf 6$ stages also.]

Similarly, as above:

$\mathbf{Frequency = 2\;GHz}$

$\therefore\;1\text{ cycle time} =\dfrac{1}{2} \;\text{nano seconds}$

$\therefore \textbf{Speed-up} = \dfrac{\text{Time without pipelining}}{\text{Time with pipelining}} = \dfrac{\dfrac{4}{2.5}}{\dfrac{1}{2}} = 3.2$

$\therefore\;3.2$ is the correct answer.

Answer 1

Answer = 3.2.

To compute cycle time, we know that a $2.5\;\textsf{GHz}$ processor means it completes $2.5\;\text{billion}$ cycles in a second. So, for an instruction which on an average takes $4$ cycles to get completed, it will take $\dfrac{4}{2.5}\ $ nanoseconds. 

On a perfect pipleline (i.e., one which has no stalls) $\text{CPI} = 1$ as during it an instruction takes just one cycle time to get completed.

So,

Speed Up $=\dfrac{\text{Old Execution Time of an Instruction}}{\text{New Execution Time of an Instruction}}$

$=\dfrac{\text{CPI}_{\text{old}}/\text{CF}_{\text{old}}}{\text{CPI}_{\text{new}}/\text{CF}_{\text{new}}}$

$=\dfrac{4/2.5\;\textsf{GHz}}{1/2\;\textsf{GHz}}$

$=3.2$

Comments

@amarVashishth So, even if we use 4 or 6 stage pipeline answer is same?

---

that will depend on what the question says. 
Here by introducing a 5 stage pipelining, though successful, the processor speed is reduced to 2GHz.

---

clock speed is reduced to handle buffer delays. Also how can you say in 1 clock cycle an instruction gets completed with pipeline? It should be the max clock cycle(s) needed for any stage.

---

Yes, you are right.

It has been encountered many times that whenever they suggest something like a pipelined-processor with no stalls we assume that we are talking about a Scalar processor.

check : https://en.wikipedia.org/wiki/Cycles_per_instruction#Explanation

---

yes, but I don't consider that a safe assumption. Moreover I very much doubt if the same question repeats answer will be 3.2..

---

Sir, but I also have a second thought on this.

Consider a pipelined-processor where CPI = 3, say EX stage takes 3 cycles and all other takes up just one.
the second instruction that enters the pipeline stalls at stage just behind the EX stage, it means there were stall cycles for that instruction.

But here, we are given that there are No stall cycles. Hence, we can say that the instruction flow from present stage to the next on each clock cycle. Hence, CPI has to be 1.

---

I think I got the issue- the execution time of an instruction with pipeline cannot go below a clock cycle (as we can not assume super scalar). This will give answer as 3.2 and that should be the reason. With a 3 stage pipeline, the same approach won't work here.

---

Sir, How is a stall cycle not possible when $CPI>1$?

---

Suppose each stage takes 2 clock cycles, there won't be any stall.

---

Pipeline stall is a delay in execution of an instruction. The instruction waiting just outside the pipeline will experience stall cycles.

---

every stage is taking same cycles- so there will be no delay..

---

for GATE syllabus we cover Classic RISC pipeline only, In which if it's a successful pipeline we have CPI = 1. Which is an objective of this pipeline.

 

"If every cycle takes up same number of cycles then there will be no delay" does this imply that there are no Stall Cycles?
If yes, then stalls do happen even when stages are always busy, this can be understood by taking example of a branch instruction.

---

yes for ideal piepline CPI is considered as 1

---

@arjun sir,what is meant by the ideal case that CPI =1?

does it mean that clock cycle to execute one instruction =1 or clock cycle for every stage =1?

and if it means that 1 clock cycle to execute an instruction then how is it possible that a single intruction needs only 1 clock cycle because there are many stages in between which are having their cycles

---

how can you say that there are no stalls when stages have equal cycles?

lets suppose 2cycles for each IF,ID,EX,WB

then

IF IF ID ID EX EX WB WB

-  -    IF IF  ID  ID   EX  EX WB WB

        -   -   IF   IF   EX  EX  WB  WB

CONSIDER ABOVE EXAMPLE,I AM FACING TWO CYCLE STALLS PER INSTRUCTION HERE...

---

@arjun Sir, So we need not worry about $\text{one stage time} > \text{new cycle time}$  situation?

---

yes we only consider CPI > or =1

---

@Akriti

CPI means Cycle Per Instruction. It is defined as no of cycle that is required to execute one instruction. It has nothing to do with the clock cycle of stage. 

In pipeline CPI=1 means that every 1 cycle one instruction is getting out of the pipeline.Though it seems that each instruction is getting out of pipeline after 1 cycle, it does not means stages of pipeline has done the computation in 1 cycle ..they all took 1 cycle each.. However due to being overlapped with other instruction, it appears that each instruction are taking 1 cycle (but actually each instruction took (k stage)*(1 cycle) )

Q. how can you say that there are no stalls when stages have equal cycles?

Stalls in pipeline occurs due to hazards  only. 

Stages of pipeline can take different cycles but to solve the problem we assume in pipeline , Cycle'=max(cycle 1, cycle 2 ...cycle k) where cycle k=cycle need for stage k.

If you use take cycle 1=cycle 2 =.... =cycle k (case where each stages take equal cycles)

then Cycle'=cycle1. Now you can see there wont be any stalls until any hazards occurs.

What i mean is , stall means waiting . So we stall only when we have a work to do but since the data is not available or resource is not available or next instruction to excute is not clear, we cant proceed. Hence we have to wait a bit i.e. stall for cycle till we get our requirement fullfilled .

---

CPI_pipelined = Ideal CPI + Pipeline stall clock cycles per instruction

= 1 + Pipeline stall clock cycles per instruction(it is given to be 0)

=1+0

=1

Source:-

http://web.cs.iastate.edu/~prabhu/Tutorial/PIPELINE/hazards.html

---

@srestha

CPI > or <?? What it should be?

---

where u got less than?

---

Oh, actually I remember now, that was in the case of superscalar.

For gate we don't have that.

---

@naresh1845 @Arjun Sir @amarVashishth

How an instruction can take $\frac{4}{2.5} Gs$

Didn't get this

---

What is CF here?

@naresh1845

---

@Arjun Sir.

There is definitely a mistake in this best answer, perhaps the typo maybe.

It should be:

On an average takes 4 cycles to get completed will take $\frac{4}{2.5} \;\bf{nano}\; seconds$

---

Is it fine now?

---

Yes sir its perfect now.

Thanks for making corrections.

---

$\color{blue}{\underline{\textbf{For Non-Pipelined System:}\Rightarrow}}$

Given frequency $\mathbf{ = 2.5 GHz}$

$\therefore 1\; \text{Cycle time} = \mathbf{\dfrac{1}{2.5Gs} }= \dfrac{1}{2.5}\;\text{nano seconds}$

$\therefore \text{Total Time}  = 4\times \frac{1}{2.5} \text{nano seconds} =\dfrac{4}{2.5}\;\text{nano seconds}$

$\color{blue}{\underline{\textbf{For Pipelined System:}\Rightarrow}}$

 $\textbf{Average CPI} = 1\;\;[\because \text{It is given that pipeline has no stalls.}]$

This also proves the fact that pipeline is also $\color{magenta}{\text{independent of the number of phases}}$, [so there would be $\color{red}{\text{no change}}$ if the question was asked for $\mathbf 6$ stages also.]

Similarly, as above:

$\mathbf{Frequency = 2\;GHz}$

$\therefore\;1\text{ cycle time} =\dfrac{1}{2} \;\text{nano seconds}$

$\therefore \textbf{Speed-up} = \dfrac{\text{Time without pipelining}}{\text{Time with pipelining}} = \dfrac{\dfrac{4}{2.5}}{\dfrac{1}{2}} = 3.2$

---

Yes its correct.

---

Thanks

---

@Arjun Sir, Do we need to take CPI=1 every time even if it is not given in the question?

If we were given 100 instructions

Without pipeline it would take = (4 x 100) clocks

With pipeline it would take  = (5 + 99 ) clocks 

So if we calculate it this way

Speed up =    Time without pipeline     =     (4 x 100) x (1 / 2.5)      

                       Time with pipeline                  (5 + 99) x ( 1/ 2)

 Speed Up = 3.0769

So if in NAT we write this value will it be considered correct or not? 

Because it is not given we should consider CPI =1 anywhere !

Please do reply, if anyone!

 

---

I have the same doubt here.

---

why we have not multiplied the cycle time of pipelined processor by 5...since it will 5 cycles to complete it’s first task ?

---

@jiminpark

the entire objective behind using pipeline is that when we n = number of instructions are huge we approximately get cpi =1, i.e one instruction completing at the end of each cycle. So while competing speedup its safe to assume n is large if not mentioned otherwise. 

Answer 2

Speed up $=\dfrac{\text{Old execution time}}{\text{New execution time}}$

Old execution time $=\dfrac{\text{CPI}}{2.5} =\dfrac{4}{2.5}=1.6\text{ ns}$

With pipelining,

$=\dfrac{\text{each instruction needs old execution time} \times \text{old frequency}}{\text{new frequency (without pipelining)}}$

$=\dfrac{1.6\times 2.5}{ 2}=2\text{ ns}$

There are $5$ stages and when there is no pipeline stall, this can give a speed up of up to $5$
(happens when all stages take same number of cycles).
In our case this time will be $\dfrac{2}{5}= 0.4\text{ ns}$.
But clock frequency being $2\text{ GHz},$ clock cycle is $\dfrac{1}{2}\text{ GHz}=0.5\text{ ns}$
and a pipeline stage cannot be faster than this.

So, average instruction execution time after pipelining $\text{= max (0.4, 0.5) = 0.5 ns}$.

So, speed up compared to non-pipelined version $=\dfrac{1.6}{0.5}= 3.2$

Comments

@arjun,

With pipelining, each instruction needs old execution time * old frequency/new frequency (without pipelining) = 1.6 * 2.5 / 2 = 2 ns

can you explain this statement? i did not understand the calculation part. 

i know execution time=(CPI/clock rate). But how you are calculating the new execution time here? Please explain?

---

Let initial processor with 2.5Ghz is P1 and new processor with 2Ghz is P2. 

Old execution time = CPI/2.5 = 4/2.5 = 1.6 ns

This is the usual equation, you all know about it.

With pipelining, each instruction needs old execution time * old frequency/new frequency (without pipelining) = 1.6 * 2.5 / 2 = 2 ns
 

P1 is upgraded to P2 but still non-pipelined, so the above equation into play again as
Execution Time=old CPI/New Frequency which is 4/2=2ns.

(sir has done that putting old values as ((4/2.5)*2.5)/2=2ns).

{Section-1}
P2 becomes pipelined and we know when we upgrade our processor from non-pipelined to pipelined we achieve a speedup of "number of stages" we have in the pipeline, i.e. 5, over non-pipelined P2.

There are 5 stages and when there is no pipeline stall, this can give a speed up of up to 5 (happens when all stages take same number of cycles). In our case this time will be 2/5 = 0.4 ns. But clock frequency being 2 GHz, clock cycle is 1/2 GHz = 0.5 ns and a pipeline stage cannot be faster than this. 

So, what will be the new execution time?
It will be obtained by the formula of speed up,
 i.e. Speed up =Old time/new time 
So, New time=Speed Up/Old time
                    =2/5=0.4 nsec.


{Section-1 Ends}

What happened in section-1 is we calculated pipelined processor P2 cycle time from its non-pipelined format.

Now, we calculate Cycle time of pipelined processor P2 like we usually do, In ideal pipeline, CPI is 1, and given clock rate is 2Ghz.
Execution time = CPI/clock rate
                       =1/2=0.5 nsec

Why there is a difference in the two execution time of the same processor when pipelined. I don't know exactly, may be arjun sir clarify this point. But I can say that the method we are using in section-1 is considering CPI=4 for non-pipeline of P2 as this CPI of old P1, it might happen P1 would have less number of stages than P2, which change the non-pipelined CPI of P2.

If above statement is confusing we can also look at this our new processor P2 has 5 stages if each stage takes 1-cycle time so our new CPI will be 5 which is greater than P1.
As CPI increase in equation Execution time=CPI/clock rate the time execution time increased. remember we still talking about the non-pipelined processor.

but as soon the processor become pipeline its Ideal CPI becomes 1 as at every clock cycle it produces one output. So we can calculate P2 another way which gave an answer as 0.5 nsec.    

So, average instruction execution time after pipelining = max (0.4, 0.5) = 0.5 ns. 

Everything is working in sequence like P1 non-pipe -> becomes P2 Non-pipe -> from which we calculate P2 pipe execution time -> then we calculate P2 pipe execution time again with default method-> compare both of these -> Max is chosen(don't know why?).

SpeedUp= Non-pipelined of P1/Pipelined of P2
             =1.6/0.5
             =3.2

---

@bhuv I had already given the reason for it -- a pipeline stage cannot run faster than a clock cycle.

Answer 3

Non Pipeline: Given $2.5$ GHz, CPI=$4$

$1$ sec ---> $2.5 * 10^{9} $cycles

$1$ cycle  --->$ \frac{10}{25}$ ns

$1$ inst ---> $4$ clock cycle -->$ 4* \frac{10}{25} = \frac{8}{5}$ns

Pipeline: Given $2$ GHz, CPI= $1$

$1$ sec ---> $2* 10^{9} $ cycles

$1$ cycle  ---> $\frac{1}{2}$ ns

$1$ inst ---> $1$clock cycle -->$\frac{1}{2}$ns

Speedup = $\frac{Time\ in\ Non\ pipeline}{Time\ in\ Pipeline}$

Speedup=$ \frac{8}{5} * 2 = 3.2$

Comments

this is under ideal condition? else with pipeline time would be Time for First inst + time for n-1 inst

i.e 4*0.5+0.5=2.5 but under ideal condition 0.5*1=0.5

am i correct?

---

@Abhisek Tiwari 4

I think in given question they mentioned $"No$  $Stalls",$So we take ideal condition. 

Answer 4

$\underline{\textbf{Answer:}\Rightarrow 3.2}$

$\underline{\textbf{Explanation:}\Rightarrow}$

$\color{blue}{\underline{\textbf{For Non-Pipelined System:}\Rightarrow}}$

Given frequency $\mathbf{ = 2.5 GHz}$

$\therefore 1\; \text{Cycle time} = \mathbf{\dfrac{1}{2.5Gs} }= \dfrac{1}{2.5}\;\text{nano seconds}$

$\therefore \text{Total Time}  = 4\times \frac{1}{2.5} \text{nano seconds} =\dfrac{4}{2.5}\;\text{nano seconds}$

$\color{blue}{\underline{\textbf{For Pipelined System:}\Rightarrow}}$

 $\textbf{Average CPI} = 1\;\;[\because \text{It is given that pipeline has no stalls.}]$

This also proves the fact that pipeline is also $\color{magenta}{\text{independent of the number of phases}}$, [so there would be $\color{red}{\text{no change}}$ if the question was asked for $\mathbf 6$ stages also.]

Similarly, as above:

$\mathbf{Frequency = 2\;GHz}$

$\therefore\;1\text{ cycle time} =\dfrac{1}{2} \;\text{nano seconds}$

$\therefore \textbf{Speed-up} = \dfrac{\text{Time without pipelining}}{\text{Time with pipelining}} = \dfrac{\dfrac{4}{2.5}}{\dfrac{1}{2}} = 3.2$

$\therefore\;\mathbf{3.2}$ is the correct answer.

Comments

great explanation!👍