next up previous
Next: Putting It All Up: Array Analysis Previous: Array Data-Flow Analysis.

Array Reductions.

Array reduction recognition is performed by a simple algorithm that is integrated with the array data-flow analysis. Recognizing reductions begins with locating commutative and associative +, *, MIN or MAX operations to the same memory location. We mark the corresponding representations of these accesses in the summary with the reduction type (according to the operator). During the bottom-up interprocedural propagation for array data-flow analysis, we ensure that all accesses to the potential reduction array within the current loop are reduction operations of the same type. At each loop, we evaluate whether variables that carry a dependence and cannot be privatized are involved in a reduction computation. The variable's computation can only be reduced if every region described in the summary has the same reduction type. This simple algorithm is sufficiently powerful to recognize and parallelize the reductions in Figure 3(a)-(c).

Saman Amarasinghe
Fri Sep 15 09:15:06 PDT 1995