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.