Learning to Superoptimize Programs
arxiv.org
Learning to Superoptimize Programs
1–10 of 28 posts
Re: Learning to Superoptimize Programs
#2TL;DNR how it differs from usual performance optimization?
Re: Learning to Superoptimize Programs
#3TL;DNR how it differs from usual performance optimization?
It is entirely automated, it can be thought of kind of like googles alphago. A neural net is used to guide monte carlo search, though it is working on the space of programs and optimizing running time. Instead of using known rules, it can learn its own optimization rules for software.
Re: Learning to Superoptimize Programs
#4This article uses a very contrived data set (bit manipulation), and also a "synthetically generated dataset", which would never occur in real life applications. This means that the results are unreliable and need to be repeated on something more realisic, or at least on programs that are uses by peole in some context (spec2000, spec2006). Moreover, the authors never compare the performance with that of llvm or gcc on different levels of optimisations, or at least do not mention any of that.
Re: Learning to Superoptimize Programs
#5This article uses a very contrived data set (bit manipulation), and also a "synthetically generated dataset", which would never occur in real life applications. This means that the results are unreliable and need to be repeated on something more realisic, or at least on programs that are uses by peole in some context (spec2000, spec2006). Moreover, the authors never compare the performance with that of llvm or gcc on…
The authors of the original Stochastic superoptimization paper performed some comparison with the outputs of gcc. You can find their results in this paper: https://raw.githubusercontent.com/StanfordPL/stoke/develop/d...
This is on the same type of dataset, as admittedly, these methods still don't scale all that well to extremely large programs.
Re: Learning to Superoptimize Programs
#6TL;DNR how it differs from usual performance optimization?
It is entirely automated, it can be thought of kind of like googles alphago. A neural net is used to guide monte carlo search, though it is working on the space of programs and optimizing running time. Instead of using known rules, it can learn its own optimization rules for software.
Note that this uses Markov chain Monte Carlo (MCMC) sampling rather than the Monte Carlo tree search (MCTS) of AlphaGo, although the latter might also be interesting to try.
I suppose one disadvantage of naive MCTS is that if it made a supoptimal decision near the root, correcting that mistake would require relearning the rest of the program from scratch.
Maybe there could be some bidirectional variant of MCTS, where you search from both the beginning and the end of the program and join the two fragments in the middle. If the two trees work independently, can they still learn to find the optimal solution?
Re: Learning to Superoptimize Programs
#7This work should be read in context of prior work, STOKE: http://stoke.stanford.edu/
This work outperforms STOKE, and STOKE outperformed existing methods including GCC, LLVM, ICC, traditional superoptimization, expert human, etc. That's why comparison with existing methods are omitted.
This work is also limited to Hacker's Delight and automatically generated programs, but so was STOKE. But STOKE readily extended to computational kernels in libm, BLAS, OpenSSL, ray tracer, computational fluid dynamics, etc. You can read about them on the link above. The next step would be applying the improvements to other STOKE tasks and more.
STOKE is an open source.
Re: Learning to Superoptimize Programs
#8Where is the source? It's not science until you can reproduce their result.
Re: Learning to Superoptimize Programs
#9Even if this was useful, it presumes the ability to prove a application correct while modifying it. This would only be doable in very limited circumstances not general purpose applications.
Re: Learning to Superoptimize Programs
#10Even if this was useful, it presumes the ability to prove a application correct while modifying it. This would only be doable in very limited circumstances not general purpose applications.
(edited to add: Note that superoptimization isn't something you do to a whole program, it's more a thing you do to speed-critical sections of a larger program, ideally on the order of a few dozen instructions at most. That alone makes things a lot more tractable)
(edit 2: I've read the relevant papers now, and have corrected some of the stuff below. Corrections are in italics.)
The paper says that this system is built on top of STOKE, which uses the following verification method:
* Generate a random set of test cases
* Each intermediate code block gets instrumented and run on the host processor
* The intermediate code block are given a cost depending on how different their results are from those of the original block on the current test set, as well as an estimate of the running time
* If we get a code block which is correct on all the current test cases, we ask a theorem prover whether it's equivalent to the original one. If it isn't, the theorem prover spits out a test case which proves they're different, and we add that to the test set for future iterations.
Finally, the fastest few provably-correct results are output, where they can be further tested in a full run of the original program they were taken from.
The main room for error here is in the theorem proving step, which requires knowing the full semantics of the host's machine code. But it feels like that part should be share-able between different projects, as it's pretty much independent of the search method used.