This paper demonstrates that significant improvements to au- tomatic parallelization technology require that existing sys- tems be extended in two ways. (l ) they must combine high- quality compile-time analysis with low-cost run-time test- ing, and (2) they must take control flow into account dur- ing analysis. We support this claim with the results of an ex- periment that measures the safety of parallelization at run time for loops left unparallelized by the Stanford SUIF com- piler's automatic parallelization system. We present results of measurements on programs from two benchmark suites - Specfp95 and NAS sample benchmarks - which identify inherently parallel loops in these programs that are missed by the compiler. We characterize remaining parallelization opportunities, and find that most of the loops require run- time testing, analysis of control flow, or some combination of the two. We present a new compile-time analysis tech- nique that can be used to parallelize most of these remain- ing loops. This technique is designed to not only improve the results of compile-time parallelization, but also to produce low-cost, directed nin-time tests that allow the system to de- fer binding of parallelization until run-time when safety can- not be proven statically. We call this approach predicated ar- ray data-flow analysis. We augment array data-flow analysis, which the compiler uses to identify independent and privati- zable arrays, by associating predicates with array data-flow values. Predicated array data-flow analysis allows the com- piler to derive “optimistic” data-
展开▼
