GATE Overflow Test Series | Mock GATE | Test 2 | Question: 55

Question

Consider a five-stage pipeline with ideal CPI. Assume that $25\%$ of the instructions executed are branch instructions out of which $75\%$ are taken branches. If the branch target is known at the end of EX stage, what will be the pipeline speedup if taken is the default branch prediction and branch misprediction penalty on average is $10$ cycles?

• A. $3.34$
• B. $3.07$
• C. $4.00$
• D. $4.11$

Comments

some problem in question. Speed with respect to what must be mentioned in question..

Answer 1

When taken branch is the actual branch target we have no penalty.

When taken branch is not the actual branch target (fall through is the actual branch target), we will know this after EX stage. And this has a $10$ cycle penalty on average.
    
So, effective instruction execution time with pipeline
    
$ = 1 + \text{Misprediction Penalty}$

$\quad = 1 + 0.25 \times 0.25 \times 10$
    
$\qquad =   1.625$
    
Speedup  $=\dfrac{\text{Depth}}{1.625} = \dfrac{5}{1.625} = 3.076.$

Comments

should we assume that decoding of instruction happening in the fetch stage itself?

@gatecse Arjun sir, we will do instruction decode in 2^nd stage of the pipeline, so we can only take the branch  decision at the end  of ID stage because we know it is branch instruction in ID stage only, so here 1 cycle stall is occuring.

so isn’t this the correct answer

effective CPI = 1 + avg no of stalls per instruction

                    = 1 + 0.25( 0.75 * 1 stall + 0.25 * 10 stalls) = 1.8125.

what is wrong in this method?

---

********************************************************************************************

should we assume that decoding of instruction happening in the fetch stage itself?

@gatecse Arjun sir, we will do instruction decode in 2^nd stage of the pipeline, so we can only take the branch  decision at the end  of ID stage because we know it is branch instruction in ID stage only, so here 1 cycle stall is occuring.

so isn’t this the correct answer

effective CPI = 1 + avg no of stalls per instruction

                    = 1 + 0.25( 0.75 * 1 stall + 0.25 * 10 stalls) = 1.8125.

what is wrong in this method?

*************************************************************************************

---

@Sachin Mittal 1 @Deepak Poonia Even if we are predicting branch taken, won’t there still be 2 stall cycles as branch target is known after EX stage? This will also reduce speedup right?

Answer 2

Why is it not solved in this way:

 

Fraction of non-branch instructions = 0.75

Fraction of branch instructions = 0.25

CPI of non-branch instructions (ideal CPI) = 1

CPI of branch instructions = (0.75 * 1 + 0.25 * 10) = 3.25, since 75% instructions don’t lose cycles due to correct branch predictions

 

Avg. CPI with pipelining = 0.75 * 1 + 0.25 * 3.25 = 1.5625

CPI without pipelining = 5

Speedup = 5 / 1.5625 = 3.2