next up previous
Next: Generating Executable Code Up: Array Reduction Recognition Previous: Array Reduction Recognition

Reduction Recognition

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.



next up previous
Next: Generating Executable Code Up: Array Reduction Recognition Previous: Array Reduction Recognition



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