GATE CSE 2016 Set 1 | Question: 32

Question

The stage delays in a $4$-stage pipeline are $800, 500, 400$ and $300$ picoseconds. The first stage (with delay $800$ picoseconds) is replaced with a functionality equivalent design involving two stages with respective delays $600$ and $350$ picoseconds. The throughput increase of the pipeline is ___________ percent.

Comments

Whats wrong with below approach:

Pileline 1 - 1 instruction in every 800 picosecond

Pipeline 2 - 1 instruction every 600 picosecond

Throughput increase - 800-600/800 = 1/4 = 0.25 = 25%

---

@Prateek

Throughput = Instructions/second

So, Throughput in old design = 1/800 (units can be ignored for percentage increase)

Throughput in new design = 1/600

Therefore, "percent" increase in throughput is:

( (New - old) / old) * 100 =

( ((1/600) - (1/800)) / (1/800) ) * 100 = 33.28%

You are using "maximum delay" instead of throughput for the calculation.

---

What is throughput ( in terms of instruction execution in a pipelined architecture )

Throughput = the no. of instruction executed per unit time( 1 sec ) = 1 / Tp

Here 800 psec is needed to execute 1 instruction.

so In 1 sec, this much instruction will get executed= 1 / 800 psec

OR  

Throughput = no.of instructions executed / total time taken to execute these instructions = n / (K+(n-1))* Tp

If the no. of instructions to be executed is not given(n not given) then use the 1st formula.

Answer 1

In pipeline ideally  $CPI=1$
So in $1$ cycle $1$ instruction gets completed
Throughput is instructions in unit time
In pipeline $1,$ cycle time$=$ max stage delay $=800\  \text{psec}$
In $800\ \text{psec},$ we expect to finish $1$ instruction
So, in $1\;\text{ps},$   $\dfrac{1}{800}$  instructions are expected to be completed, which is also the throughput for pipeline $1.$

Similarly pipeline $2,$ throughput$=\dfrac{1}{600}$
Throughput increase in percentage

$=\dfrac{\text{new-old} }{\text{old}}\times100$

$= \dfrac{\dfrac{1}{600}-\dfrac{1}{800}}{\dfrac{1}{800} }\times 100$

$=\dfrac{200}{600}\times 100$

$=33.33 \%$

Comments

@Shaik Masthan

Spell check Line 3: Throughout → Throughput

Not a major error though. 😉

---

How are we supposed to choose whether to apply ideal conditions or practical conditions if nothing is specified?

---

Thank you for your explanation.

Answer 2

Maximum throughput of a Pipeline i.e in best case without any stalls is equal to Clock Frequency of the pipeline

In first case Clock cycle time $=\text{Max Stage Delay = Max(800,500,400 and 300)} = 800.$

So clock Frequency $=\dfrac{1}{800}$ (Ignore the units as we have to calculate percentage only)

In Second Case Clock cycle time $= \text{Max(600,350,500,400 and 300)} = 600.$

So clock Frequency $=\dfrac{1}{600}.$

Percentage increase in throughput of pipeline $=\text{percentage in Clock Frequency}$

$=\dfrac{\left(\dfrac{1}{600}-\dfrac{1}{800}\right)}{\dfrac{1}{800}}\times 100 = 33.33\%$

Comments

Nice explanation.

---

multiply with 100 , in last step then you will get 33.3333%

Answer 3

33.33 % increase

initial through put is 1 instruction for 3200 pico seconds  

Reason : 4*800  ( here 800 is maximum stage delay of any stage in an instruction so its selected as syncronous clock cycle time )

in the next design 

through put will be 1 instruction for 2400 pico seconds 

reason : 4*600 ( here 600 is maximum stage delay of any stage in an instuction so its selected as syncronous clock cycle time) 

now increase in throughput is caluclated by ((1/2400)-(1/3200))/(1/3200)*100

now there is an assumption that the pipeline used is syncronous because if assyncronous is used the through put is droped but not increased

Comments

In normal cases n is much more greater than k..so, k+n-1 is almost equal to n..that's why we can say CPI for pipeline is approx 1..

That's why no of stages can be ignored..throughput will be 1/cycle time

---

@bikram sir Is this method correct? And are we supposed to ignore k here as its small compared to n?

---

@shraddha priya 

yes , this method is correct, you can see the best chosen answer.

k = no of stages  , this can be ignored when n = number of tasks are large .

if we have a k-segment pipeline with a clock cycle time tp to execute n tasks. 

The first task T1 requires a time equal to k*tp to complete its operation since there are k segments in pipeline. The remaining n-1 tasks emerge from the pipe at a rate of one task per clock cycle and they will be completed in k+n-1 clock cycles. 

so when number of tasks is >> number of segments , that time k+n-1 = n clock cycles ..

so we supposed to ignore k here as its small compared to n .

Answer 4

Speed up = 800/600 = 1.3333
For %, just multiply 100,   133.33
So increase in thoughput is 33.33% (Ans)

Comments

@Ahwan, here why are you considering pipelining to be ideal ?? avg CPI = 1

why arent we finding avg cpi for both the cases and then calculating throughput increase ??