I implemented this in a CPU simulator for a computer architecture class back in grad school, and I believe I couldn't reproduce their prediction success rate.
Dynamic Branch Prediction with Perceptrons (2000) [pdf]
21–27 of 27 posts
Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]
#22It's an interesting idea. Did this go anywhere? Is it worth revisiting in 2023?
Maybe or maybe not, but they manually put it onto the front page using https://news.ycombinator.com/pool
Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]
#23Modern branch predictors are based on relatively simple state machines and already have >95% accuracy. Thus, even if machine learning-based predictors can sometimes beat them, it is not clear that they can beat them enough for the much more complicated circuitry they need to be worth it.
With many architectural caches, it's typically valuable to think of miss rate instead. A 5% miss rate is very high if the miss path is 20x the cost of the hit path - misses account for 1/2 of the execution time, so reducing that to 4% gives a 10% improvement in runtime.
Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]
#24Did they ever figure out how to look at the value of a loop counter and use that to predict the branch?
Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]
#25Did they ever figure out how to look at the value of a loop counter and use that to predict the branch?
essentially yes, except that on modern CPUs the fetch/decode stages (where the branch predictors live) are so far away (in space and time) from where the loop counters live that it's not practical to connect them directly - instead the front end maintains history bitmaps of recent branch activity (whether branches are taken or not) which in effect contain the history of how many times you've been around a loop
Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]
#26Modern branch predictors are based on relatively simple state machines and already have >95% accuracy. Thus, even if machine learning-based predictors can sometimes beat them, it is not clear that they can beat them enough for the much more complicated circuitry they need to be worth it.
As someone who works on design verification for modern CPUs, this is not true. Most modern CPUs use some form of TAGE branch prediction, if not something more complex.
Well, yes, but the complexity of TAGE is nowhere near the complexity of a modern deep neural network where you essentially have no chance of figuring out how its predictions are made. Branch predictors based on multi-layer networks, RNNs, LSTMs, or networks with more than a handful of neurons is a hot research topic, but has not, to the best of my knowledge, found their way into any modern cpu.
Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]
#27Earlier quoted context omitted.
As someone who works on design verification for modern CPUs, this is not true. Most modern CPUs use some form of TAGE branch prediction, if not something more complex.
Well, yes, but the complexity of TAGE is nowhere near the complexity of a modern deep neural network where you essentially have no chance of figuring out how its predictions are made. Branch predictors based on multi-layer networks, RNNs, LSTMs, or networks with more than a handful of neurons is a hot research topic, but has not, to the best of my knowledge, found their way into any modern cpu.
Yes modern CPUs aren't using neural nets in hardware or anything like that for branch prediction. I was referring to TAGE not being a simple state machine. That makes it sound like modern CPUs are just using a basic two-bit branch predictor.