Article

Free access

Removal of redundant dependences in DOACROSS loops with constant dependences

Authors:

V. P. Krothapalli,

P. SadayappanAuthors Info & Claims

PPOPP '91: Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming

Pages 51 - 60

https://doi.org/10.1145/109625.109632

Published: 01 April 1991 Publication History

PDF eReader

References

[1]

A.V. Aho, M.R. Garey, and J.D. Ullman. The Transitive Reduction of a Directed Graph. SIAM Journal of Computing, June 1972, pp.131-137.

Crossref

Google Scholar

[2]

F. Allen, M. Burke, P. Charles, R. Cytron, and J. Ferrante An Overview of the PTRAN Analysis System for Multiprocessing. Journal of Parallel and Distributed Computing., Vol. 5, No. 5, Oct 1988, pp.617-640.

Digital Library

Google Scholar

[3]

J.R. Allen and K. Kennedy. PFC: A Program to Convert FORTRAN to Parallel Form. Proceedings of the IBM Conference on Parallel Computers and Scientific Computations, March 1982.

Google Scholar

[4]

Shimon Even Graph Algorithms. Computer Science Press, 1979.

Digital Library

Google Scholar

[5]

Z.Fang, P. Yew, P. Tang, and C. Zhu Dynamic Processor Self-Scheduling for General Parallel Nested Loops. Int. Conf. on Parallel Processing, 1987, pp.l-10.

Google Scholar

[6]

V.P. Krothapalli and P. Sadayappan. Dynamic Scheduling of DOACROSS Loops, Prec. Parbase. 90 International Conference on Databases and Parallel Architectures, 1990.

Google Scholar

[7]

D.J. Kuck. et. al. Dependence Graphs and Compiler Optimizations. In Prec. A CM 8th Annual Symposium on Programming Languages, 1981, pp.207-218.

Digital Library

Google Scholar

[8]

D.J. Kuck. et. al. Parallel Supercomputing Today and the CEDAR Approach. Science, Vol. 231, No. 2, 1986, pp.967-974.

Crossref

Google Scholar

[9]

Zhiyuan Li and Abu-Sufah On Reducing Data Synchronization in Multiprocessed Loops IEEE Transactions on Computers, Vol. C-36, No. 1, 1987, pp. 105-109.

Google Scholar

[10]

S.P. Midkiff and D.A. Padua. Compiler Algorithm for Synchronization. IEEE Trans. Compu$., Vol. C- 36, No. 12, 1987, pp.1485-1495,

Digital Library

Google Scholar

[11]

C.D.Polychronopoulos. and D.Kuck. Guided Self- Scheduling: A Practical Scheduling Scheme for Parallel Supercomputers. IEEE Transactions on Computers, Vol. C-36, No. 12, 1987, pp.1425-1439.

Digital Library

Google Scholar

[12]

P. Tang, P. Yew, Z. Fang, and C. Zhu Deadlock Prevention in Processor Self-Scheduling for Parallel Nested Loops. Int. Conf. on Parallel Processing, 1987, pp.11-18.

Google Scholar

[13]

R. Tarjan. Depth First Search and Linear Graph Algorithms. SIAM Journal of Computing, 1(2), 1972, pp.146-160.

Crossref

Google Scholar

[14]

M.J. Wolfe. Techniques for Improving the Inherent Parallelism in Programs. Master's thesis, University of Illinois, Urbana-Champaign, July 1978.

Google Scholar

[15]

M.J. Wolfe. Optimizing Supercompilers for Supercomputers. The MIT Press, Cambridge, 1988

Digital Library

Google Scholar

[16]

C.Q. Zhu and P.C. Yew. A Scheme to Enforce Data Dependencies on Large Multiprocessor Systems. 1EEE Transactions on Software Engineering, Vol. SE-13, No.6, 1987, pp.726- 739.

Digital Library

Google Scholar

[17]

C.Q. Zhu and P.C. Yew. A Synchronization Scheme and its Applications for Large Multiprocessor Systems. Proc. 4th Int. Conf. on Distributed Computing Systems, 1984, pp.486-493.

Google Scholar

Cited By

View all

Cui YLiu SZou NWu W(2018)A Dynamic Parallel Strategy for DOACROSS LoopsProceedings of the International Conference on High Performance Computing in Asia-Pacific Region10.1145/3149457.3149469(108-115)Online publication date: 28-Jan-2018
https://dl.acm.org/doi/10.1145/3149457.3149469
Kelly WPugh WRosser EShpeisman T(2016)Transitive Closure of Infinite Graphs and Its ApplicationsInternational Journal of Parallel Programming10.1007/BF0335676024:6(579-598)Online publication date: 26-May-2016
https://doi.org/10.1007/BF03356760
Xiao LZhang XKuang ZFeng BKang J(2006)Auto-CFD-NOWThe Journal of Supercomputing10.1007/s11227-006-8324-z38:2(189-217)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1007/s11227-006-8324-z
Show More Cited By

