microprocessor - 2-bit branch prediction accuracy

I am trying to solve this problem, the answer should be 15/20 = 75%.

However, I am not sure how this was calculated and want to understand the underlying concept.

A program core consists of five conditional branches. The program core will be executed thousands of times. Below are the outcomes of each branch for one execution of the program core (T = taken, N = Not taken).

 Branch 1: T-T
 Branch 2: N-N-N

 Branch 3: T-N-T-N-T
 Branch 4: T-T-T-N
 Branch 5: T-T-N-T-T-T

This behavior remains the same. For dynamic schemes, assume each branch has its own prediction buffer and each buffer initialized to the same state before execution.

What is the prediction accuracy for the 2-bit predictor, initialized to weakly predict taken? (Answer is at the beginning but I'd like to understand the concept of the calculation.)

Answer

First off, I think it's important for you to specify when you do these types of problems (and clarify by asking your professor) which type of 2-bit predictor is being used, because there are 2 types.

The first type makes a transition from a weak state to the alternate weak state on failure.

The second type makes a transition from a weak state to the alternate strong state on failure.

For this problem, I am assuming it is the first type, which transitions from a weak state to the alternate weak state upon failure. That is the type shown in the picture below:

Consider what happens in each case individually:

WT = weakly taken ST = strongly taken WN = weakly not taken SN = strongly not taken

Branch #1

Predict WT - T : 1/1

Predict ST - T : 1/1

Total : 2/2

Branch #2

Predict WT - N : 0/1

Predict WN - N : 1/1

Predict SN - N : 1/1

Total 2/3

Branch #3

Predict WT - T : 1/1


Predict ST - N : 0/1

Predict WT - T : 1/1

Predict ST - N : 0/1

Predict WT - T : 1/1

Total : 3/5

Branch #4

Predict WT - T : 1/1

Predict ST - T : 1/1

Predict ST - T : 1/1

Predict ST - N : 0/1

Total : 3/4

Branch #5

Predict WT - T : 1/1

Predict ST - T : 1/1

Predict ST - N : 0/1

Predict WT - T : 1/1

Predict ST - T : 1/1


Predict ST - T : 1/1

Total : 5/6

Total of all branches : 15/20