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.