Article

Free access

Incremental dependence analysis for interactive parallelization

Authors:

Kurt StirewaltAuthors Info & Claims

ICS '90: Proceedings of the 4th international conference on Supercomputing

Pages 330 - 341

https://doi.org/10.1145/77726.255173

Published: 01 June 1990 Publication History

Abstract

Incrementally updating dependence information during interactive parallelization is a difficult proposition. We have developed a tool (PAT) that maintains dependence information during incremental transformations to a Fortran program, including loop parallelization, code replication, alignment and shifting, as well as insertion and deletion of code including parallel primitives. Our analysis is based on a variation on the standard approach to dependence graph generation, with program wide and local information separated in a sequential and a parallel dependence graph.

References

[1]

IBM Parallel FORTRAN, Language and Library Reference, International Business Machines Corporation (1988).

[2]

Alfred V. Aho, Ravi Sethi, and Jeffrey D. UUman, Compilers: Principles, Techniques and Tools, Addison-Wesley Publishing Company, Reading, Massachusetts (1987).

Digital Library

[3]

J.R. Alien, Ken Kennedy, Carrie Porterfield, and Joe Warren, "Conversion of Control Dependence to Data Dependence," Conference Record of the Tenth Annual ACM Symposium on Principles of Programruing Languages, Austin, Texas (January 1983).

Digital Library

[4]

Randy Allen, "Dependence Analysis for Subscripted Variables and its Application to Program Transformations," Phi) Dissertation, Department of Mathematical Science, Rice University, Houston, Texas (April 1983).

Digital Library

[5]

Randy Allen, Donn Baumgartner, Ken Kennedy, and Allan Porterfield, "PTOOL: A Semi-automatic Parallel Programming Assistant," Computer Science Technical Report, Rice University (January 1987).

[6]

Randy Allen, David Callahan, and Ken Kennedy, "Automatic Decomposition of Scientific Programs for Parallel Execution," Computer Science Technical Report, Rice COMP TR86-42, Rice University (November, 1986).

[7]

Randy Allen and Ken Kennedy, "Automatic Translation of Fortran Programs to Vector Form," Computer Science Technical Report, Rice COMP TR84- 9, Rice University (July, 1984).

[8]

Bill Appelbe and Kevin Smith, Analyzing Loops for Parallelism, submitted to the Journal of Parallel and Distributed Computing.

[9]

Bill Appelbe and Kevin Smith, "Replication and Alignment: A Unified Theory," Technical Report NO. G IT-ICS 88/36, Georgia Institute of Technology (October 1988).

[10]

Vasanth Balasundaram, "Interactive Parallelization of Numerical Scientific Programs," PhD Thesis, Department of Computer Science, Rice University (May 1989).

Digital Library

[11]

Utpal Banerjee, Dependence Analysis for Supercomputing, Kluwer Academic Publishers, Boston, Massachusetts (1988).

Digital Library

[12]

David Callahan, "A Global Approach to Detection of Parallelism," PhD Thesis, Rice COMP TR87-50, Rice University (April 1987).

Digital Library

[13]

David Callahan, lack Dongarra, and David Levine, "Vectorizing Compilers: A Test Suite and Results," Proceedings of Supercomputing '88, Orlando, Florida, pp. 98-105 (November 14-18, 1988).

Digital Library

[14]

Leslie A. Henderson, "The Usefulness of Dependency-Analysis Tools in Parallel Programming: Experiences Using Ptool," Technical Report LA-UR-87-3135, Los Alamos National Laboratory, Los Alamos, New Mexico (1988).

[15]

Gyungho Lee, Clyde P. Kruskal, and David I. Kuck, "The Effectiveness of Automatic Restructuring on Nonnumerical Programs," Proceedings of the 1985 International Conference on Parallel Processing, Los Angeles, California, pp. 607-613, IEEE Computer Society (August 20-23, 1985).

[16]

Zhiyuan Li, Pen-Chung Yew, and Chuan-Qi Zhu, "Data Dependence Analysis on Mul~dimensional Axray References," Proceedings of the 3rd International Conference on Supercomputing, Crete, Greece, pp. 215-224 (June 5-9, 1989).

Digital Library

[17]

Constantine D. Polychronopoulos, Parallel Programming and Compilers, Kluwer Academic Publishers, Boston, Massachusetts (1988).

Digital Library

[18]

Kevin Smith, "PAT: an Interactive Fortran Paxallelizing Assistant Tool," PhD Thesis, Georgia Institute of Technology, Atlanta, Georgia (December 1988).

Digital Library

[19]

Kevin Smith and Bill Appelbe, "Interactive Conversion of Sequential to Multitasking FORTRAN," Proceedings of the 3rd Internan'onal Conference on Supercomputing, Crete, Greece, pp. 225-234 (June 5-9, 1989),

Digital Library

[20]

Kevin Smith and William F. Appelbe, "PAT--An Interactive Fortran Parallelizing Assistant Tool," Proceedings of the 1988 International Conference on Parallel Processing, St. Charles, Illinois, pp. 58- 62, Penn State Press (August 15-19, 1988).

[21]

R.A. Towle, "Control and Data Dependence for Program Transformation," PhD Dissertation, Report 76-788, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Illinois (March 1976).

Digital Library

[22]

Michael Wolfe, "Advanced Loop Interchanging," Proceedings of the 1986 International Conference on Parallel Processing, Los Angeles, California, pp. 536-543, IEEE Computer Society (August 19- 22, 1986).

[23]

