6 ms·
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 t
by avian 6y ago
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 https://youtu.be/wlvKAT7SZIQ?t=864
- rowanG077 6y agoI'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_prediction https://en.wikipedia.org/wiki/Branch_predictor#Neural_branch....
- WJW 6y agoModern 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 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 https://patents.google.com/patent/WO2009066063A1/en. There is a wealth of patents and articles if you search for "neural net branch prediction patent".
- heavenlyblue 6y agoCan 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”?
- avian 6y agoAMD 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/12/AMD-Zen-December-2016-Update_Final-For-Distribution-18-980x551.jpeg https://cdn.arstechnica.net/wp-content/uploads/sites/3/2016/...
- bXVsbGVy 6y ago> Anticipate future decisions, pre-load instruction, chose best path through the CPU. This slide is about speculative execution not necessarily about branch prediction.
- brianush1 6y agoPre-loading instructions doesn't mean they're actually getting executed. It sounds like it's talking about branch prediction.
- WJW 6y agoI 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.pdf 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.
- bXVsbGVy 6y agoAMD 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-core/ https://fuse.wikichip.org/news/2458/a-look-at-the-amd-zen-2-... [2] https://www.jilp.org/cbp2014/program.html https://www.jilp.org/cbp2014/program.html [3] https://www.jilp.org/cbp2016/program.html https://www.jilp.org/cbp2016/program.html
- avian 6y agoWell, that's certainly the most surprising thing I've learned today. Thanks.
- e12e 6y agoNow, the natural next question: are there commercial cpus available which branch prediction is Turing complete?
- __alexs 6y agoSeems 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.