CO-Pipelining-Q11

+2 votes

We have a program code consisting of five conditional branches. The program code will be executed an arbitrarily large number of times. Below are the outcomes of each branch for one execution of the program code.

 

Branch 1: T-T-T

Branch 2: N-N-T-N

Branch 3: T-N-T-N-N-T

Branch 4: T-T-N-T-T-T-N

 

The 2-bit dynamic branch prediction algorithm is used with the following states.

 

ST    - Strongly likely to be taken

LT     - Likely to be taken

LNT  - Likely not to be taken

SNT  - Strongly likely not to be taken

Assume that each branch has its own prediction buffer and each buffer is initialized to the branch state LT.

What is the overall accuracy of the prediction scheme?

(A) 55%

(B) 60%

(C) 65%

(D) 70%

asked Jun 12 in Computer Organization by gbmentor (54,290 points)
reshown Jun 13 by gbmentor

2 Answers

0 votes
A) 55% is correct one
answered Jun 13 by tsnikhilsharmagate2018 (19,690 points)
plz explain the answer
0 votes

Reference(Image): Hamacher

Every branch initialized with LT

Branch 1:

Prediction Correct
T \checkmark
T \checkmark
T \checkmark

Branch 2:

Prediction Correct
N (\times)
N (\checkmark)
T (\times)
N (\checkmark)

Branch 3:

Prediction Correct
T (\checkmark)
N (\times)
T (\checkmark)
N (\times)
N (\times)
T (\times)

Branch 4:

Prediction Correct
T (\checkmark)
T (\checkmark)
N (\times)
T (\checkmark)
T (\checkmark)
T (\checkmark)
N (\times)

so 

accuracy = \frac{hits}{\text{total prediction}} = \frac{12}{20} = 0.6

\%accuracy = 0.6\times 100 = 60\%

answered Jun 14 by 23rishiyadavpro20 (6,590 points)
edited Jun 16 by 23rishiyadavpro20
how do you marked  'x' for first n in second branch. as it in LT by reading N it will go to SNT
see that again every branch here start from LT(likely to be taken) and when it sees N(Not taken) then its prediction is wrong so it will go to SNT
That's why I have added (cross) X in the first n
@tsprathyushareddy1231
ok thank you
ok . let me clarify  ... is it not like reaching SNT or  ST is correct prediction?
bro please read dynamic branch prediction first, here its nothing like that we have to reach somewhere but here we care about in which state we are in and what type of prediction we get on that state if a prediction positive then we think may be further predictions will come similar so we move towards strongly side of that but when we got wrong then we move to loosly side(nothing is fixed neither taken or not taken)
Answer:
...