A practical run-time technique for exploiting loop-level parallelism

In order to exploit potential parallelism of loops, in which the array acce ss patterns cannot be analyzed at compile-time, parallelizing compilers mus t rely on the run-time dependence analysis techniques. The LRPD test is not ed in this field for its applicability. It assumes full parallelism and exe cutes speculatively, then examines the correctness of parallel execution af ter loop termination. We extended the concept and developed a practical run -time technique, called the speculative parallelization with new technology (SPNT) test, to further exploit loop-level parallelism. Two main character istics make the SPNT test distinguished. The first is improving the success rate of speculative parallelization by eliminating all cross-iteration dat a dependences except the cross-processory flow dependences. The second is r educing the failure penalty by aborting the speculative parallel execution immediately once a cross-processor flow dependence is detected during the e xecution. Our experimental results on shared-memory parallel machines lip S PP2000 and ALR QUAD6 prove the high effectiveness of the SPNT test. (C) 200 0 Elsevier Science Inc. All rights reserved.