Hacker News Reader

Comment by avian | Hacker News Reader

The GitHub page links to a video that explains some of the internals [1]. Can someone comment on the result that they show at 14:26?

My understanding is that they run a code that does 2000 branches based on a pseudo-random sequence. Over around 10 runs of that code, the CPU supposedly learns to correctly predict those 2000 branches and the performance steadily increases.

Do the modern branch predictors really have the capability to remember an exact sequence of past 2000 decisions on the same branch instruction? Also, why would the performance increase incrementally like that? I would imagine that it would remember the loop history on the first run and achieve maximum performance on the second run.

I doubt that there's really a neural net in the silicon doing this as the author speculates.

[1] https://youtu.be/wlvKAT7SZIQ?t=864

View on HN

Modern branch predictors absolutely have neural nets these days. Check out for example this 2001 IEEE paper on "dynamic branch prediction using neural networks": https://ieeexplore.ieee.org/document/952279 or this 2007 patent using "conditional bias" (it beats around the bush, only explicitly naming neural networks once, but it's clear what it is about if you read between the lines): https://patents.google.com/patent/WO2009066063A1/en.

There is a wealth of patents and articles if you search for "neural net branch prediction patent".

Well, that's certainly the most surprising thing I've learned today. Thanks.

Now, the natural next question: are there commercial cpus available which branch prediction is Turing complete?

Can you clear up whether you mean “there’s a paper that describes using neural nets” or “there’s an actual modern CPU that uses neural nets for branch brediction”?

AMD said back in 2016 to have a neural net predictor [1]. I found this slide following references in the Wikipedia article that rowanG077 linked below.

[1] https://cdn.arstechnica.net/wp-content/uploads/sites/3/2016/...

> Anticipate future decisions, pre-load instruction, chose best path through the CPU.

This slide is about speculative execution not necessarily about branch prediction.

Pre-loading instructions doesn't mean they're actually getting executed. It sounds like it's talking about branch prediction.

I originally meant "people were already doing this in the lab 19 years ago", but you are right that that does not mean CPUs "in the wild" actually do this. I originally learned about it from a blog post where someone uncapped chips to make photographs of the die and made an offhand comment about the branch prediction having neural nets.

I did some more searching and found an article at https://acad.ro/sectii2002/proceedings/doc2019-2/12-Vintan.p... which describes Samsung Galaxy S7 phones having these type of branch predictors as far back as 2016 and AMD CPUs having perceptron based branch predictors as far back as 2011. It was not officially known if Intel also uses neural networks in their chips, but the author of that paper "strongly believes" it does and I concur that it's unlikely they don't given that Samsung, Oracle, IBM, ARM and AMD all seem to use them.

AMD Zen 2 CPU and IBM z15 mainframe claims to be using TAGE branch predictor -- but this doesn't say much. The basic TAGE is quite simple (see [1]), but actual implementation likely includes loop predictor, statistical corrector predictor, perceptron hashing functions, etc.

To learn more about state of start BP look for Andre Seznec (INRIA/IRISA) and Daniel Jimenez (Texas A&M University) work. They are usually the winners of Championship Branch Prediction [2,3].

[1] https://fuse.wikichip.org/news/2458/a-look-at-the-amd-zen-2-...

[2] https://www.jilp.org/cbp2014/program.html

[3] https://www.jilp.org/cbp2016/program.html

I'm no expert but neural networks are definitely used in some CPUs for branch prediction. See the wikipedia section: https://en.wikipedia.org/wiki/Branch_predictor#Neural_branch....

Seems like the the processor may just gradually be storing the explicit branch pattern at that point in the program? 2000 branches isn't that many if you have tens of megabytes of cache on the die.

Reply on news.ycombinator.com