The Privatizing DOALL Test: A Run-Time Technique for DOALL Loop . . .

Current parallelizing compilers cannot extract a significant fraction of the available parallelism in a loop if it has a complex and/or statically insufficiently defined access pattern. This is an important issue because a large class of complex simulations used in industry todayhave irregular domains and/or dynamically changing interactions. To handle these types of problems methods capable of automatically extracting parallelism at run--time are needed. For this reason, wehave developed the Privatizing DOALL test -- a technique for identifying fully parallel loops at run--time, and dynamically privatizing scalars and arrays. The test is fully parallel, requires no synchronization, is easily automatable, and can be applied to any loop, regardless of its access pattern. Weshow that the expected speedup for fully parallel loops is significant, and the cost of a failed test (a not fully parallel loop) is minimal.We present experimental results on loops from the PERFECT Benchmarks which confirm our conclusion that this test can lead to significant speedups