SHF: Small: Simplifying Reductions

SHF：小：简化削减

• 批准号: 0917319
• 负责人: Sanjay Rajopadhye
• 金额: $ 46.62万
• 依托单位: Colorado State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2016-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0917319&HistoricalAwards=false
• 关键词: SHF; Small; Simplifying; Reductions

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.

该项目开发编译时技术和软件工具（称为简化引擎，RSE），用于优化具有简化（适用于数据集合的关联，通常是交换运算）的方程程序。 通过使用这些技术和工具，有可能生成比原始规范具有更低渐近复杂度的程序。 这样的复杂性降低是编译中一个雄心勃勃的，几乎闻所未闻的目标：大多数编译器寻求恒定的因子增益，通常是几个百分点。 在这个项目中开发的技术建立在PI二十多年来对一种称为“多面体模型”的形式主义的研究之上。“目前的努力的主要新奇是，除了多面体技术，代数属性，如幂等性和分配性也被用来增强所执行的分析。