retagged by
575 views

1 Answer

Best answer
7 votes
7 votes

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

               =  CPInon pipelined * Clock cycle timenon pipelined /  CPIpipelined * Clock cycle timepipelined

               =   No of stages / CPIpipelined

               =   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

==>    xmin    =   0.9333

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

selected by

Related questions

0 votes
0 votes
1 answer
2
Samujjal Das asked Dec 5, 2016
677 views
0 votes
0 votes
1 answer
3