The LRPD Test: Speculative Run-Time Parallelization of Loops With Privatization and Reduction Parallelization

Current parallelizing compilers cannot identify a significant frac-tion of parallelizable loops because they have complex or statically insufficiently defined access patterns. As parallelizable loops arise frequently in practice, we advocate a novel framework for their identification: speculatively execute the loop as a doall, and ap-ply a fully parallel data dependence test to determine if it had any cross–iteration dependences; if the test fails, then the loop is re– executed serially. Since, from our experience, a significant amount of the available parallelism in Fortran programs can be exploited by loops transformed through privatization and reduction paralleliza-tion, our methods can speculatively apply these transformations and then check their validity at run–time. Another important contribu-tion of this paper is a novel method for reduction recognition which goes beyond syntactic pattern matching: it detects at run–time if the values stored in an array participate in a reduction operation, even if they are transferred through private variables and/or are affected by statically unpredictable control flow. We present experimental results on loops from the PERFECT Benchmarks which substanti-ate our claim that these techniques can yield significant speedups which are often superior to those obtainable by inspector/executor methods.