HomeresearchPeopleGeneral InfoSeminarsResources
Abstract

Lawrence Rauchwerger, David Padua, "The Privatizing DOALL Test: A Run-Time Technique for DOALL Loop Identification and Array Privatization," Technical Report, 1383, Center for Supercomputing Research & Development, University of Illinois, Oct 1994.
Technical Report(ps, pdf, abstract)

Current parallelizing compilers cannot extract a significant fraction of the available parallelism in a loop if ithas a complex and/or statically insufficiently defined access pattern. This is an important issue because a large class of complex simulations used in industry today have 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, we have 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 ofits access pattern. We show 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.