Combining Compile‐Time and Run‐Time Parallelization
Sungdo Moon, Byoungro So, Mary W. Hall · Scientific Programming · 1999
This paper demonstrates 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. We support this claim with the results of an experiment that measures the safety of parallelization at run time for loops left unparallelized by the Stanford SUIF compiler’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 technique that can be used to parallelize most of these remaining 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 predicates with array data‐flow values. 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.
Cited by 1 works. doi:10.1155/1999/490628 Open-access PDF
Authors
References
- Systematic design of program analysis frameworks
- Constant propagation with conditional branches
- Maximizing multiprocessor performance with the SUIF compiler
- Parallel programming with Polaris
- Run-time parallelization and scheduling of loops
- Improving data-flow analysis with path profiles
- Automatic Array Privatization
- The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization
- Eliminating false data dependences using the Omega test
- The LRPD test