A reduction occurs when a location is updated on each loop iteration with the result of a commutative and associative operation applied to its previous contents and some data value. A loop containing a reduction may be safely parallelized since the ordering of the commutative updates need not be preserved.
We have implemented a simple, yet powerful approach to recognizing reductions, in response to the common cases we have encountered in experimenting with the compiler. The reduction recognition, which is integrated with the array analysis described in the previous section, finds reductions involving general commutative updates to array elements, possibly spanning multiple procedures.