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 the next design, the length of pipeline is increased to 5

---

I think it will have 5 stages after the pipeline modified... So, 5*600... which shud give the answer as 6.67%

---

not getting, why u r multiplying time with stages???

https://cseweb.ucsd.edu/classes/sp13/cse141-a/solutions/assignment4_solutions.pdf

see 2.1, 2.2, 2.3 in above pdf

i think sol given by anurag is correct

---

becoz to calculate the execution time of one instruction, the formula is

(k + (n - 1))*tp   where k = no of stages, here n is 1 and also tp is the cycle time

or I can say: k*tp

---

why 600 multiplied by 4 ? it should be multiplied by 5 beacause first stage replaced with 2 stages, so now total stages should be 5

---

Yes i also have sme doubt here that first stage is divided into 2 stages so total stages should be .5 na ???? @arjun sir

---

@arjun sir why it is multiplied by 4 ? How did u get 2400 ps ?

---

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 ??