Predicated Analysis for Cost-Effective Run-Time Parallelization

具有成本效益的运行时并行化的预测分析

• 批准号: 9721368
• 负责人: Mary Hall
• 金额: $ 27.17万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1998
• 资助国家: 美国
• 起止时间: 1998-12-01 至 2002-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9721368&HistoricalAwards=false
• 关键词: Predicated; Analysis; Cost; Effective; Run

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.

今天的编译器受到了严重的限制，因为它们是静态的，基本的优化决策，完全基于编译时可证明的知识。 特别是，编译器只产生计算的单个优化版本。 因此，每个优化都是保守地执行的，即，只有当它保证对所有可能的输入和通过程序采取的控制流路径是安全的（并且预期是有利的）时。 该项目将开发一种新的，更动态的优化模型，称为预测优化，编译器策略性地优化转换一些代码段，产生多个版本的计算，每个版本的执行由运行时测试保护，保证应用优化的安全性（或建议盈利能力）。 谓词优化提供了几个优点：（1）它可以使优化只对程序的某些输入有效;（2）它可以使优化对所有输入有效，但在编译时分析证明安全性是不可行的;（3）它可以使优化只对通过程序的某些控制流路径有效;以及（4）它可以确定取决于来自运行时环境的值或者太复杂而不能静态访问的优化的收益率。 本计画将发展一个一般性的预测最佳化方法，并应用此方法来改善自动平行化的效能。