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

@vaishnavi30

 “If the stages are perfectly balanced, then the time per instruction on the pipelined machine is equal to Time per instruction on non pipelined machine”

This is true only for first instruction . 

---

@abir_banerjee can u share a referance where it’s written that it’s true only for first instruction ?

---

Assume that there is no cycle-time overhead of pipelining.

This means that we are assuming that introducing a pipeline into our currently non-pipelined system keeps the clock period unaffected, right?

Answer 1

Suppose 'n' instructions are there and n is very large...and Tp time of each cycle. Thus we are having 0.25n branched and 0.75n non-branched instructions

now 0.25n instructions create 2 stalls and thus the time taken is:

           =    #f cycles * Tp

           =   (6+0.25n-1 + 2*0.25n)Tp

           =   (5+0.75n)Tp

Now similarly for non branch, time= (6+0.75n-1)Tp = (5+0.75n)Tp

thus total time taken in Pipeline =  (5+0.75n)Tp + (5+0.75n)Tp =(10 + 1.5n)Tp

For Non pipeline time taken for n instruction = #f cycles for per instruction * each cycle time * #f instructions

                                                                      = 6*Tp*n = 6n*Tp

now, speedup achieved =Time(non-pipe)/Time(pipe)

                                      = (6n Tp) / (10+1.5n)Tp 

                                      = 6n / (10+1.5n)

  as  n → ∞, taking limits,  speedup= 6/1.5 =4

     

                    

Answer 2

In non-pipelined , for 100 instructions, we need 6*100 = 600 cycles. As 6 stages are there and no cycle time overhead.

Now in pipelined architecture we need = 6+ (100-1) = 105 cycles and 25 instructions additionally take 2 cycle stalls so 25*2 = 50 cycles more, so 105+50 = 155 cycles in pipelined architecture.

So speedup = 600/155 = 3.87 ~ 4.

4 is the ans.

Answer 3

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

Answer 4

“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