Loading...
Please wait, while we are loading the content...
Similar Documents
The LRPD Test: Speculative Run-Time Parallelization of Loops With Privatization and Reduction Parallelization (1995)
| Content Provider | CiteSeerX |
|---|---|
| Author | Rauchwerger, Lawrence Padua, David |
| Abstract | 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. 1 |
| File Format | |
| Publisher Date | 1995-01-01 |
| Access Restriction | Open |
| Subject Keyword | Reduction Parallelization Syntactic Pattern Matching Cross Iteration Dependence Significant Frac-tion Perfect Benchmark Important Contribu-tion Reduction Recognition Private Variable Array Participate Inspector Executor Method Parallel Data Dependence Test Unpredictable Control Flow Speculative Run-time Parallelization Reduction Paralleliza-tion Parallelizable Loop Lrpd Test Defined Access Pattern Fortran Program Available Parallelism Reduction Operation |
| Content Type | Text |
| Resource Type | Proceeding Article |
