Advanced search
1 file | 1.85 MB

Partitioning and labeling of loops by unimodular transformations

Author
Organization
Abstract
In a nested loop the indexes form an index vector and the index vectors of all iterations form the index set. The dependencies between the loop iterations are represented by dependence vectors, which are stored as the columns of the dependence matrix. Parallel execution of the independent subsets of the index set requires no communication or synchronization and is therefore quite efficient. A general method for the identification of the independent subsets in loops with constant dependence vectors is presented. First it is shown that the dependence relation remains invariant under a unimodular transformation. Then a unimodular transformation is used to bring the dependence matrix into a form where the independent subsets are obtained by a direct and inexpensive partitioning algorithm. This leads to a procedure for the automatic conversion of a serial loop into a nest of parallel DO-ALL loops. Another unimodular transformation results in an algorithm to label the dependent iterations of an n-fold nested loop in O(n2) time. This provides a multithreaded dynamic scheduling scheme requiring only one fork and one join primitive.
Keywords
ALGORITHMS, SUPERCOMPUTERS, SCHEME, SYNCHRONIZATION, COMPILER OPTIMIZATIONS, UNIMODULAR TRANSFORMATION, NESTED LOOP PARTITIONING, DYNAMIC SELF-SCHEDULING, DO ALL CONVERSION, CONSTANT DEPENDENCE VECTORS, DATA DEPENDENCE REMAPPING

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 1.85 MB

Citation

Please use this url to cite or link to this publication:

Chicago
D’Hollander, Erik. 1992. “Partitioning and Labeling of Loops by Unimodular Transformations.” Ieee Transactions on Parallel and Distributed Systems 3 (4): 465–476.
APA
D’Hollander, E. (1992). Partitioning and labeling of loops by unimodular transformations. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 3(4), 465–476.
Vancouver
1.
D’Hollander E. Partitioning and labeling of loops by unimodular transformations. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS. 1992;3(4):465–76.
MLA
D’Hollander, Erik. “Partitioning and Labeling of Loops by Unimodular Transformations.” IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 3.4 (1992): 465–476. Print.
@article{206476,
  abstract     = {In a nested loop the indexes form an index vector and the index vectors of all iterations form the index set. The dependencies between the loop iterations are represented by dependence vectors, which are stored as the columns of the dependence matrix. Parallel execution of the independent subsets of the index set requires no communication or synchronization and is therefore quite efficient. A general method for the identification of the independent subsets in loops with constant dependence vectors is presented. First it is shown that the dependence relation remains invariant under a unimodular transformation. Then a unimodular transformation is used to bring the dependence matrix into a form where the independent subsets are obtained by a direct and inexpensive partitioning algorithm. This leads to a procedure for the automatic conversion of a serial loop into a nest of parallel DO-ALL loops. Another unimodular transformation results in an algorithm to label the dependent iterations of an n-fold nested loop in O(n2) time. This provides a multithreaded dynamic scheduling scheme requiring only one fork and one join primitive.},
  author       = {D'Hollander, Erik},
  issn         = {1045-9219},
  journal      = {IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS},
  keywords     = {ALGORITHMS,SUPERCOMPUTERS,SCHEME,SYNCHRONIZATION,COMPILER OPTIMIZATIONS,UNIMODULAR TRANSFORMATION,NESTED LOOP PARTITIONING,DYNAMIC SELF-SCHEDULING,DO ALL CONVERSION,CONSTANT DEPENDENCE VECTORS,DATA DEPENDENCE REMAPPING},
  language     = {eng},
  number       = {4},
  pages        = {465--476},
  title        = {Partitioning and labeling of loops by unimodular transformations},
  volume       = {3},
  year         = {1992},
}