next up previous
Next: Array Reduction Recognition Up: Analysis of Array Previous: Dependence and Array

Generating Executable Code With Array Privatization

It is straightforward to generate parallelized code for loops for which there are no dependences, but in the presence of array privatization, the system must ensure that initial and final values of the array are copied to and from the private copies.

If an array has upwards-exposed read regions, the compiler must copy these regions into the private copy prior to execution of the parallel loop. If an array is live on exit of the loop, then after a parallel execution of the loop the array must contain the same values as those obtained had the loop been executed sequentially; we do not test array liveness on exit, so we limit privatization to those cases where every iteration in the loop writes to exactly the same region of data. To do so the analysis performs the following test to finalize a loop whose index i has upper bound ub: If , the last loop iteration is peeled, and this final iteration writes to the original array. Earlier iterations write to a private copy of the array. No peeling is necessary if the compiler can guarantee that the last processor executes the last iteration. Then the compiler can generate code which simply writes to private copies in all the processors except the last one.

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