seedup due to pipelining

Question

Answer 1

Basically the question is asking about x i.e. branching probability..

Assuming uniform pipeline , i.e. cycle times of all stages are same,,then

Speedup  =  Execution time in non pipelined system / In pipelined system

               =  CPI_{non pipelined} * Clock cycle time_{non pipelined} /  CPI_pipelined * Clock cycle time_pipelined

               =   No of stages / CPI_pipelined

               =   No of stages / (1 + No of stall cycles per instruction) [As CPI of ideal pipeline  =  1]

Now stall will happen here due to branch instruction only since only this factor is mentioned(other factors include cache miss , data dependency etc) ..Now we know ,

No of stalls / instruction (Branch penalty)  = Stage at which target address is computed - 1

So ,

 No of stalls / instruction for a branch instruction(Branch penalty)   =  4 - 1   =  3

Given probability of non branch instruction  = x

So probability of branch instruction             = 1 - x

So stalls / instruction effectively                =  3(1-x)

Hence for speedup to be at least 5 , we have :

          6 / (1 + 3(1-x))  >= 5

==>    6 / (4 - 3x)        >= 5

==>    6      >= 20 - 15x

==>    x      >=  14 / 15

==>    x_min    =   0.9333

So max of  6.67 % instructions approximately is allowed to be branch instructions to attain minimum speedup of 5..

Comments

Here target address is available at 4th stage ... means that after 3 stages we can fatch the branch istruction?

---

Yes that is why 3 cycles penalty is incurred here..

---

Shouldn't $T_p = 1*x+3(1-x)$ instead of $1 + 3(1-x)$?