Predicated array data-flow analysis for run-time parallelization
Sungdo Moon, Mary W. Hall, Brian R. Murphy · International Conference on Supercomputing · 1998
This paper presents a new analysis for parallelizing compilers called predicated array data-flow analysis, whereby array dataflow analysis for parallelization and privatization is extended to associate predicates with data-flow values.These predicates can be used to derive conditions under which dependences can be eliminated or privatization is possible.These conditions, which can consist of arbitrary program statements, can be used both to enhance compile-time analysis and to introduce run-time tests that guard safe execution of a parallelized version of a computation.We have implemented predicated array data-llow analysis in the Stanford SUIF compiler.We describe features of the implementation and present experimental results that demonstrate this analysis improves the performance of three programs from the SPECgSFP benchmark suite.
Cited by 30 works. doi:10.1145/277830.277874 Open-access PDF
Authors
References
- Systematic design of program analysis frameworks
- Constant propagation with conditional branches
- Run-time parallelization and scheduling of loops
- Eliminating false data dependences using the Omega test
- The LRPD test
- Extending typestate checking using conditional liveness analysis
- Symbolic Analysis for Parallelizing Compilers
- Parallelizing Compiler Techniques Based on Linear Inequalities
- Symbolic analysis techniques for effective automatic parallelization
- Interprocedural analysis for parallelization