Evaluation of predicated array data-flow analysis for automatic parallelization

This paper presents an evaluation of a new analysis for parallelizing compi lers called predicated array data-flour analysis. This analysis extends arr ay data-flow analysis for parallelization and privatization to associate pr edicates with data-flow values. These predicates can be used to derive cond itions under which dependences can be eliminated or privatization is possib le. These conditions can be used both to enhance compile-time analysis and to introduce run-time tests that guard safe execution of a parallelized ver sion of a computation. As compared to previous work that combines predicates with array data-flow analysis, our approach is distinguished by two features: (1) it derives low -cost, run-time parallelization tests; and, (2) it incorporates predicate e mbedding and predicate extraction, which translate between the domain of pr edicates and data-flow values to derive more precise analysis results. We p resent extensive experimental results across three benchmark suites and one additional program, demonstrating that predicated array data-flow analysis parallelizes more than 40% of the remaining inherently parallel loops left unparallelized by the SUIF compiler and that it yields improved speedups f or: 5 programs.