We currently recognize reductions on scalar variables and array locations
involving the operations , , ` MIN`, and `
MAX`. ` MIN` (and, equivalently, ` MAX`) reductions of the form
` if (a(i) tmin) tmin = a(i)` are also supported.

The system looks for commutative updates to a single location **A**
of the form , where **A** is either a scalar
variable or an array location and is one of the operations listed
above. This approach allows any commutative update to a single
array location to be recognized as a reduction,
even without information
about the array indices. We illustrate this point
with an example sparse matrix-vector multiply found in the NAS
sample benchmark * cgm*:

DO 200 J = 1, N XJ = X(J) DO 100 K = COLSTR(J) , COLSTR(J+1)-1 Y(ROWIDX(K)) = Y(ROWIDX(K)) + A(K) * XJ 100 CONTINUE 200 CONTINUE

Our system correctly determines that updates to ` Y` are
reductions on the outer loop, even though ` Y` is
indexed by another array ` ROWIDX` and so the array access functions
for ` Y` are not affine expressions.

The reduction recognition analysis first locates commutative updates in a loop body; it verifies that the only other reads and writes in the loop to the same location are also commutative updates of the same type described by . A loop is parallelized if all dependences involve variables whose only accesses are reduction operations of identical type.

In terms of our data-flow analysis algorithm, reduction recognition is initialized by examining the code for commutative updates to the same array location. Whenever an array element is involved in a commutative update, the array analysis derives summaries for the read and written subarrays and marks the system of inequalities as a reduction of the type described by . When meeting two systems of inequalities during the interval analysis, the reduction types are also met. The resulting system of inequalities will only be marked as a reduction if both reduction types are identical.

Mon Oct 2 11:00:22 PDT 1995