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.

• Introduction
  • Motivation for Scan Detection
  • The Dataflow Graph
• Overview of the Method
  • What is a Reduction?
  • Detecting a reduction
  • Normalization Strategy
• Program normalization
  • Translation to SLRE
  • Elimination of Variables Using Substitutions
  • Criterion for Total Elimination
  • Algorithms for Variables Elimination
• Identification of Scans
  • An Operator to Denote Scans
  • Scan Recognition
• Scan Algebra
  • Combination of Scans
  • Multi-directional Scans
  • Tactical Considerations
• Conclusion
  • Implementation
  • Future Work
• References

This document was translated from L^AT_EX by H^EV^EA and H^AC^HA.