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).

Fri Sep 15 09:15:06 PDT 1995