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.