ISRO2020-7

Question

Consider a $5$- segment pipeline with a clock cycle time $20$ ns in each sub operation. Find out the approximate speed-up ratio between pipelined and non-pipelined system to execute $100$ instructions. (if an average, every five cycles, a bubble due to data hazard has to be introduced in the pipeline)

• A. $5$
• B. $4.03$
• C. $4.81$
• D. $4.17$

Comments

$$\frac{100*5*20}{[1(5)+99(1)+\frac{1(5)+99(1)}{5}]*20}$$

$$=> \frac{100*5*20}{[104+21]*20}$$

$$=> \frac{500}{125}$$

Option B

---

option B) 4.03 is correct

                speed up = exec. time non pipeline/ exec. time pipeline

                               = 100*5*20 / {(5*20)+(99*20)}+400

                              =4.03

Answer 1

$T_{\ without\ pipeline} = no.\ of\ instructions \times stages\ in\ pipeline \times  clock\ cycle\ per\ stage $

                              $= 100\times5\times20 $

$T_{pipeline} = (time\ for\ pipelined\ execution\ without\ stalls) + (overhead\ due\ to\ stalls) $

                $= (5+99)\times20 + 20\times20 = 124\times20$

$\therefore speed\ up = \frac{T_{\ without\ pipeline}}{T_{pipeline} } = \frac{500\times20}{124\times20} = 4.03$

$\therefore$ Option $B.$ is correct

Comments

Satbir

Can u please tell me what is the meaning of this line actually -

(if an average, every five cycles, a bubble due to data hazard has to be introduced in the pipeline)

I can't interpret this line.

at every 5 cycles, there is stall, means 1st stall @5, 2nd stall @10, 3rd stall @15........so on

Is it like that ???

then why can't we do like = 1 + #stall rate * #stall cycle.

New CPI = $1+\frac{1}{5}*1$ 

---

How did you came up with the above formula ?

---

bro logic is correct but i think you have done just one mistake

for non pipeline it should be:: 1.2*(99*1+5*1)=104*1.2

so we get 10^4/2496=appx 4.01 as the ans

Answer 2

$\underline{\textbf{Answer:}\Rightarrow}\;\;4.76$

$\underline{\textbf{Explanation:}\Rightarrow}$

Number of stalls $=5$
Clock Time $=20\;\text{ns}$
Number of instructions $=100$

Time taken by non-pipelined system $=5\times 20\times 100 = 10000$
Time taken by a pipelined system if no stall is present $=5\times \enclose{circle}{1}\times 20 + \enclose{circle}{99}\times 20 + \mathbf{19\;stalls} = 2099 \;\;\text{[Since, stall in the last cycle is insignificant.]}$

$\mathrm{5, stall, 10, stall, 15, stall, 20, stall, 25, stall, 30, stall, 35, stall, 40, stall, 45, stall, 50, stall, 55, stall, 60, stall, 65, stall, 70, stall, 75, stall, 80, stall, 85, stall, 90, stall, 95, stall, 100, \require{cancel} \cancel{stall}=19 \;stalls}$

$\therefore \;\text{Speedup} =\dfrac{\text{Time without pipelining}}{\text{Time with pipelining}}= \dfrac{10,000\;\text{ns}}{2099\;\text{ns}} = 4.76$

Comments

They have said

on an avg 5 cycles 

Means stalls can be anywhere in the 5 cycles

---

But we have to read every as well.

Anyway that looks debatable. Leave it.

---

With 19 stalls, the denominator would be $(104+19)*20$

Which brings you to Option B.

Answer 3

Non-pipeline time=5*20*100=10000 ns

pipeline time= time for first item + time for rest 99 item + due to stalling (20 nos)=1x 5clock cycle +99* 1 clock cycle+20*20 (stalling)=1*5*20+99*20+400=2480

Hence the speed up ratio= 1000/24680=4.0322  which is confirms the option B.

Answer 4

A 5 segment pipeline with clock cycle time of 20ns.
Time without pipeline for one instruction = 5*20 = 100ns.
For 100 instructions time without pipeline = 100*100ns = 10^4 ns.
With pipeline, it is given that on average for every 5 cycles there is one bubble or stall cycle which is introduced. So stall frequency = ⅕.
In general in a pipeline we have clocks per instruction CPI = 1. But when there are stall cycles, the updated CPI = (1 + stall frequency * no. of stall cycles) = (1+⅕*1) = 1.2
Execution time with the pipeline = no. of instructions * CPI * clock cycle time.
= 100 * 1.2 * 20 = 2400ns
Speed up = Time without pipeline / Time with pipeline
= 10^4 / 2400 = 100/24 = 4.17

Comments

bro logic is correct but i think you have done just one mistake

for non pipeline it should be:: 1.2*(99*1+5*1)=104*1.2

so we get 10^4/2496=appx 4.01 as the ans