SHF: Small: Simplifying Reductions

这个项目开发了编译时技术和一个软件工具(称为归约简化引擎，RSE)，用于优化带有归约(应用于数据集合的联合运算，通常是交换运算)的等式程序。通过使用这些技术和工具，可以生成比原始规范更低的渐近复杂性的程序。这样的复杂性降低是编译中一个雄心勃勃、几乎闻所未闻的目标：大多数编译器寻求持续的因子收益，通常是几个百分点。在这个项目中开发的技术建立在PI对一种被称为“多面体模型”的形式主义的20多年研究的基础上。目前这项工作的主要新奇之处在于，除了多面体技术之外，还使用了诸如幂等和分配性等代数性质来增强所执行的分析。

This project develops compile time techniques and a software tool (called the Reduction Simplification Engine, RSE) for optimization of equational programs with reductions (associative, and usually commutative, operations applied to collections of data). By using these techniques and tools it is possible to generate programs with lower asymptotic complexity than the original specification. Such complexity reduction is an ambitious, almost unheard of, goal in compilation: most compilers seek constant factor gains, usually a few percentage points. The techniques developed in this project build on more than twenty years of research by the PI on a formalism called the "polyhedral model." The main novelty of the current effort is that in addition to polyhedral techniques, algebraic properties such as idempotency and distributivity are also used to augment the analyses performed.