next up previous
Next: Reduction Recognition Up: Interprocedural Analysis for Parallelization Previous: Generating Executable Code

Array Reduction Recognition

  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.

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