GATE CSE 2014 | Set 1 | Question: 43

Question

Consider a $6$-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this $6$-stage pipeline, the speedup achieved with respect to non-pipelined execution if $25$% of the instructions incur $2$ pipeline stall cycles is ____________

Comments

#stalls per Instr. = 0.25 * 2 = 0.5
Avg Exec time = (1+#stalls per Instr) * Tp = (1+0.5) Tp
Exec Time without pipeline = no. of stages * Tp = 6 Tp
Speed up = ET without pipeline / ET with pipeline
S = 6 Tp / 1.5 Tp = 4

---

Ans

---

Assume that there is no cycle-time overhead of pipelining means delay due to buffer register is zero(0)

Answer 1

$Speedup =\frac{ No. \,of \,stages(or \,pipeline\, depth)}{1 \,+ \,Pipeline \,stall\, cycles \,per\, instr.} = 6/1+0.25(2) = 6/1.5 = 4$

Answer 2

“All stages are perfectly balanced” means ALL STAGES TAKE SAME TIME (say, t time)

“No cycle time overhead of pipelining” means there is no buffer

Given , k=6

for Non-pipelined processor, tn=6t and CPI=1

for Pipelined Processor, tp= MAX(t,t,t,t,t,t)=t

FINDING CPI:

say, we have n-instructions

25% of n-instructions incur 2 stalls each

CPI= (n + 0.25*n*2)/n = 1.5

 

Speedup= slow process/ fast process

= 1 instruction execution time for non-pipeline/ 1 instruction execution time for pipeline

= (CPI for non-pipeline)* tn  / (CPI for pipeline)*tp

= 1*6t/1.5*t

=4

 

Answer 3

Assume we are doing it for 100 instructions

Non pipelined instructions

every instruction will take 6 cycle’s each so a total of  6*100 =600

 

Pipelined

25% has 2 stall cycles when 2 stall cycles they will have a cpI=3

Stall cyle is the part of the cycle where no operation is performed

 

75* of instructions when done on pipeline will have a cpi =1

 

so total cycles for pipeline = 25*3 + 75*1 =150 cycles for 100 instructions

 

speedup achieved = cycles for non pipeline/cycles for pipeline =600/150   =4

Answer 4

No. of stalls per Instr. = 0.25 * 2 = 0.5
Avg Exec time with pipeline = (1 + #stalls per Instr) * Tp = (1+0.5) Tp
Avg Exec Time without pipeline = no. of stages * Tp = 6 Tp
Speed up = ET without pipeline / ET with pipeline
S = 6 Tp / 1.5 Tp = 4

Answer 5

Ans