States of a 2-bit Branch Predictor

1
votes

I was reading the dynamic branch prediction section in Chapter 5 of Computer Organization and Design: The Hardware/Software Interface 5th Edition by Patterson and Hennessy when I came across the following diagram for the states of the 2-bit predictor :

enter image description here

The 2-bit predictor should change it's prediction after it predicts wrong twice. But according to this diagram when we start from the bottom left state, if the machine predicts "NOT TAKEN" twice when the branch should have been "TAKEN", then the top right PREDICT TAKEN state is reached. However here the machine will change state to the bottom right PREDICT NOT TAKEN even if it predicts wrongly when the branch should have been "NOT TAKEN" just once.

Isn't that wrong behavior and does this mean the state machine is wrong or am I missing something?

On the bottom NOT TAKEN dark colored state when the branch is TAKEN twice, you can see that the state reached is the light colored "unsure" state, whereas it should have been according to me the dark colored "sure" state, since the branch did the same action twice in a row.

1
cpu-architecturebranch-prediction
What behavior you think is wrong? The light-colored states represent the CPU "not being sure" if the branch should be taken or not. In that situation, a single misprediction is enough to make it "change its mind". When it is in a dark-colored state it is more "sure" about the branch, so it takes two mispredictions in a row to get it to change the prediction. Obviously, it's easy to find pathological examples (e.g. you may fail 100% of times if you start in a light-colored state and have an alternating pattern, taken-not taken-taken-not taken-...). – jdehesa
On the bottom NOT TAKEN dark colored state when the branch is TAKEN twice, you can see that the state reached is the light colored "unsure" state, whereas it should have been according to me the dark colored "sure" state, since the branch did the same action twice in a row. – Rijul Ganguly

1 Answers

2
votes

On the bottom NOT TAKEN dark colored state when the branch is TAKEN twice, you can see that the state reached is the light colored "unsure" state, whereas it should have been according to me the dark colored "sure" state, since the branch did the same action twice in a row.

The light-blue state predicts taken like you want it to after two successive taken branches. If the branch is taken from then on there will be no further mispredicts. I don't think your "should" is justified.

It's a 2-bit saturating counter; it takes 3 steps to get all the way from 00 to 11, corresponding to 3 steps along that graph.

Your idea could be implemented using the 2 bits of state to record which way each of the last 2 branches went. But then how would you tell the difference between a loop branch that was not-taken once (falling out of previous loop) and/or after being taken again once (first iter of next loop) vs. a rarely taken branch that was taken once? The actual way, as shown in the graph, mispredicts a loop branch once per loop, only on the last iteration when it falls through. The first iteration of the next time you enter the loop predicts correctly, returning it to strongly taken.

You can find a detailed example of such a predictor in Raffzahn's answer on How does the 68060 branch predictor work? on retrocomputing.SE, including static prediction (backward taken, forward not-taken) when you get a BPB miss (no prediction entry for this branch).

A 2-bit predictor is very far from perfect; more advanced predictors also consider whether global history predicts this branch better than local. https://danluu.com/branch-prediction/