Article

Free access

Direct parallelization of call statements

Authors:

Francois Irigoin,

Paul FeautrierAuthors Info & Claims

SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler construction

Pages 176 - 185

https://doi.org/10.1145/12276.13329

Published: 01 July 1986 Publication History

Abstract

Asynchronous CALL statements are necessary in order to use more than one processor in current multiprocessors. Detecting CALL statements that may be executed in parallel is one way to fill this need. This approach requires accurate approximations of called procedure effects. This is achieved by using new objects called Region and Execution Context. An algorithm to find asynchronous CALL statements is given. It involves a new dependence test to compute data dependence graphs, which provides better results than previous ones even when no CALL statements are involved. This method has been implemented in Parafrase and preliminary results are encouraging.

References

[1]

F. E. Allen, Intvrprocedural Data Flow Analysis, Proc. of the IFIP Congress, North Holland, (1974)

[2]

U. Banerjee, Speedup of Ordinary Programs, Report No. UIUCDCS-R-79-989, University of Illinois at Urbana-Champaign, (1979)

[3]

P. Cousot, N. Halbwacks, Automatic Discovery of Linear Restraints among Variables of a Program, in Proc. of the 5th POPL, (1978)

Digital Library

[4]

R.G. Cytron, Compile-time Scheduling and Optimization for Asynchronous Machines, Report No. UIUCDCS-R-84-1177, University of Illinois at Urbana-Champaign, (1984)

[5]

J.J. Dongarra and R. E. Hiromoto, A Collection of Parallel Linear Equations Routine8 for the D~nelcor HEP, Parallel Computing, vol. 1(2), North Holland, (1984)

[6]

R. J. Duffin, On Fourier's Analysis of Linear Inequality Systems, Mathematical Programming Study 1, North Holland, (1974)

[7]

N. Halbwachs, Automatic Discovery of Linear Relationships among Variables of a Program, in French: D$termination automatique de relations lin~aires v~rifi~e, par les variables d'un programme, Th~se 3~me cycle, Universit~ de Grenoble (I.N.P.), (1979)

[8]

M.S. Hecht, Flow Analysis of Computer Programs, North Holland, (1977)

Digital Library

[9]

C. A. Huson, An 1n-Line Subroutine Expander for Parafrase, Rep. UIUCDCS-R- 82-1118, University of Illinois at Urbana- Champaign, (1982)

[10]

M. Karr, Affine Relationships among Variables of a Program, Acta inform atic a, No 6, ( 976)

[11]

K. Kennedy, Automatic Translation of Fortran Programs to Vector Form, Report No. 476-029-4, Rice University, (1980)

[12]

G. Killdal, A Unified Approch to Global Program Optimization, Proc. of the 1st POPL, (1973)

Digital Library

[13]

D. J. Kuek, Dependence Graph and Compiler Optimizations, Proc. of the 8th POPL, (1981)

Digital Library

[14]

R.H. Kuhn, Optimization and Intereonneetion Complezity for: Parallel Processors, Single-Stage Networks, and Decision Trees, Report No. ~CDCS-R-80-1009, University of Illinois at Urbana-Champaign, (1980)

[15]

Analyzer Documerttation (PARAFRASE), Center for Supercomputing R & D, University of Illinois at Urbana-Champaign, (1985)

[16]

R. Shostak, Deciding Linear Inequalities by Computing Loop Residue8, ACM Journal, vol. 28(4), (1981)

Digital Library

[17]

R. Triolet, Contribution to Automatic Parallelization of Fortran Programs with Procedure Calls in French: Contribution h la parall&liaation automatique de programmes Fortran eomportant de8 appel8 de procedure, Th~se de Docteur-Ing~nieur, Universit~ PARIS VI (I.P.), (1984)

[18]

R. Triolet, Interprocedural Analysis Based Restructuring of Fortran Programs, Proc. of the international Workshop, Parallel Algorithms & Architectures, Marseille (France), to be published by North-Holland, (Apr. 14-18, 1986)

