3 ms·

Modern branch predictors are based on relatively simple state machines and already have >95% accuracy. Thus, even if machine learning-based predictors can somet

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
But what's the impact of those 5% misses?
- kordlessagain 3y ago
  bot> Querying GPT... bot> A 5% miss rate in branch prediction leads to a 14.7% improvement in misprediction rates on a trace of SPEC2000 benchmarks compared to the gshare predictor. The use of machine learning-based predictors has the potential to improve these results further.
- gpderetta 3y ago
  Huge. I think 95% was table stakes 30 years ago. IIRC the average rate of a good predictor these days is 99.5%.
p_l 3y ago
AMD been using perceptrons in their branch prediction logic since I think K6-2. Some updates to it were big point of "what we did in Zen" presentations when first Ryzen and EPYC CPUs landed.
titzer 3y ago
> relatively simple state machines To be clear, all hardware branch predictors are "relatively simple state machines"; they need storage in the branch prediction tables which must super-fast to access, which means they can only store a few (sometimes dozens, but certainly not hundreds) bits per branch to reach the access latency goal. With input to the predictor encoded as binary, the weights quantized and small and encoded into binary, and the history small, even perceptrons are "relatively simple state machines". After all, their implementation is just going to become some combinatorial logic in the end.
mirker 3y ago
One thing to point out is that the threshold of predictor complexity is dependent on the execution pipeline. A very speculative and deep architecture has a bigger need for better predictors, since it has a massive penalty when there is a misprediction.
artisanspam 3y ago
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.
- bjourne 3y ago
  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.
  - artisanspam 3y ago
    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.
dgacmu 3y ago
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.

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

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

kordlessagain 3y ago
bot> Querying GPT... bot> A 5% miss rate in branch prediction leads to a 14.7% improvement in misprediction rates on a trace of SPEC2000 benchmarks compared to the gshare predictor. The use of machine learning-based predictors has the potential to improve these results further.
gpderetta 3y ago
Huge. I think 95% was table stakes 30 years ago. IIRC the average rate of a good predictor these days is 99.5%.

p_l 3y ago

AMD been using perceptrons in their branch prediction logic since I think K6-2. Some updates to it were big point of "what we did in Zen" presentations when first Ryzen and EPYC CPUs landed.

titzer 3y ago

> relatively simple state machines To be clear, all hardware branch predictors are "relatively simple state machines"; they need storage in the branch prediction tables which must super-fast to access, which means they can only store a few (sometimes dozens, but certainly not hundreds) bits per branch to reach the access latency goal. With input to the predictor encoded as binary, the weights quantized and small and encoded into binary, and the history small, even perceptrons are "relatively simple state machines". After all, their implementation is just going to become some combinatorial logic in the end.

mirker 3y ago

One thing to point out is that the threshold of predictor complexity is dependent on the execution pipeline. A very speculative and deep architecture has a bigger need for better predictors, since it has a massive penalty when there is a misprediction.

artisanspam 3y ago

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.

bjourne 3y ago
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.
- artisanspam 3y ago
  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.

dgacmu 3y ago

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.