Index Terms

Removal of redundant dependences in DOACROSS loops with constant dependences

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 ...
Redundant Synchronization Elimination for DOACROSS Loops

Cross-iterations data dependences in DOACROSS loops require explicit data synchronizations to enforce them. However, the composite effect of some data synchronizations may cover the other dependences and make the enforcement of those covered dependences ...
Time Stamp Algorithms for Runtime Parallelization of DOACROSS Loops with Dynamic Dependences

This paper presents a time stamp algorithm for runtime parallelization of general DOACROSS loops that have indirect access patterns. The algorithm follows the INSPECTOR/EXECUTOR scheme and exploits parallelism at a fine-grained memory reference level. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PPOPP '91: Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming

April 1991

223 pages

ISBN:0897913906

DOI:10.1145/109625

Chairman:
David S. Wise
Indiana Univ., Bloomington

ACM SIGPLAN Notices Volume 26, Issue 7
July 1991
223 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/109626
Editor:
Richard L. Wexelblat
IDA/CSED, Alexandria, VA
Issue’s Table of Contents

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 April 1991

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PPoPP91

Sponsor:

SIGPLAN

PPoPP91: 3rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

April 21 - 24, 1991

Virginia, Williamsburg, USA

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
318
Total Downloads

Downloads (Last 12 months)95
Downloads (Last 6 weeks)24

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Cui YLiu SZou NWu W(2018)A Dynamic Parallel Strategy for DOACROSS LoopsProceedings of the International Conference on High Performance Computing in Asia-Pacific Region10.1145/3149457.3149469(108-115)Online publication date: 28-Jan-2018
https://dl.acm.org/doi/10.1145/3149457.3149469
Kelly WPugh WRosser EShpeisman T(2016)Transitive Closure of Infinite Graphs and Its ApplicationsInternational Journal of Parallel Programming10.1007/BF0335676024:6(579-598)Online publication date: 26-May-2016
https://doi.org/10.1007/BF03356760
Xiao LZhang XKuang ZFeng BKang J(2006)Auto-CFD-NOWThe Journal of Supercomputing10.1007/s11227-006-8324-z38:2(189-217)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1007/s11227-006-8324-z
Kelly WPugh WRosser EShpeisman T(2005)Transitive closure of infinite graphs and its applicationsLanguages and Compilers for Parallel Computing10.1007/BFb0014196(126-140)Online publication date: 9-Jun-2005
https://doi.org/10.1007/BFb0014196
Li Xiao Xiadong Zhang Zhengqian Kuang Baiming Feng Jichang Kang (2003)Auto-FCD: efficiently parallelizing CFD applications on clustersProceedings IEEE International Conference on Cluster Computing CLUSTR-0310.1109/CLUSTR.2003.1253298(46-53)Online publication date: 2003
https://doi.org/10.1109/CLUSTR.2003.1253298
Chen DYew P(1999)Redundant Synchronization Elimination for DOACROSS LoopsIEEE Transactions on Parallel and Distributed Systems10.1109/71.77013810:5(459-470)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1109/71.770138
Rajamony RCox A(1997)Optimally synchronizing DOACROSS loops on shared memory multiprocessorsProceedings 1997 International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT.1997.644017(214-224)Online publication date: 1997
https://doi.org/10.1109/PACT.1997.644017
Kelly WPugh WRosser EShpeisman T(1996)Transitive Closure of Infinite Graphs and Its ApplicationsInternational Journal of Parallel Programming10.5555/247013.294946324:6(579-598)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.5555/247013.2949463
Chao HHarper M(1995)Minimizing redundant dependencies and interprocessor synchronizationsInternational Journal of Parallel Programming10.1007/BF0257786823:3(245-262)Online publication date: Jun-1995
https://doi.org/10.1007/BF02577868
Blume WEigenmann R(1992)Performance Analysis of Parallelizing Compilers on the Perfect Benchmarks ProgramsIEEE Transactions on Parallel and Distributed Systems10.1109/71.1806213:6(643-656)Online publication date: 1-Nov-1992
https://dl.acm.org/doi/10.1109/71.180621
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

Redundant Synchronization Elimination for DOACROSS Loops

Time Stamp Algorithms for Runtime Parallelization of DOACROSS Loops with Dynamic Dependences