TY - JOUR
T1 - The LRPD Test
T2 - Speculative Run—Time Parallelization of Loops with Privatization and Reduction Parallelization
AU - Rauchwerger, Lawrence
AU - Padua, David
PY - 1995/1/6
Y1 - 1995/1/6
N2 - Current parallelizing compilers cannot identify a significant fraction 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 apply 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 parallelization, our methods can speculatively apply these transformations and then check their validity at run-time. Another important contribution 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 substantiate our claim that these techniques can yield significant speedups which are often superior to those obtainable by inspector/executor methods.
AB - Current parallelizing compilers cannot identify a significant fraction 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 apply 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 parallelization, our methods can speculatively apply these transformations and then check their validity at run-time. Another important contribution 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 substantiate our claim that these techniques can yield significant speedups which are often superior to those obtainable by inspector/executor methods.
UR - http://www.scopus.com/inward/record.url?scp=84976823223&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84976823223&partnerID=8YFLogxK
U2 - 10.1145/223428.207148
DO - 10.1145/223428.207148
M3 - Article
AN - SCOPUS:84976823223
SN - 0362-1340
VL - 30
SP - 218
EP - 232
JO - ACM SIGPLAN Notices
JF - ACM SIGPLAN Notices
IS - 6
ER -