Predicated Analysis for Cost-Effective Run-Time Parallelization

点击翻译按钮获取中文摘要

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.