1
$\begingroup$

I have read various explanations why a 1-bit branch predictor is wrong twice per loop, once at the beginning when it wrongly predicts against entering the loop and once at the end when it wrongly predicts against leaving the loop. Makes sense.

What I don't understand is why the 2-bit predictor is better. It seems it could even be worse, since it might well predict against entering the loop in the first place, hold to that prediction for a second time before beginning to be "right," and then still wrongly predict against leaving the loop at the end.

I could live with "in practice it turns out to not happen that way all that often," but most of these explanations don't seem to be based on such. Rather, they seem (to me) to begin with a demonstration how the 1-bit predictor fails twice, and then merely state that the 2-bit predictor does better without demonstrating that it does.

So...what am I missing?

$\endgroup$
3
$\begingroup$

The assumption is that destructive aliasing (or really any aliasing) is rare. That is, the branch predictor entry is unique to that static branch or at least not shared with another branch that is generally not taken.

If there is no aliasing, a later encounter of the loop will still predict taken for the 2-bit predictor but will mispredict for the 1-bit predictor. (A 1-bit predictor will also lack constructive aliasing with other loops since the previous encounter with the other loop will set the predictor entry to not-taken.)

(The common technique of BTB filtering "never" taken branches (i.e., a BTB miss for a branch that is not taken does not update the predictor and behaves as if no branch was present) can reduce destructive aliasing for taken branches.)

For loop dominated workloads a loop branch is both less likely to alias (fewer static branch instructions, one static branch accounts for multiple dynamic branches) and less likely to have destructively aliasing (constructive aliasing with other loop branches is more likely).

If aliasing were common, branch prediction would not work well because the prediction would not apply to the branch being predicted. (A 1-bit predictor can reduce aliasing by providing twice the number of entries compared to a 2-bit predictor of the same storage capacity. For certain workloads with high static branch count, the tradeoff of number of entries/aliasing and hysteresis may be justified.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.