CPA-CPL: The Reduction Simplification Engine

提高程序员的工作效率是一个关键的挑战，特别是在多核和多核处理器出现的情况下。高级数学公式是程序的一大类计算密集型和数据密集型部分的声明性规范。当用户被允许指定称为“约简”的集合运算时，此类方程的可表现性大大增强：应用于值集合的结合和交换运算符。这类等式程序的另一个共同特征是“重用”：在集合中的不同点上，(重新)计算或使用相同的中间值。当等式程序同时具有缩减和重用时，某些非常有效的程序优化是可能的。这些优化产生了计算复杂度更低的新方程(例如，可以将二次时间方程转换为线性复杂度的方程)。本项目研究如何以自动和优化的方式执行这些简化。PI将开发和部署一种名为简化引擎(RSE)的工具，该工具可以实现此类优化技术。传统的编译器优化只是寻求几个百分点的性能提升，充其量是一个小的、恒定的因素。另一方面，RSE执行的优化具有明显更多的好处，因为它们降低了程序的渐近复杂性。

Improving programmer productivity is a crucial challenge, especially with the emergence of multi- and many-core processors. High level mathematical equations serve as declarative specifications for a large class of compute- and data- intensive parts of programs. The expressivity of such equations is greatly enhanced when users are allowed to specify collective operations called "reductions:" associative and commutative operators applied to sets of values. Another common feature of such equational programs is "reuse:" at different points in a set, the same intermediate value is (re)- computed or used. Certain extremely effective program optimizations are possible when equational programs have both reductions and reuse. These optimizations yield new equations with lower computational complexity (e.g., a quadratic time equation can be transformed into one with linear complexity). This project investigates how to perform these simplifications automatically and optimally. The PIs will develop and deploy a tool called Reduction Simplification Engine (RSE) that implements such optimizations techniques. Traditional compiler optimizations simply seek a few percentage points of performance gains, at best a small, constant factor. On the other hand, the optimizations performed by the RSE have significantly more benefits since they reduce the asymptotic complexity of the program.