SHF: Small: A Composable, Sound Optimization Framework for Loops and Recursion

Purdue University, West Lafayette IN

Investigators

Abstract

Over the last several decades, researchers have developed numerous general frameworks to optimize programs that manipulate matrices, grids, and other "regular" structures by using loops. These optimizations can improve parallelism and performance and hence are critical to developing high-performance software. However, a large class of programs does not use loops but instead uses recursive formulations; these programs are inaccessible to existing general frameworks, and heretofore have only been optimized by ad hoc, narrowly-focused techniques. This means that optimization strategies that work for one program, or one domain, often have to be re-thought and re-implemented for new applications. This project's novelties are developing new program representations, transformation strategies, and analysis techniques to build a new, general framework for optimizing programs that use recursion. This project's impacts will be to open up the power of general optimizations and transformations to a broader range of applications that use recursion, which arise in domains ranging from graphics to data mining to simulation. The general framework developed by the investigator in this project leverages several novel components. First, it captures the schedule of computations of recursive applications using computational constructs called multi-tape finite automata, that allow the framework to distinguish between computations that arise from different parts of the program. Second, it represents transformations of that schedule--which can restructure a computation to improve locality or parallelism--using multi-tape finite transducers. Third, it captures dependences in the computation--which restrict the space of legal computation schedules--using a novel abstraction called witness tuples. Finally, the project develops new, decidable algorithms for determining whether a particular transformation is safe. The work is then extended to identify promising transformation strategies, handle more general types of recursive programs, and generate high-performance code in a more effective manner. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.