gatebook mt2 qn-36

Question

Consider a simple in-order five-stage pipeline with a two-cycle branch misprediction penalty and a single-cycle load-use delay penalty. For a specific program, 30% of the instructions are loads, 20% are branches, the remaining 50% of instructions are simple single-cycle ALU operations. Half of the load instructions are followed immediately by a dependent instruction, and 75% of branches are predicted correctly. What is the average CPI of this program on this processor?

Comments

Reference : 

http://www.cis.upenn.edu/~cis371/16sp/exams/cis371-12sp-exam2-soln.pdf

Answer 1

Here the key thing is :

CPI = 1 in case of ideal pipeline which has no stalls

Now we need to find no of stalls / instruction according to given specifications :

Stall due to branch penalty due to misprediction in branching  =  Fraction of branch ins. * Fraction of misprediction * Stall cycles

                                                                                         =  0.2 * 0.25 * 2  =  0.1

Stall due to load use delay                          =   Fraction of load ins. * Fraction of dependency(i.e. if instruction which is                                                                                    dependent immediately follows)  *  stall cycles

                                                                 =    0.3 * 0.5  * 1

                                                                 =    0.15

Hence total stalls / instruction                      =    0.1  + 0.15

                                                                 =    0.25 cycles

Hence CPI_pipeline                                                      =    CPI_{ideal pipeline}  + Stalls / instruction

                                                                 =    1.25 

Hence required no of cycles / instruction       =   1.25

---

Diagrammatically 

Comments

@Habib

What is meant by 'a single-cycle load-use delay penalty' ?

With the phrasing of sentence it seems to me like load is taking single cycle and will take a delay penalty if dependent instruction comes.

Is there any standard definition of delay penalty.

Answer 2

Plz, correct me if my way is wrong!

Branch= 2 cycle delay, Load= 1 cycle delay

30% Load+ 20% Branch+ 50% Other

0.3(0.5(1+1) + 0.5(1)) {Half of the(50%) load instructions are followed immediately by a dependent instruction, meaning::They don't need that load cycle anymore} + 0.20(0.75(1)+0.25(1+2)){75% of branches are predicted correctly,meaning::They don't need those branch missprediction penalty, because they are predicted correctly}+0.5(1)

=0.3+0.45+0.5

=1.25

P.S. correct me if I'm wrong!

Comments

the remaining 50% of instructions are simple single-cycle ALU operations

What is the meaning of this. for ALU do we need to do 0.5*1???