Detection of Scans in the Polytope Model

Xavier Redon^*   Paul Feautrier^#

Abstract: Most automatic parallelizers are based on the detection of independent operations. Dependence analysis is mainly a syntactical process, in which the actual data transformations are ignored. There is another source of parallelism, which relies on semantical information, namely the detection of reductions and scans. Scans and reductions are quite frequent in scientific codes and are implemented efficiently on most parallel computers. We present here a new Scan detector which is based on the normalization of systems of recurrence equations. This allows the detection of scans in loops nests of arbitrary depth and on multi-dimensional arrays, and gives a uniform treatment for scalar reductions, array reductions, and arrays of reductions.

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

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