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

Speed Up = New performance / Old performance

Old performance => Old throughput (instructions/second)=> (1/800p)... (1)

New performance => Old throughput (instructions/second) (1/600p)...(2)

Speed up= 2/1 = (1/600) / (1/800)  =1.33333

Improvement  = 1.33333-1 =.3333333*100 = 33.33 % Answer

Answer 2

$\text{Suppose you have n instructions}$

$\text{Apply this formula}$

$\frac{(k1+n-1)d1}{(k2+n-1)d2}$

$\text{In our case k1 is 4 as you have 4 stage pipeline}$

$\text{and k2 is 5 as you will get a new pipeline having 5 stages}$

$\text{In First pipeline you have delay as d1 = 800}$

$\text{In second pipeline you will be having delay as d2 = 600}$

$\text{Put everything in the formula}$

$\text{Speedup will be}$

$\frac{(3+n)*800}{(4+n)*600}$

$\frac{24+8n}{24+6n}$

$1+\frac{2n}{24+6n}$

$\text{Divide the numerator and dinominator by n}$

$1+\frac{2}{ \frac{24}{n}+6}$

$\text{For large n,}$ $\frac{24}{n}$ $vanishes$

$1+\frac{2}{6}$

$1+0.3333...$

$\text{You can clearly see that the speedup has increased by 33.33%}$

Answer 3

In a pipelined processor the throughput is 1/clock cycle time.
Cycle time = max of all stage delays.
In the first case max stage delay = 800.
So throughput = 1/800 initially.
After replacing this stage with two stages of delays 600, 350... the cycle time = maximum stage delay = 600.
So the new throughput = 1/600.
The new throughput > old throughput.
And the increase in throughput = 1/600 - 1/800.
We calculate the percentage increase in throughput w.r.t initial throughput, so the % increase in throughput
= (1/600 - 1/800) / (1/800) * 100
= ((800 / 600) - 1) * 100
= ((8/6) -1) * 100
= 33.33%

Answer 4

Let say there are n instructions.

For the first pipeline with 4 stages, clock cycles needed = (4+n-1) = (3+n) clock cycles = (3+n)*800ps

Now throughput for n instructions will be n/(3+n)*800, considering n to be asymptotic throughput = 1/800

similarly throughput for second pipeline = 1/600

increase in throughput = (1/600 - 1/800)/(1/800) = 0.33

percentage increase = 33.33%.