CPA-CPL: The Reduction Simplification Engine

Colorado State University, Fort Collins CO

Investigators

Abstract

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.