Dynamic Branch Prediction with Perceptrons (2000) [pdf]

(The guy who posted the link is Dan Luu who used to work for a company that made x86 CPUs. His blog is worth looking at. He also used to work for Twitter -- but his predictions about the Doom and Disaster after Musk's takeover hasn't panned out at all. Good at some things (CPU architecture and blog posts). Not so good at Elon Musk predictions ;) )

--- Edit: put in the missing "a". My fingers and my brain don't always agree on what to write.

Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]

#6

Post by bjourne » Wed, May 10, 2023, 12:50 PM UTC

Modern 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.

Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]

#7

Post by albertzeyer » Wed, May 10, 2023, 12:56 PM UTC

bjourne wrote: post #6

Modern 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.

But is it really much more complicated? It looks very simple to me. Maybe actually even simpler than such state machine?

Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]

#8

Post by thesz » Wed, May 10, 2023, 1:15 PM UTC

albertzeyer wrote: post #7

bjourne wrote: post #6

Modern 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.

But is it really much more complicated? It looks very simple to me. Maybe actually even simpler than such state machine?

There are several multipliers and adders (possible, floating point ones), a register file for perceptron weights and perceptron selection logic. The scheme also need to keep information somewhere for training - the decision and backpropagation stimulus are separeted in time.

So the circuitry is complicated despite superficial simplicity of the model.

Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]

#9

Post by pfdietz » Wed, May 10, 2023, 1:31 PM UTC

bjourne wrote: post #6

Modern 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.

But what's the impact of those 5% misses?

Re: Dynamic Branch Prediction with Perceptrons (2000) [pdf]

#10

Post by kordlessagain » Wed, May 10, 2023, 1:51 PM UTC

Using my DocGPT project to process this...

system> What are the microarchitectural tricks that allow prediction to take place in one clock cycle?

bot> The microarchitectural tricks include using the branch address to hash and select a perceptron from the table, calculating the dot product of the perceptron and the global history register, using the training algorithm to update the weights in the perceptron, and writing the updated perceptron back to the table.