Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How many branches can your CPU predict?

lemire.me

Post reply on HN
Print view View original

41–50 of 66 posts

Re: How many branches can your CPU predict?

#41

Post by stingraycharles »

OskarS wrote: post #6

Hmm, that's interesting. The code as written only has one branch, the if statement (well, two, the while loop exit clause as well). My mental model of the branch predictor was that for each branch, the CPU maintained some internal state like "probably taken/not taken" or "indeterminate", and it "learned" by executing the branch many times. But that's clearly not right, because apparently the specific data it's branch…

> My mental model of the branch predictor was that for each branch, the CPU maintained some internal state like "probably taken/not taken" or "indeterminate", and it "learned" by executing the branch many times.

I always figured the algorithm was much simpler, it would just use the same branch as last execution — should work fairly well.

Didn’t realize it used the input value as well, which to me makes no sense — the whole point is to avoid having to inspect the value. This article raises more questions than answers, I’m intrigued now.

Re: How many branches can your CPU predict?

#42

Post by fc417fc802 »

themafia wrote: post #32

The testing function seems a little simple since branch density is a factor. I still love this reference: https://blog.cloudflare.com/branch-predictor/ Should be titled: How I Learned to Stop Worrying and Love the Branch Predictor

It's odd. The section headers says "Density matters" but then the experiment shows that, actually, density does not matter. Only the total number of branches encountered across the linear piece of code. (In the chart "block size" is what determines density.)

Also note in that chart what's being tested is unconditional jumps placed at unique addresses in a linear piece of code, not conditional jumps at the same address in a loop that fits entirely in L1i.

Re: How many branches can your CPU predict?

#43

Post by atq2119 »

I find it interesting that the S-curve is much steeper for AMD than it is for the others. AMD maintains perfect prediction for much larger sizes than the others, but it also reaches essentially random behaviour earlier.

Are they really keeping a branch history that's 30k deep? Or is there some kind of hashing going on, and AMD's hash just happens to be more attuned to the PRNG used here?

Would be interesting to see how robust these results are against the choice of PRNG and seed.

Re: How many branches can your CPU predict?

#44

Post by stevefan1999 »

I still remember learning about TAGE and preceptron predictors, and how machine learning and neural networks has long been, in some form, been used in CPU architecture design.

The simplest binary saturating counter, ala bimodal predictor, already achieved more than 90% success rate. What comes next is just extension around that, just use multiple bimodal predictors and build a forest of it, but the core idea that treating the branch prediction using a Bayesian approach, never fades.

It is a combined effort between hardware design and software compiler, though.

Re: How many branches can your CPU predict?

#46

Post by stinkbeetle »

atq2119 wrote: post #43

I find it interesting that the S-curve is much steeper for AMD than it is for the others. AMD maintains perfect prediction for much larger sizes than the others, but it also reaches essentially random behaviour earlier. Are they really keeping a branch history that's 30k deep? Or is there some kind of hashing going on, and AMD's hash just happens to be more attuned to the PRNG used here? Would be interesting to see h…

> Are they really keeping a branch history that's 30k deep? Or is there some kind of hashing going on, and AMD's hash just happens to be more attuned to the PRNG used here?

No, you don't need much branch history to get a vanishingly small probability that any two branches would collide. ~40 bits maybe. The limit will be running out of prediction table capacity I would say. It's possible the better ones are able to cleverly fit competing entries in different TAGE tables whereas the worse ones might start thrashing just one or some of the tables since the test is so regular. It's also possible the better ones just have more prediction resources available (or fewer, bigger tables, or ...).

> Would be interesting to see how robust these results are against the choice of PRNG and seed.

Provided it is somewhat random, I would say very robustly since all those CPUs likely have far more than enough history to uniquely fingerprint every branch even if the PRNG was not a great one.

Re: How many branches can your CPU predict?

#47

Post by cloudbonsai »

ErikCorry wrote: post #28
piinbinary wrote: post #25

How does the benchmark tell how many branches were mispredicted? Is that something the processor exposes?

Yeah performance counters

To fill in the details, here is the code used for the measurement:

https://github.com/lemire/counters/blob/main/include/counter...

It fetches the number of mispredicted instructions from Linux's perf subsystem, which in turn gathers the metrics from CPU's PMU (Performance Monitoring Unit) interface.

Re: How many branches can your CPU predict?

#49

Post by eigenform »

OskarS wrote: post #6

Hmm, that's interesting. The code as written only has one branch, the if statement (well, two, the while loop exit clause as well). My mental model of the branch predictor was that for each branch, the CPU maintained some internal state like "probably taken/not taken" or "indeterminate", and it "learned" by executing the branch many times. But that's clearly not right, because apparently the specific data it's branch…

The idea here is about maintaining a "path history"!

When looking up a register that tracks the "local" history of outcomes for a particular branch, you want to have a hash function that captures enough context to distinguish the different situations where that branch might be encountered.

Apart from folding a long "global history" of recent outcomes and mixing in the current program counter, I think many modern machines also mix in the target addresses of recently-taken branches.

Re: How many branches can your CPU predict?

#50

Post by PunchyHamster »

fc417fc802 wrote: post #39
rayiner wrote: post #17

Earlier quoted context omitted.

Your mental model is close. Predictors generally work by having some sort of table of predictions and indexing into that table (usually using some sort of hashing) to obtain the predictions. The simplest thing to do is use the address of the branch instruction as the index into the table. That way, each branch instruction maps onto a (not necessarily unique) entry in the table. Those entries will usually be a two-bit…

It seems like that would struggle with detecting how many layers of branching to pay attention to. Imagine the two nested loops surrounded by a randomized one. Wouldn't that implementation keep hitting patterns it hadn't seen before? Obviously that must be a solved problem; I'd be curious to know what the solution is.

might be but what real code does that ?
Post reply on HN