Article

Free access

The importance of direct dependences for automatic parallelization

Author:

T. BrandesAuthors Info & Claims

ICS '88: Proceedings of the 2nd international conference on Supercomputing

Pages 407 - 417

https://doi.org/10.1145/55364.55404

Published: 01 June 1988 Publication History

PDF eReader

Abstract

For the automatic vectorization and concurrentization of Fortran- or Pascal-like programs the dependencies have to be determined and to be observed with every transformation. The full dependence relation is a transitive relation. Direct dependencies are defined as such dependencies that cannot be represented transitively by other dependencies.

It will be shown that information about the direct dependencies is useful for renaming and expansion of structured variables. Indeed, many other transformations that are applied for automatic parallelization and program restructuring can be extended in this way. Though some extensions have already been made by other authors, with the concept of direct dependencies a uniform theoretical background for all these transformations is given.

As most known dependence tests do not give information about direct dependencies, it is also explained how to determine direct dependencies.

References

[1]

Allen, J.R.: Kennedy, K.: "A Parallel Programming Environment", IEEE Software, July 1985

Google Scholar

[2]

Banerjee, U.: "Speedup ofordinary programs" Ph.D. dissertation, Dep. Comput. Sci., University of Illinois, U rbana-Champaign, 1979

Digital Library

Google Scholar

[3]

Brandes, Th.: "Automatic Vectorization for High Level Languages based on an Expert System", Proceedings of CONPAR 86, Sept. 1986, Springer

Digital Library

Google Scholar

[4]

Brandes, Th.: "Determination ot~ Dependences in a Knowledge-Based Parallelization Tool", in proceedings of VAPPIII, 1987, Aug. 25-28, Liverpool

Google Scholar

[5]

Brandes, Th.: "Formal Methods for the Specification of Automatic Parallelization" (in german), Ph. d. dissertation, University of Marburg, Germany

Google Scholar

[6]

Brandes, Th.; Sommer, M.: "Realization of a Knowledge-Based Parallelization Tool in a Programming Environment", in proceedings of the International Conference on Supercomputing, 1987, Jun. 8-12, Athens

Digital Library

Google Scholar

[7]

Callahan, D. :"A Global Approach to Detection or Parallelism", Technical Report TR 87-50, Department of Computer Science, Rice University, Houston, Texas, 158 pp.

Google Scholar

[8]

Cytron, R.; Ferrante, J.: "What's in a Name? - or - The Value of Renaming for Parallelism Detection and Storage Allocation", Proceedings of the 1987 International Conference on Parallel Processing (St.Charles, Ill., Aug. 17-21) IEEE Press, New York 1987, pp. 19-27

Google Scholar

[9]

Kennedy, K.; Allen, J.R.: "Automatic Translation of Fortran programs to Vector Form" (revised Jan. 86), Technical Report TR84-9, Department of Computer Science, Rice University, Houston Texas

Google Scholar

[10]

Kuck, D.J.; Kuhn, R.H.; Padua, D.A.; Leasure, B.; Wolfe, M.: "Dependence graph and compiler optimizations", Proc. 8th ACM Symp. Principles Programming Lang., Williamsburg, VA, Jan. 1981

Digital Library

Google Scholar

[11]

Lamport, L.: "The Parallel Execution of DO Loops" Comm. of the ACM: February 1974, Vol. 17, No.2, pp. 83-93

Digital Library

Google Scholar

[12]

Padua, D.A." Wolfe, M.J." "Advanced Compiler Optimizations for Supercomputers", Comm. of the ACM, Vol. 29, Number 12, December 1986

Digital Library

Google Scholar

[13]

Wolfe, M.J.: "Optimizing super compilers for supercomputers", Ph. D. dissertation, Dep. Comput. Sci., Univ. Illinois, Urbana-Champaign, 1982

Digital Library

Google Scholar

Cited By

View all

