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

Time without pipeline $=6 \text{ stages}=6 \text{ cycles}$

Time with pipeline $=1+\text{stall freqency}\times \text{stall cycle}$

 $=1+.25\times 2$
 $=1.5$

Speed up $=\dfrac{6}{1.5}=4$

Comments

@Amoljadhav  see here  at $1:51:43$ sir took $1$ for ideal situation 

---

ok

---

it is the ideal situation ....so every instruction will be taking 1 cycle anyway and the other is the penalty term

Answer 2

Speed Up= 4

Speed up = Time without Pipeline /  Time with Pipeline

Time without pipeline = 6 clock cycle

 25% of the instructions incur 2 pipeline stall cycles means CPI = 3

Time with pipeline = 0.25*( 3 ) + 0.75*1 = 1.5 clock cycle

speed up = 6 clock cycle / 1.5 clock cycle   = 4

Comments

cpi=1+stall cycle

---

Correct Explanation But With One Flaw

This is obviously one of best explanation but here is one flaw according to me as sequencing of these 25% instructions will also matter.

If all 25% instruction are at last then in that case those 25 % will get stablized and avg CPI will be 1 for them as well so total time they take effectively will be(for n instructions) = .75n*1 + 2(moving from normal to stalled instructions) + .25n*1 = n+2

for non pipelined  = n*6

so speed up in that case  = 6*n/(n+2) and for very large n that will be effectively ~6

but if these 25% instuctions are not together and there is 1 such instruction after 3 normal instructions in that case avg CPI for these 25% instructions will be = 3

in that case we can apply above formula...

please correct if i am wrong somewhere.

---

That won't work. It is important to understand here that cpi is nothing but the delay caused in the total execution by any instruction. So even if non stalling instruction comes after stalling one, delay would only be of 2 and not 3.

Answer 3

It was a numerical digit type question so answer must be 4.

As for 6 stages, non-pipelining takes 6 cycles.

There were 2 stall cycles for pipelining for 25% of the instructions

So pipe line time = (1+(25/100)*2) = 1.5

Speed up = Non pipeline time/Pipeline time = 6/1.5 = 4

Answer 4

The question has been answered before. However, when I looked at it, I couldn't get it. So I am providing an alternate explanation here.

By the basic performance equation, we know that $$ \text{Execution Time} = \frac{N \times S}{ R} $$ where N is the number of instructions, S is the average clock cycles taken per instruction and R is the number of clock cycles per second.

Another useful metric is throughput, which is the number of instructions executed per second. It is defined as:

$$\text{Throughput} = \frac{R}{S}$$.

Now in an non-pipelined processor, the number of stages is equal to the number of cycles i.e $S = \text{No. of stages}$

In a pipelined processor, the value of $S = 1$ because an instruction can enter the pipeline in every cycle.

However, this is the case for an ideal pipeline. In case of a pipeline with stall, the general formula is:

$$S = 1 + \delta_{stall} + \delta_{branch} + \delta_{cache}$$ where $\delta$ is the penalty associated with each of the misses.

Here, $\delta_{stall}$ is given as $0.25 \times 2$, hence the value of $S$ is $1+ 0.5 = 1.5$.

So according to the question, non-pipelined $T_{np} = R/6$ and for the pipelined, $T_{p} = R/1.5$.

From this, we can see that the speedup is $4$ times.

Answer 5

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 6

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.