CO-Pipelining-Q11

+1 vote

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%

reshown Jun 13

A) 55% is correct one
answered Jun 13 by (7,480 points)

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 5 days ago by (4,120 points)
edited 4 days ago
Your answer seems perfectly fine but how come they are getting 60%.
Do you thing answer needs any modification?
yeah i think same
If we get T on LNT, we go on ST and not on LT. Refer hamachar, on the internet the flow diagram is incorrect
Yes you are right Hamacher have a different diagram but this diagram is correct, refer Patterson and Hennessy for that also have similar kind of diagram
In this diagram which state should be considered as LT?
And if we consider the correct diagram given in hamacher we are getting the same answer as 60%? Please cross-verify it as i am getting ans as 60% but not sure because dealing with such type of questions for the first time.
changed... now you can see LT