Automatically simplifying reductions

Abstract

When developing software from a mathematical model, the efficiency of the model and the code which implements it both have significant impacts on the runtime performance of the software. The reduction simplification transformation can be used to automatically provide these benefits, improving the runtime performance of programs while simultaneously making it easier to specify a program. This work, which was done in collaboration with Louis Narmour based on a partial implementation by Tomofumi Yuki, tackles the theoretical gaps in this transformation and provides the first complete, automatic implementation of reduction simplification in a compiler. We demonstrate its effectiveness using the real-world problem of RNA secondary structure prediction. Our compiler automatically rediscovers the known optimization for this problem, which required significant human effort to initially discover and implement. In addition, our compiler discovers several previously unknown optimizations for this problem and generates a C implementation of all optimized programs.