3 ms·

Branch prediction strategies can be learned, just like any other model. I could certainly see something like this outperforming the huge bag of hand-tuned optim

by gcr 10y ago

Branch prediction strategies can be learned, just like any other model. I could certainly see something like this outperforming the huge bag of hand-tuned optimization strategies for branch prediction anyway. It could save some silicon. Even a simple dot product can be called a "neural network," albeit a small uninteresting one. Your features could be (say) the state of cache, the number of jumps, the number of recent stalls / stack size / returns, and so on. Put them into a 10-dimensional vector or whatever, take the dot product between that and a set of 10 learned weights, and preload the branch if the result is above some threshold. Even a simple model could perhaps work really well here. Of course it's not like they have some deep learning convolutional net running on the program input. I also bet the weights are set at the factory so it's not "learning" anything.

medains 10y ago
Nothing in the article suggests that it's learning - so I suspect that the weights are indeed set in the factory. Learning on the fly would consume much more power as it back-propagates, so doesn't really make much sense as the potential performance gain would be marginal and would probably cause a performance hit when switching to a different process or thread.
- pawadu 10y ago
  But if it is not learning, can you really call it NN?
  - chas 10y ago
    Yes. Most neural net applications separate training and inference so that once the net is in production it doesn't change, though it might be replaced with a new net rather frequently depending on how much the distribution of data it's operating on changes over time.
    - pawadu 10y ago
      not an expert on this, but wouldn't what you mention be adaptive control rather than ANN?
    - FungalRaincloud 10y ago
      To add to that, the backpropagation doesn't have to happen on device - they could, for instance, record statistics from a sampling of the cellphones in use, backprop on a server, then push an update to the weights in the next over the air update. The statistics would potentially be much cheaper than actually training the network.
- drothlis 10y ago
  The article links to a paper[1] that talks about online learning: > The perceptrons are trained by an algorithm that increments a weight when the branch outcome agrees with the weight’s correlation and decrements the weight otherwise. A "perceptron" seems to be a single linear function, akin to a single neuron in a neural network. So complex learning algorithms like back-propagation don't apply here. The complete process, from the paper, is: > 1. The branch address is hashed to produce an index "i" into the table of perceptrons. > 2. The "i"th perceptron is loaded from the table into a vector register "P" of weights. > 3. The value of "y" is computed as the dot product of "P" and the global history register. [This is a shift register containing values of -1 or 1 for the last N branches seen. -1 means not taken, and 1 means taken.] > 4. The branch is predicted "not taken" when "y" is negative, or "taken" otherwise. > 5. Once the actual outcome of the branch becomes known, the training algorithm uses this outcome and the value of "y" to update the weights in "P". > 6. "P" is written back to the "i"th entry in the table. The article says that AMD's microarchitecture uses a hashed perceptron system in its branch prediction. So, from the above, it seems that "hashed" means that you hash the branch address to pick which perceptron (model) to use, and "perceptron" is just a dot product. (Actually the wikipedia article[2] suggests that the name "perceptron" refers to the training algorithm, i.e. how you update the weights.) [1]: Daniel A. Jiménez and Calvin Lin. 2002. Neural Methods for Dynamic Branch Prediction. https://www.cs.utexas.edu/~lin/papers/tocs02.pdf https://www.cs.utexas.edu/~lin/papers/tocs02.pdf [2]: https://en.wikipedia.org/wiki/Perceptron https://en.wikipedia.org/wiki/Perceptron

by gcr 10y ago

medains 10y ago

Nothing in the article suggests that it's learning - so I suspect that the weights are indeed set in the factory. Learning on the fly would consume much more power as it back-propagates, so doesn't really make much sense as the potential performance gain would be marginal and would probably cause a performance hit when switching to a different process or thread.

pawadu 10y ago
But if it is not learning, can you really call it NN?
- chas 10y ago
  Yes. Most neural net applications separate training and inference so that once the net is in production it doesn't change, though it might be replaced with a new net rather frequently depending on how much the distribution of data it's operating on changes over time.
  - pawadu 10y ago
    not an expert on this, but wouldn't what you mention be adaptive control rather than ANN?
  - FungalRaincloud 10y ago
    To add to that, the backpropagation doesn't have to happen on device - they could, for instance, record statistics from a sampling of the cellphones in use, backprop on a server, then push an update to the weights in the next over the air update. The statistics would potentially be much cheaper than actually training the network.
drothlis 10y ago
The article links to a paper[1] that talks about online learning: > The perceptrons are trained by an algorithm that increments a weight when the branch outcome agrees with the weight’s correlation and decrements the weight otherwise. A "perceptron" seems to be a single linear function, akin to a single neuron in a neural network. So complex learning algorithms like back-propagation don't apply here. The complete process, from the paper, is: > 1. The branch address is hashed to produce an index "i" into the table of perceptrons. > 2. The "i"th perceptron is loaded from the table into a vector register "P" of weights. > 3. The value of "y" is computed as the dot product of "P" and the global history register. [This is a shift register containing values of -1 or 1 for the last N branches seen. -1 means not taken, and 1 means taken.] > 4. The branch is predicted "not taken" when "y" is negative, or "taken" otherwise. > 5. Once the actual outcome of the branch becomes known, the training algorithm uses this outcome and the value of "y" to update the weights in "P". > 6. "P" is written back to the "i"th entry in the table. The article says that AMD's microarchitecture uses a hashed perceptron system in its branch prediction. So, from the above, it seems that "hashed" means that you hash the branch address to pick which perceptron (model) to use, and "perceptron" is just a dot product. (Actually the wikipedia article[2] suggests that the name "perceptron" refers to the training algorithm, i.e. how you update the weights.) [1]: Daniel A. Jiménez and Calvin Lin. 2002. Neural Methods for Dynamic Branch Prediction. https://www.cs.utexas.edu/~lin/papers/tocs02.pdf https://www.cs.utexas.edu/~lin/papers/tocs02.pdf [2]: https://en.wikipedia.org/wiki/Perceptron https://en.wikipedia.org/wiki/Perceptron