Predicated Array Data-Flow Analysis for Run-Time Parallelization

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-flow 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 SPEC95FP benchmark suite. 1 Introduction Automatic parallelization analysis in current practice is severely limited because it is static in nature, basing optimization decisi..