next up previous
Next: Generating Executable Code Up: Analysis of Array Previous: Transfer Functions.

Dependence and Array Privatization Tests


To determine if array accesses allow the parallelization of a loop with index i, dependence and privatization tests are performed on the summary sets for the loop body :

A loop may be safely parallelized if there are no loop-carried true, anti or output dependences. The array privatization test is applied only to the variables that are involved in dependences to determine if privatization will eliminate these dependences.

Our formulation of array privatization is an extension of Tu and Padua's algorithm[21]. Tu and Padua recognize an array as privatizable only if there are no upwards-exposed reads within the loop. Our algorithm is more general in that upwards-exposed reads are acceptable as long as they do not overlap writes in other iterations of the same loop.

Saman Amarasinghe
Mon Oct 2 11:00:22 PDT 1995