Digital Library

[19]

A. Veidenbaum, Compiler Optimizations and Architecture Design Issues for M~ltiproeessors, Report No. UIUCDCS-R-85-1207, University of Illinois at Urbana-Champaign, (1985)

[20]

M. J. Wolfe, Optimizing Supercompilers for Supereomputers, Report No. UIUCDCS-R- 82-1105, University of Illinois at Urbana- Champaign, (1982)

Cited By

Mendonça GGuimarães BAlves PPereira MAraújo GPereira F(2017)DawnCCACM Transactions on Architecture and Code Optimization10.1145/308454014:2(1-25)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/3084540
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
Li Z(2014)Array privatization for parallel execution of loopsACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2667166(173-182)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2667166
Show More Cited By

Index Terms

Recommendations

Direct parallelization of call statements

Asynchronous CALL statements are necessary in order to use more than one processor in current multiprocessors. Detecting CALL statements that may be executed in parallel is one way to fill this need. This approach requires accurate approximations of ...
Evaluating a CALL software on the learning of English prepositions

This study assessed the effectiveness of using a CALL lesson (Computer Assisted Language Learning) over a conventional lesson to facilitate learning of English prepositions at Bario, Malaysia. CALL was developed by the Ministry of Education, Malaysia as ...
Advanced loop parallelization: dependence uniformization and trapezoid self-scheduling

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler construction

July 1986

275 pages

ISBN:0897911970

DOI:10.1145/12276

Editor:
Richard L Wexelblat
Philips Laboratories, Briarcliff Manor, NY

ACM SIGPLAN Notices Volume 21, Issue 7
July 1986
275 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/13310
Editor:
Richard L. Wexelblat
Philips Laboratories, Briarcliff Manor, NY
Issue’s Table of Contents

Copyright © 1986 Authors.

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1986

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCC86

Sponsor:

SIGPLAN

SCC86: SIGPLAN Symposium on Compiler Construction

June 25 - 27, 1986

California, Palo Alto, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

132
Total Citations
View Citations
512
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)10

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mendonça GGuimarães BAlves PPereira MAraújo GPereira F(2017)DawnCCACM Transactions on Architecture and Code Optimization10.1145/308454014:2(1-25)Online publication date: 26-May-2017
https://dl.acm.org/doi/10.1145/3084540
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
Li Z(2014)Array privatization for parallel execution of loopsACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2667166(173-182)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2667166
Irigoin FJouvelot PTriolet R(2014)Semantical interprocedural parallelizationACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2667163(143-150)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2667163
Li Z(2014)Author's retrospective for array privatization for parallel execution of loopsACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2591648(21-23)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2591648
Irigoin FJouvelot PTriolet R(2014)Author retrospective for semantical interprocedural parallelizationACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2591645(12-14)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2591645
Silber-Chaussumier FMuller AHabel R(2013)Generating data transfers for distributed GPU parallel programsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2013.07.02273:12(1649-1660)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1016/j.jpdc.2013.07.022
Li YAbousamra AMelhem RJones A(2012)Compiler-Assisted Data Distribution and Network Configuration for Chip MultiprocessorsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2011.27923:11(2058-2066)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1109/TPDS.2011.279
Qawasmeh AChapman BBanerjee A(2012)A Compiler-Based Tool for Array Analysis in HPC ApplicationsProceedings of the 2012 41st International Conference on Parallel Processing Workshops10.1109/ICPPW.2012.63(454-463)Online publication date: 10-Sep-2012
https://dl.acm.org/doi/10.1109/ICPPW.2012.63
Li YAbousamra AMelhem RJones ASalapura VGschwind MKnoop J(2010)Compiler-assisted data distribution for chip multiprocessorsProceedings of the 19th international conference on Parallel architectures and compilation techniques10.1145/1854273.1854335(501-512)Online publication date: 11-Sep-2010
https://dl.acm.org/doi/10.1145/1854273.1854335
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents