Virtually all software today is written by a combination of man and machine. Programmers write programs in programming languages that cannot be executed directly---these languages are designed to make the task of programming easier but cannot actually be run on a computer without a second step, where the human-written program is translated into a language that the machine can execute. Many changes to the program are made during this translation and especially important are optimizations that improve the performance of the final program on the hardware.
Optimizing programs is a very complex process as there are many tradeoffs to be made in how to best use the limited resources of the target architecture. Traditionally this large problem is solved by breaking it into many small sub-problems, each of which focuses on a particular class of optimizations. In this project a very different alternative will be explored, using randomized search techniques to simultaneously consider all of the factors that go into producing the fastest possible code. Preliminary results have shown this approach can match or outperform production compilers for important short kernels; a focus of this research will be to try to scale these results up to full programs. The intellectual merit of this work is to reconsider how to perform compiler optimizations in light of the dramatic advances in computational power over the last several decades, a period in which the basic structure of compilers has hardly changed. The broader impact will be to demonstrate novel methods based on stochastic search, for producing, with a significant degree of automation, consistently much faster low-level code than today?s compilers. Thus, instead of compiler projects requiring years to produce reliable and high performance code for new architectures, stochastic optimizers that perform even better and with higher assurance can be built much more quickly by smaller teams of people. The techniques that will be developed will also be widely disseminated through massively online course portals.