Michael J. Wolfe, "Optimizing Supercompilers for Supercomputers," PhD Thesis, UIUCDCS-R-82- 1105, University of Illinois at Urbana-Champaign (October 1982).

Digital Library

Cited By

Nougrahiya ANandivada V(2024)Homeostasis: Design and Implementation of a Self-Stabilizing CompilerACM Transactions on Programming Languages and Systems10.1145/364930846:2(1-58)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1145/3649308
Cai HJenkins JZaidman AKamei YHill E(2018)Leveraging historical versions of Android apps for efficient and precise taint analysisProceedings of the 15th International Conference on Mining Software Repositories10.1145/3196398.3196433(265-269)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3196398.3196433
Mishra VAggarwal S(2011)PartoolProceedings of the 9th international conference on Advanced parallel processing technologies10.5555/2042522.2042534(157-171)Online publication date: 26-Sep-2011
https://dl.acm.org/doi/10.5555/2042522.2042534
Show More Cited By

Index Terms

Incremental dependence analysis for interactive parallelization

Recommendations

Incremental dependence analysis for interactive parallelization
Special Issue: Proceedings of the 4th international conference on Supercomputing

Incrementally updating dependence information during interactive parallelization is a difficult proposition. We have developed a tool (PAT) that maintains dependence information during incremental transformations to a Fortran program, including loop ...
Incremental dependence analysis
Automatic speculative parallelization of loops using polyhedral dependence analysis
COSMIC '13: Proceedings of the First International Workshop on Code OptimiSation for MultI and many Cores

Speculative Execution (SE) runs loops in parallel even in the presence of a dependence. Using polyhedral dependence analysis, more speculation candidate loops can be discovered than normal OpenMP parallelization. In this research, a framework is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICS '90: Proceedings of the 4th international conference on Supercomputing

June 1990

492 pages

ISBN:0897913698

DOI:10.1145/77726

Chairmen:
Ahmed Sameh
Univ. of Illinois
,
Henk van der Vorst
Delft Univ. of Technology and CWI, The Netherlands

ACM SIGARCH Computer Architecture News Volume 18, Issue 3b
Special Issue: Proceedings of the 4th international conference on Supercomputing
Sept. 1990
489 pages
ISSN:0163-5964
DOI:10.1145/255129
Chairmen:
Ahmed Sameh
Univ. of Illinois at Urbana-Champaign, Urbana
,
Henk van der Vorst
Delft Univ. of Technology and CWI, The Netherlands
Issue’s Table of Contents

Copyright © 1990 ACM.

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]

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

IC'90

Sponsor:

SIGARCH

IC'90: ACM SIGARCH International Conference on Supercomputing

June 11 - 15, 1990

Amsterdam, The Netherlands

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
420
Total Downloads

Downloads (Last 12 months)90
Downloads (Last 6 weeks)16

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Nougrahiya ANandivada V(2024)Homeostasis: Design and Implementation of a Self-Stabilizing CompilerACM Transactions on Programming Languages and Systems10.1145/364930846:2(1-58)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1145/3649308
Cai HJenkins JZaidman AKamei YHill E(2018)Leveraging historical versions of Android apps for efficient and precise taint analysisProceedings of the 15th International Conference on Mining Software Repositories10.1145/3196398.3196433(265-269)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3196398.3196433
Mishra VAggarwal S(2011)PartoolProceedings of the 9th international conference on Advanced parallel processing technologies10.5555/2042522.2042534(157-171)Online publication date: 26-Sep-2011
https://dl.acm.org/doi/10.5555/2042522.2042534
Mak JMycroft A(2011)Critical-Path-Guided Interactive ParallelisationProceedings of the 2011 40th International Conference on Parallel Processing Workshops10.1109/ICPPW.2011.26(427-436)Online publication date: 13-Sep-2011
https://dl.acm.org/doi/10.1109/ICPPW.2011.26
Mishra VAggarwal S(2011)ParTool: A Feedback-Directed ParallelizerAdvanced Parallel Processing Technologies10.1007/978-3-642-24151-2_12(157-171)Online publication date: 2011
https://doi.org/10.1007/978-3-642-24151-2_12
Kennedy KMcKinley KTseng C(2006)Analysis and transformation in an interactive parallel programming toolConcurrency: Practice and Experience10.1002/cpe.43300507055:7(575-602)Online publication date: 25-Oct-2006
https://doi.org/10.1002/cpe.4330050705
Praveen KAggarwal SGhosh R(1996)Incremental data dependence analysisProceedings of 3rd International Conference on High Performance Computing (HiPC)10.1109/HIPC.1996.565823(195-200)Online publication date: 1996
https://doi.org/10.1109/HIPC.1996.565823
Kennedy KMcKinley KTseng C(1991)Analysis and transformation in the ParaScope editorProceedings of the 5th international conference on Supercomputing10.1145/109025.109126(433-447)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/109025.109126
Appelbe BSmith KStirewalt K(1991)PATCH—a new algorithm for rapid incremental dependence analysisProceedings of the 5th international conference on Supercomputing10.1145/109025.109123(424-432)Online publication date: 1-Jun-1991
https://dl.acm.org/doi/10.1145/109025.109123
Kennedy KMcKinley KTseng C(1991)Interactive Parallel Programming using the ParaScope EditorIEEE Transactions on Parallel and Distributed Systems10.1109/71.861082:3(329-341)Online publication date: 1-Jul-1991
https://dl.acm.org/doi/10.1109/71.86108

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten