# 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.)

• This is not a programming question. It appears to be a hardware design question. Try cs.stackexchange.com
– Raymond Chen
Oct 22 '14 at 18:49

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

Assuming this is a local branch predictor, the answer of 5 mispredictions and 15 correct predictions. The easiest way to visualize this problem is by creating the FSM for a 2-bit branch predictor and flowing through each branch to see what the predictor predicts and what state is moves to:

Using this FSM, we per branch see what it predicts and what it goes to next:

Branch 1:

Step:         T   T
Prediction:   T   T
State:        WT  ST
NextState:    ST  ST
Correct?:     Y   Y

Branch 2:

Step:         N   N   N
Prediction:   T   N   N
State:        WT  WNT SNT
NextState:    WNT SNT SNT
Correct?:     N   Y   Y

Branch 3:

Step:         T   N   T   N   T
Prediction:   T   T   T   T   T
State:        WT  ST  WT  ST  WT
NextState:    ST  WT  ST  WT  ST
Correct?:     Y   N   Y   N   Y

Branch 4:

Step:         T   T   T   N
Prediction:   T   T   T   T
State:        WT  ST  ST  ST
NextState:    ST  ST  ST  WT
Correct?:     Y   Y   Y   N

Branch 5:

Step:         T   T   N   T   T   T
Prediction:   T   T   T   T   T   T
State:        WT  ST  ST  WT  ST  ST
NextState:    ST  ST  WT  ST  ST  ST
Correct?:     Y   Y   N   Y   Y   Y


So, if we count the number of Ys, we get 15/20 or an accuracy of 75%. (conversely, 5/20 Ns, so 25% misprediction).

A two-bit predictor is just a number from 0 to 3, like this

• 0 - strongly not taken
• 1 - weakly not taken
• 2 - weakly taken
• 3 - strongly taken

where state (2) is what you'd get at first branch execution.

• Branch 1: T-T - the predictor is right the first time, and the predictor is increased (with saturation at (3)) and predicts "taken" for both iterations
• Branch 2: N-N-N - the first one is a failure, and the predictor is decreased (with saturation at (0)), predicting the next two Ns. We have 2 hits, 1 miss.
• Branch 3: T-N-T-N-T - the one here is interesting. We oscillate between (3) and (2), being wrong on each "N". 3 hits, 2 misses.
• Branch 4: T-T-T-N - this is similar; out of 4 occurrences, one is mishandled
• Branch 5: T-T-N-T-T-T - again, out of 6 occurrences, one is mispredicted.

Summing hits and misses: (2h+0m) + (2h+1m) + (3h+2m) + (3h+1m) + (5h+1m)

Summing: 15 hits, 5 misses

Accuracy = hits / (hits + misses) = 15 / 20.

• Thanks your answers are equally great but the visual helps a lot. Thanks for the accuracy formula at the end @anrieff. Oct 22 '14 at 19:40

Well, you don't even need to do the math if you note that a 2-bit predictor changes its mind if it mispredicts two times in a row.

Branch 1: always predicts right (2/2)

Branch 2: always predicts rights (3/3)

Branch 3: this one is interesting. For this one you need to write the states and do the math. it turns out you can predict correctly 3 out of 5. For this case, the initial value of the predictor is important.

Branch 4: 3 out of 4

Branch 5: 5 out of 6

total is 15 out of 20.

Takeout: A 2-bit local predictor works well for highly biased branches, but not for branches that change frequently (like Branch 3).