GATE CSE 2016 Set 2 | Question: 33

Question

Consider a $3 \ \text{GHz}$ (gigahertz) processor with a three stage pipeline and stage latencies $\large\tau_1,\tau_2$ and $\large\tau_3$ such that $\large\tau_1 =\dfrac{3 \tau_2}{4}=2\tau_3$. If the longest pipeline stage is split into two pipeline stages of equal latency , the new frequency is __________ $\text{GHz}$, ignoring delays in the pipeline registers.

Comments

Simplest one:

$T1 = \frac{3T2}{4} = 2T3$
Suppose, $T1=12, T2=16, T3=6$. T2 is divided into two equal parts, therefore
$T1=12, T_{21}=8,T_{22}=8, T3=6$

Cycle time = max(all stage delays), and frequency = $\frac{1}{Cycle-Time}$

$\frac{1}{16}=3$

$ \frac{1}{12}= x$ do cross multiplication, and we get $x=4$

---

geeks solution is best on this one..

https://www.geeksforgeeks.org/gate-gate-cs-2016-set-2-question-43/

---

As simple as possible

 

$T_{1}$ is 2 times $T_{3}$ $\Rightarrow$ $T_{1}$ > $T_{3}$

$T_{1}$ is $\frac{3}{4}$th of $T_{2}$ $\Rightarrow$ $T_{2}$ > $T_{1}$

these two implies $T_{2}$ > $T_{1}$ > $T_{3}$

So time taken by 2nd stage ( ie $T_{2}$ ) is used to calculate frequency of the processor. $\Rightarrow$ $T_{2}$ = $\frac{1}{3}$

Let $T_{1}$ = K , which implies

$T_{3}$ = $\frac{K}{2}$

$T_{2}$ = $\frac{4}{3}$K  = $\frac{1}{3}$ $\Rightarrow$ K = $\frac{1}{4}$

 

We will now split $T_{2}$ ( ie $\frac{4}{3}$K  ) into 2 stages as $T_{21}$ =  $\frac{2}{3}$K  and $T_{22}$ = $\frac{2}{3}$K

 

Now we have four stages

$T_{1}$ = K

$T_{21}$ = $\frac{2}{3}$K

$T_{22}$ = $\frac{2}{3}$K

$T_{3}$ = $\frac{K}{2}$

Out of these four stages $T_{1}$ is largest. $T_{1}$ = K = $\frac{1}{4}$. So the new frequency is 4. (GHz)

---

$4T_{1}$ = $3T_{2}$ = $8T_{3}$

$T_{1}:T_{2}:T_{3}$ = $\frac{1}{4} :\frac{1}{3}:\frac{1}{8}$

$\frac{x}{3}$ = $\frac{1}{3G}$

x = $\frac{1}{G}$

T2 is the highest & divided into two stages, So it becomes $\frac{1}{6}$

Now, Highest is $\frac{1}{4}$

So $\frac{1}{\frac{x}{4}}$ = 4G

Answer 1

Answer is 4 GHz.

Given $3$ stage pipeline , with $3\text{ GHz}$ processor.

Given , $e_1 =\dfrac{3e_2}{4}=2e_3$

Put $e_1 = 6x$ 

  we get, $e_2 = 8x\  , e_3 = 3x$

Now largest stage time is $8x$.

So, frequency is $\dfrac{1}{8x}$

$\Rightarrow\dfrac{1}{8x}=3 \text{GHz}$  

$\Rightarrow\dfrac{1}{x}=24\text{ GHz}\quad \rightarrow (1)$

---

Now, we divide $e_2$  into two stages  of $4x\ \&\ 4x.$

New processor has $4$ stages -

$6x,\ 4x,\ 4x,\ 3x.$

Now largest stage time is $6x$.

So, new frequency is 

$\dfrac{1}{6x}$ = $\dfrac{24}{6}$ =  4 GHz (Ans)  $[\because \text{from}\; (1)]$ 

Comments

Is my answer correct i am getting 4.04Ghz instead of 4Ghz

---

@ Ananya Raj

It would have been better if you would have consider fractions.

 

---

@ Ananya Raj Correct, u got that .04 more because of  divisions.

Answer 2

I hope this way it's more easy to understand

 

 

Answer 3

Consider, for first case t1=k, t2=4k/3, t3=k/2

Now, for n instructions time to complete the execution is with $3 * 10^9$ Hz clock speed is $n * (1/3) * 10 ^{-9} (\because CPI = 1 $ for pipelined processors).

According to 3-stage pipeline time for n instructions would be :${k}+{4k/3}+{k/2}+{{(n-1)} *{4k/3}}$

by equating these two

$n * (1/3) * 10 ^{-9} {=} {k}+{4k/3}+{k/2}+{{(n-1)} *{4k/3}} $

$ \therefore  (1/3) * 10 ^{-9} {=} {k/n}+{k/2n}+{4k/3} $

So if n is very large we can do,

 $ \lim _ {n \to \infty  } \left ( (1/3) * 10 ^{-9} {=} {k/n}+{k/2n}+{4k/3} \right ) $

By solving this,

$ (1/4) * 10 ^{-9} {=} {k}$

 

Now, we divide 2nd stage so t1=k, t2=2k/3,t3=2k/3, t4=k/2

Consider x to be the resultant frequency or clock speed.

By following the exact same procedure as above, Taking longest pipeline stage as stage 1.

${1/x} {=} {k}$

$ \therefore x {=} {1/k}$

$\therefore x {=} {4 * 10^{9}}$

which is 4 GHz.

Comments

The eqn. should be (n + 2 ) * (4k / 3 )  instead of

(n + 2 ) * (4k / 3 ) = n / (3 * 10^9 )  

Then for n -> inf.

k = (1 / 4 ) * 10^-9

now for 4 - stage since k is large

we get 4GHz.

Answer 4

here frequency=3GHZ 

cycle time =1/frequency=1/3 *10^-9 sec

here pipeline has 3 stages and stage delay is given as : 

τ₁  = 3/4τ₂ = 2τ₃ 

now equate all stage delay in terms of τ_1, so that we can distinguish the largest delay _.

and that is :τ₁  = 4/3 τ₁ = 1/2 τ₁

so here we got  4/3 τ₁ is the largest delay_.(  number of input is not given so we are assuming it would be a very lage number .)

time taken by pipeline is : (K+n-1)cycle time ,  where( cycle time = largest stage delay+buffer delay + some extra overhead ) and we have only stage delay so cycle time will be that only .now we can write it as :

n*4/3 τ_{1  =}  n* 3*10^-9  ( n is very large so rest calculation with it will be negligible )

and here we got , τ₁ =1/4 * 10^-9 ,

split the  largst stage in two stages with equal delay :

stage1= τ₁ ,stage 2= 4/6 τ_{1 stage 3 =} 4/6 τ_{1 ,} stage4 ₌  τ_1/2  

and  the largest delay = cycle time is now τ1  which is 1/4 *10^9

so frequency = 4GHZ