Mohammadi MYuki TCheshmi KDavis EHall MDehnavi MNandy POlschanowsky CVenkat AStrout MMcKinley KFisher K(2019)Sparse computation data dependence simplification for efficient compiler-generated inspectorsProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314646(594-609)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314646
Creusillet BIrigoin F(2016)Interprocedural Array Region AnalysesInternational Journal of Parallel Programming10.1007/BF0335675824:6(513-546)Online publication date: 26-May-2016
https://doi.org/10.1007/BF03356758
Feautrier P(2005)Automatic parallelization in the polytope modelThe Data Parallel Programming Model10.1007/3-540-61736-1_44(79-103)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-61736-1_44
Show More Cited By

Index Terms

The importance of direct dependences for automatic parallelization

Recommendations

Removal of Redundant Dependences in DOACROSS Loops with Constant Dependences

An efficient algorithm to remove redundant dependences in simple loops with constant dependences is presented. Dependences constrain the parallel execution of programs and are typically enforced by synchronization instructions. The synchronization ...
Automatic parallelization of nonuniform loops
Minimum dependence distance tiling of nested loops with non-uniform dependences
SPDP '94: Proceedings of the 1994 6th IEEE Symposium on Parallel and Distributed Processing

We address the problem of partitioning nested loops with non-uniform (irregular) dependence vectors. Although many methods exist for nested loop partitioning, most of these perform poorly when parallelizing nested loops with irregular dependencies. We ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICS '88: Proceedings of the 2nd international conference on Supercomputing

June 1988

679 pages

ISBN:0897912721

DOI:10.1145/55364

Editor:
J. Lenfant
Rennes

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
307
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)13

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mohammadi MYuki TCheshmi KDavis EHall MDehnavi MNandy POlschanowsky CVenkat AStrout MMcKinley KFisher K(2019)Sparse computation data dependence simplification for efficient compiler-generated inspectorsProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314646(594-609)Online publication date: 8-Jun-2019
https://dl.acm.org/doi/10.1145/3314221.3314646
Creusillet BIrigoin F(2016)Interprocedural Array Region AnalysesInternational Journal of Parallel Programming10.1007/BF0335675824:6(513-546)Online publication date: 26-May-2016
https://doi.org/10.1007/BF03356758
Feautrier P(2005)Automatic parallelization in the polytope modelThe Data Parallel Programming Model10.1007/3-540-61736-1_44(79-103)Online publication date: 4-Jun-2005
https://doi.org/10.1007/3-540-61736-1_44
Barthou DCollard JFeautrier P(2005)Applications of Fuzzy Array Dataflow AnalysisEuro-Par'96 Parallel Processing10.1007/3-540-61626-8_56(424-427)Online publication date: 8-Jun-2005
https://doi.org/10.1007/3-540-61626-8_56
Pugh WWonnacott D(2005)An exact method for analysis of value-based array data dependencesLanguages and Compilers for Parallel Computing10.1007/3-540-57659-2_31(546-566)Online publication date: 31-May-2005
https://doi.org/10.1007/3-540-57659-2_31
Maydan DAmarsinghe SLam M(2005)Data dependence and data-flow analysis of arraysLanguages and Compilers for Parallel Computing10.1007/3-540-57502-2_63(434-448)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-57502-2_63
Seater RWonnacott D(2003)Polynomial Time Array Dataflow AnalysisLanguages and Compilers for Parallel Computing10.1007/3-540-35767-X_27(411-426)Online publication date: 13-May-2003
https://doi.org/10.1007/3-540-35767-X_27
Feautrier P(2001)Array dataflow analysisCompiler optimizations for scalable parallel systems10.5555/380466.380472(173-219)Online publication date: 1-Jun-2001
https://dl.acm.org/doi/10.5555/380466.380472
Seater RWonnacott D(2001)Polynomial time array dataflow analysisProceedings of the 14th international conference on Languages and compilers for parallel computing10.5555/1769331.1769358(411-426)Online publication date: 1-Aug-2001
https://dl.acm.org/doi/10.5555/1769331.1769358
Feautrier P(2001)Array Dataflow AnalysisCompiler Optimizations for Scalable Parallel Systems10.1007/3-540-45403-9_6(173-219)Online publication date: 18-May-2001
https://doi.org/10.1007/3-540-45403-9_6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Removal of Redundant Dependences in DOACROSS Loops with Constant Dependences

Automatic parallelization of nonuniform loops

Minimum dependence distance tiling of nested loops with non-uniform dependences