edited by
1,118 views
1 votes
1 votes

Assume that execution of 200 instructions on a 6 staged pipeline where the target address is available at 4th stage.Let X be the probability of an instruction not being branch. The value of X such that speedup is atleast 5 is ________ ?

----------------------------------------------------

Doubt:

=> I know the normal method i.e.      K stages / (1 + Branch freq * Stall cycles)   =  Speedup             which yields near to exact answer.

=> But I am unable to get the answer by :    ( K stages * instructions ) / [ (K + N - 1) + (freq * stalls) ]        

Method 2) : 6 * 200 / [205 + (1 - X)*3]  

=> 1200 / (208 - 3X) = 5

=> 1200 = 1040 - 15X

=> 15X = - 160              Which is not possible.

Where am I going wrong ??

 :

edited by

2 Answers

Best answer
3 votes
3 votes
Got it! Actually in second method I was directly considering the probability. But, its a percentage of number of instructions which have taken the branch.

So, Y% instructions are branches = branch freq.

Hence,     (200 * 6) / [205 + (Y/100 * 200 * 3)] Which gives Y around 6% and so our required X would be 94% which is 0.94 [to be exact] :)
2 votes
2 votes
Speed up is at least 5.

So , $5 \leqslant \frac{(Non pipelined time )}{ Pipeline time}$

Here , target address is available at the 4th clock cycle. So , if we execute any instruction at the 1st clock cycle , we would need to wait till 4th clock cycle to get the output. So, this is stall. So , stall cycle = (4-1) =3

So ,

$5 \leqslant \frac{(6 )}{(1+stall frequency * stall penalty)}$

 

Now , here question asks about when not branch.

$5 \leqslant \frac{(6 )}{(1+(1-stall frequency) * stall penalty)}$

$5 \leqslant \frac{(6 )}{(1+(1-X) * 3)}$

so , on solving , x comes 0.933

 

So , 1-x comes as 0.066. So , not to branch probability 0.07.

Related questions

2 votes
2 votes
4 answers
2
2 votes
2 votes
1 answer
3
Satbir asked Jan 16, 2019
853 views
5 stage pipeline → 3,6,5,8,4 latencies(in ns).What is average CPI of non pipelined CPU when speed up achieved by to pipeline is 4 ? (ans = 1.23)