Predicated Analysis for Cost-Effective Run-Time Parallelization

今天的编译器受到了严重的限制，因为它们是静态的，基本的优化决策仅基于编译时可证明的知识。特别是，编译器只生成计算的单个优化版本。因此，每次优化都是保守地执行的——也就是说，只有在保证对所有可能的输入和通过程序采取的控制流路径都是安全的（并预期是有利可图的）时。这个项目将开发一种新的、更动态的优化模型，称为预测优化，通过这种模型，编译器战略性地乐观地转换一些代码段，产生计算的多个版本，每个版本的执行都由运行时测试保护，以保证所应用优化的安全性（或建议盈利能力）。预测优化提供了几个优点：(1)它可以使优化只对程序的某些输入有效；(2)它可以使优化对所有输入有效，但在编译时分析证明安全性是不可行的；(3)它可以使优化只对通过程序采取的某些控制流路径有效；并且，(4)它可以确定取决于运行时环境值或过于复杂而无法静态访问的优化的盈利能力。本项目将开发一种通用的预测优化方法，并应用该方法来提高自动并行化的有效性。

Compilers today are severely limited because they are static, basic optimization decisions solely on knowledge provable at compile time. In particular, compilers produce only a single optimized version of a computation. Thus, each optimization is performed conservatively- i.e., only when it is guaranteed to be safe (and expected to be profitable) for all possible inputs and control flow paths taken through a program. This project will develop a new, more dynamic model of optimization called predicated optimization, whereby the compiler strategically transforms some code segments optimistically, producing multiple versions of a computation with each version's execution guarded by a run-time test guaranteeing safety (or suggesting profitability) of the optimizations applied. Predicated optimization offers several advantages: (1) it can enable optimizations only valid for some inputs to a program; (2) it can enable optimizations valid for all inputs, but where compile-time analysis to prove safety is infeasible; (3) it can enable optimizations only valid for certain control flow paths taken through a program; and, (4) it can determine profitability of an optimization that either depends on values from the run-time environment or is too complex to access statically. This project will develop a general approach to predicated optimization and apply this approach to improve the effectiveness of automatic parallelization.