Detection of Scans in Sequential Programs
Xavier Redonand
Paul Feautrier
Abstract:
Most automatic parallelizers
are based on the detection of independent operations. This
is a purely syntactical process, which relies on the computation of
dependences. There is another source of parallelism, which relies on
semantical information, namely the detection of reductions.
A reduction is the application of a binary associative operator to a vector
of values. When the intermediate results are kept, the operation is a scan.
Scans and reductions are quite frequent
in scientific codes and are implemented efficiently on most parallel
computers. A scan detector must be based on pattern-matching, but the
power of the detector is greatly increased if the program is normalized first.
Our normalizer uses an internal representation based on systems of recurrence
equations. This allow the detection of scans in loops nests of arbitrary
depth and on multi-dimensional arrays. Scan operators obey many transformations
rules, which allows the definition of a Scan algebra. Use of these rules
usually improves the performance of parallel programs and may lead
in the future to algorithm recognition.
keywords:
Automatic parallelization, reductions, scans, programs transformations,
programs normalization.
This document was translated from LATEX by
HEVEA and HACHA.