#pipeline

Question

Consider execution of 100 instructions on a 5 stage pipeline. let P be the probability of an instruction being branch. The value of P such that speed up is atleast 4 is_____(assume each stage takes 1 cycle to perform its task and branch is predicted on forth stage of the pipeline)

Comments

We usually use the formula that Speedup = $\frac{\text{Pipeline Depth}}{\text{CPI_{ideal} + Pipeline Stalls Per Instruction}}$.

Now, this formula works only in the case when all the instructions pass through all the stages of the pipeline. Here, I I've assumed that all the instructions pass through all the stages, and hence wrote the numerator as five. Regarding the denominator, we take the ideal CPI of a processor to be 1 on a pipelined processor.

For the other term, assuming the stalls are only from branches, we can write the stall cycles as $\text{Branch Frequency*Branch Penalty}$. Here, the branch frequency will be $p$ and using the same, I've solved the question.

The important assumption is that CPI of a pipelined processor is $1$ only when the number of instructions are large. For a finite number of instructions, using the exact value of instructions should give a more accurate answer.

---

@Shaik Masthan @shreyansh jain can you update the final answer? 

My doubts are 

1) don't we have to multiple with (p-1) in non branch instruction here

2) we have to multiply branch with cpi=4 why are we taking penalty=3?

---

@Shaik Masthan@shreyansh jain sry sry got it final answer is 0.07 I just did from other method I will update it in ans section soon

Answer 1

Taking some assumptions  , let the 5 stages be IF, D, EX, M ,WB. Since in the case of pipeline it is given that branch will not be known till M, so there will be  3 stall cycles. Branch penalty=3(for branch instructions).

                                                IF  |  ID | E | M | WB

                                                        X |  X | X |  IF |......    so, 3 stall cycles will be there  in case of branch instruction.

Avg CPI(pipelined)= 1(in the ideal case)  +  Branch penalty *# of branch instructions=1+3*P (let P will be the number of branches

instructions)=1+3p.

       In the case of non-pipelined CPI=5(since there will be no overlapping).

Given speedup>=4  

=> 5/1+3p>=4

=>p<=0.084

Comments

Why you have not consider value of n and taken ideal case … I think answer should be 0.07

500/(5+100-1)+100(3x)=4  

By solving this we get x=0.07

Hence, thats the probability