A General and Powerful Method for Program Optimization

点击翻译按钮获取中文摘要

This project studies a general and powerful method for program optimization. This method is based on incrementalization, which allows repeated computations on slightly changing inputs to be performed efficiently by updating their values incrementally from one computation to the next. Since all non-trivial computations proceed in an iterative fashion, which requires repeated updates of program states, incrementalization underlies essentially all loop optimizations. This project focuses on an important application of incrementalization, namely, loop optimization for aggregate computations on arrays. This optimization can produce drastic speedups of programs for problems in image processing, computational geometry, computer graphics, multimedia, matrix computation, etc. The method captures aggregate array computations in loop bodies and incrementally updates their results over iterations. Part of the analysis is reduced to symbolic simplification of constraints on loop variables and array subscripts. Analytical and experimental results both show drastic speedups compared to previous techniques. Work specifically planned for this project includes: refining and extending the techniques and algorithms, implementing the algorithms, analyzing the performance of the optimization algorithm and the optimized programs, and developing models for the time and space complexity and data locality of the programs that will enable us to tune the optimizations.