| In this dissertation, we investigate how good today's parallelizing compilers are, what opportunities remain to improve them, and, what technology is needed to exploit the remaining opportunities. To answer these questions, we perform experiments that measure the safety of parallelization at run time for loops left unparallelized by the Stanford SUIF compiler's automatic parallelization system. The experimental results demonstrate that significant improvements to automatic parallelization technology require that existing systems be extended in two ways: (1) they must combine high-quality compile-time analysis with low-cost run-time testing; and, (2) they must take control flow into account during analysis.; In order to exploit these remaining opportunities, we have developed a new compile-time analysis technique that can be used to parallelize most of these remaining parallelizable loops, This technique is designed to not only improve the results of compile-time parallelization, but also to produce low-cost, directed run-time tests that allow the system to defer binding of parallelization until run-time when safety cannot be proven statically, We call this approach predicated array data-flow analysis. We augment array data-flow analysis, which the compiler uses to identify independent and privatizable arrays, by associating with each array data-flow value a predicate. Predicated array data-flow analysis allows the compiler to derive “optimistic” data-flow values guarded by predicates; these predicates can be used to derive a run-time test guaranteeing the safety of parallelization.; We demonstrate the effectiveness of predicated data-flow analysis by implementing it in the Stanford SUIF compiler and performing experiments on three benchmark suites and one additional program, Experimental results with a prototype implementation show that predicated array data-flow analysis is promising at finding additional parallel loops, as it parallelizes more than 40% of the remaining inherently parallel loops left unparallelized by the SUIF compiler, We demonstrate improved speedups with negligible run-time overhead for 5 programs among 6 programs in our benchmark suite where significant speedup improvement is possible. |
