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.