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

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!👍