The R-LRPD Test: Speculative Parallelization of Partially Parallel Loops

Current parallelizing compilers cannot identify a signifi-cant fraction of parallelizable loops because they have com-plex or statically insufficiently defined access patterns. In our previously proposed framework we have speculatively executed a loop as a doall, and applied a fully paral-lel data dependence test to determine if it had any cross– processor dependences; If the test failed, then the loop was re–executed serially. While this method exploits doall parallelism well, it can cause slowdowns for loops with even one cross-processor flow dependence because we have to re-execute sequentially. Moreover, the existing, partial parallelism of loops is not exploited. We now propose a gen-eralization of our speculative doall parallelization tech-nique, called the Recursive LRPD test, that can extract and exploit the maximum available parallelism of any loop and that limits potential slowdowns to the overhead of the run-time dependence test itself. In this paper we present the base algorithm and an analysis of the different heuristics for its practical application and a few experimental results on loops from Track, Spice, and FMA3D. 1. Improving Loop Parallelization Coverage To achieve a high level of performance for a particu-lar program on today’s supercomputers, software develop-ers are often forced to tediously hand–code optimizations tailored to a specific machine. Such hand–coding is diffi-cult, increases the possibility of error over sequential pro-gramming, and the resulting code may not be portable to other machines. Restructuring, or parallelizing, compilers detect and exploit parallelism in programs written in con-ventional sequential languages or parallel languages (e.g.