5 ms·

Dynamic Branch Prediction with Perceptrons (2000) [pdf]

59 points by luu 3y ago

GaggiX 3y ago
You should add "(2000)"
jacknews 3y ago
It's an interesting idea. Did this go anywhere? Is it worth revisiting in 2023?
- w1nk 3y ago
  Yes, it did: https://chasethedevil.github.io/post/the_neural_network_in_your_cpu/ https://chasethedevil.github.io/post/the_neural_network_in_y...
- peterfirefly 3y ago
  That is a* very, very important paper. The answer is yes. (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.
  - jackmott42 3y ago
    [flagged]
- ftxbro 3y ago
  Maybe or maybe not, but they manually put it onto the front page using https://news.ycombinator.com/pool https://news.ycombinator.com/pool
bjourne 3y ago
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.
- albertzeyer 3y ago
  But is it really much more complicated? It looks very simple to me. Maybe actually even simpler than such state machine?
  - thesz 3y ago
    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.
    - isotypic 3y ago
      The version in the paper only is ever multiplying by 1 or -1, so you do not need a full multiplier circuit. The weights are also stored as signed integers, not floats, so no complicated floating point circuity. I am not sure what current state of the art is, but considering the cost of multipliers/floating point circuity I would be surprised if it changed to those if signed integers work. All branch predictors need some way of storing their state and selection logic, and the way a perceptron branch predictor stores its data is just a big table indexed by some hash of the program counter of the branch, which is pretty standard for branch predictors. Also, all branch predictors have a sort of "backpropogation" in that pipelined processors produce the actual result of the branch (possibly many) cycles later, so this also is not as much of a factor. Since the training is a function of the weights you do not need to store extra data beyond the threshold, but that is already being computed as the prediction anyways.
- pfdietz 3y ago
kordlessagain 3y ago
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.
gharzol 3y ago
I believe this was (is?) used in the Samsung Exynos CPUs: https://people.engr.tamu.edu/djimenez/pdfs/exynos_isca2020.pdf https://people.engr.tamu.edu/djimenez/pdfs/exynos_isca2020.p...
delta_p_delta_x 3y ago
Modern CPUs use TAGE-like[1] and Perceptron-based branch predictors, achieving a 99.7% prediction accuracy. Zen 2 in particular uses TAGE[2]. I recall implementing one in software in a computer architectures class; it was pretty gnarly but the prediction accuracy (and therefore performance) compared to a simple two-bit saturating counter is immense. [1]: https://doi.org/10.1145/3226098 https://doi.org/10.1145/3226098 [2]: https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Branch_Prediction_Unit https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Br...
Tommstein 3y ago
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.
Dwedit 3y ago
Did they ever figure out how to look at the value of a loop counter and use that to predict the branch?
- Taniwha 3y ago
  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

59 points by luu 3y ago

GaggiX 3y ago

You should add "(2000)"

jacknews 3y ago

It's an interesting idea. Did this go anywhere? Is it worth revisiting in 2023?

w1nk 3y ago
Yes, it did: https://chasethedevil.github.io/post/the_neural_network_in_your_cpu/ https://chasethedevil.github.io/post/the_neural_network_in_y...
peterfirefly 3y ago
That is a* very, very important paper. The answer is yes. (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.
- jackmott42 3y ago
  [flagged]
ftxbro 3y ago
Maybe or maybe not, but they manually put it onto the front page using https://news.ycombinator.com/pool https://news.ycombinator.com/pool

bjourne 3y ago

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.

albertzeyer 3y ago
But is it really much more complicated? It looks very simple to me. Maybe actually even simpler than such state machine?
- thesz 3y ago
  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.
  - isotypic 3y ago
    The version in the paper only is ever multiplying by 1 or -1, so you do not need a full multiplier circuit. The weights are also stored as signed integers, not floats, so no complicated floating point circuity. I am not sure what current state of the art is, but considering the cost of multipliers/floating point circuity I would be surprised if it changed to those if signed integers work. All branch predictors need some way of storing their state and selection logic, and the way a perceptron branch predictor stores its data is just a big table indexed by some hash of the program counter of the branch, which is pretty standard for branch predictors. Also, all branch predictors have a sort of "backpropogation" in that pipelined processors produce the actual result of the branch (possibly many) cycles later, so this also is not as much of a factor. Since the training is a function of the weights you do not need to store extra data beyond the threshold, but that is already being computed as the prediction anyways.
pfdietz 3y ago

kordlessagain 3y ago

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.

gharzol 3y ago

I believe this was (is?) used in the Samsung Exynos CPUs: https://people.engr.tamu.edu/djimenez/pdfs/exynos_isca2020.pdf https://people.engr.tamu.edu/djimenez/pdfs/exynos_isca2020.p...

delta_p_delta_x 3y ago

Modern CPUs use TAGE-like[1] and Perceptron-based branch predictors, achieving a 99.7% prediction accuracy. Zen 2 in particular uses TAGE[2]. I recall implementing one in software in a computer architectures class; it was pretty gnarly but the prediction accuracy (and therefore performance) compared to a simple two-bit saturating counter is immense. [1]: https://doi.org/10.1145/3226098 https://doi.org/10.1145/3226098 [2]: https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Branch_Prediction_Unit https://en.wikichip.org/wiki/amd/microarchitectures/zen_2#Br...

Tommstein 3y ago

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.

Dwedit 3y ago

Did they ever figure out how to look at the value of a loop counter and use that to predict the branch?

Taniwha 3y ago
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