3 ms·

Whenever one sees "heuristic", I think "Bitter Lesson" [1] and how can we apply brute force computation to the problem. It would seem like there is still ample

Whenever one sees "heuristic", I think "Bitter Lesson" [1] and how can we apply brute force computation to the problem. It would seem like there is still ample space to study the application of neural networks to register allocation. [2] They already gave pretty good results to branch prediction. [3] What are your thoughts on the application of NN for RA and how would you structure the training set? [1] http://incompleteideas.net/IncIdeas/BitterLesson.html http://incompleteideas.net/IncIdeas/BitterLesson.html [2] https://www.semanticscholar.org/paper/Real-time-physical-register-file-allocation-with-Wang-Lin/694db27cb6a444f40a982b1e187224987eb280e6 https://www.semanticscholar.org/paper/Real-time-physical-reg... I haven't read the paper, just found in a quick search. [3] https://cseweb.ucsd.edu/~atsmith/rnn_branch.pdf https://cseweb.ucsd.edu/~atsmith/rnn_branch.pdf

aseipp 4y ago
The second paper you are referencing is not quite what you think it is. It is the application of a neural network to the processor itself, to assist in performing physical register renaming, at runtime, in order to achieve out-of-order execution. This is a very different problem than a compiler's register allocator (for one you're dealing with hundreds of potential registers vs like, 16-30.) On that topic, NN for branch prediction are, in some sense, nothing new; perceptron and perceptron-based designs have existed for at least 20 years. But I'm not aware of anything concrete or specific in current BP designs as of recently (beyond marketing hype) but I haven't kept up with it; maybe some variation of TAGE with model-assistance is out there, but I'm not sure. I do not know what a training set or neural network model for performing register allocation on real-world programs would look like at this moment.
- sitkack 4y ago
  The second paper is more of an existence proof that folks are thinking about the problem. From a high level, register file selection and register renaming is similar problem to register allocation in a compiler. The paper itself is dealing with hundreds of virtual registers and how to map them to renamer. TAGE is what I was thinking of [1,2]. Thanks for the reminder. I found some relevant research in neural register allocation, "2020 LLVM in HPC Workshop: Deep Learning-based Approx. Graph-Coloring for Register Allocation" https://www.youtube.com/watch?v=4FW7iznzIoE https://www.youtube.com/watch?v=4FW7iznzIoE There is also some nascent work on applying neural techniques to constraint optimization problems. [1] https://www.semanticscholar.org/paper/A-case-for-(partially)-TAgged-GEometric-history-Seznec-Michaud/a56ecaf2a44259478acf55d1865ed570d80c921b https://www.semanticscholar.org/paper/A-case-for-(partially)... [2] https://www.semanticscholar.org/search?q=TAGE%20branch%20predictor&sort=relevance https://www.semanticscholar.org/search?q=TAGE%20branch%20pre...

aseipp 4y ago

The second paper you are referencing is not quite what you think it is. It is the application of a neural network to the processor itself, to assist in performing physical register renaming, at runtime, in order to achieve out-of-order execution. This is a very different problem than a compiler's register allocator (for one you're dealing with hundreds of potential registers vs like, 16-30.) On that topic, NN for branch prediction are, in some sense, nothing new; perceptron and perceptron-based designs have existed for at least 20 years. But I'm not aware of anything concrete or specific in current BP designs as of recently (beyond marketing hype) but I haven't kept up with it; maybe some variation of TAGE with model-assistance is out there, but I'm not sure. I do not know what a training set or neural network model for performing register allocation on real-world programs would look like at this moment.

sitkack 4y ago
The second paper is more of an existence proof that folks are thinking about the problem. From a high level, register file selection and register renaming is similar problem to register allocation in a compiler. The paper itself is dealing with hundreds of virtual registers and how to map them to renamer. TAGE is what I was thinking of [1,2]. Thanks for the reminder. I found some relevant research in neural register allocation, "2020 LLVM in HPC Workshop: Deep Learning-based Approx. Graph-Coloring for Register Allocation" https://www.youtube.com/watch?v=4FW7iznzIoE https://www.youtube.com/watch?v=4FW7iznzIoE There is also some nascent work on applying neural techniques to constraint optimization problems. [1] https://www.semanticscholar.org/paper/A-case-for-(partially)-TAgged-GEometric-history-Seznec-Michaud/a56ecaf2a44259478acf55d1865ed570d80c921b https://www.semanticscholar.org/paper/A-case-for-(partially)... [2] https://www.semanticscholar.org/search?q=TAGE%20branch%20predictor&sort=relevance https://www.semanticscholar.org/search?q=TAGE%20branch%20pre...