Article

Free access

Optimal loop parallelization

Authors:

A. Aiken,

A. NicolauAuthors Info & Claims

PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementation

Pages 308 - 317

https://doi.org/10.1145/53990.54021

Published: 01 June 1988 Publication History

PDF eReader

References

[1]

AIKEN, A., AND NICOLAU, A. Loop Quantization: an analysis and algorithm. Tech. Rep. 87-821, Cornell Univ., 1987.

Digital Library

Google Scholar

[2]

AiKEN, A., AND NICOLAU, A. A development environment for horizontal microcode. IEEE Trans. Softw. Eng. (May 1988). Also available as Cornell Tech. Rep. TR 86-785.

Digital Library

Google Scholar

[3]

AIKEN, A., AND NICOLAU, A. Perfect Pipelining: A new loop parallelization technique. In Proc. of the 1988 European Syrup. on Programming (Mar. 1988), Springer Verlag Lecture Notes in Computer Science. Also available as Cornell Tech. Rep. TR 87-873.

Digital Library

Google Scholar

[4]

ALbEN, J. R., AND KENNEDY, K. Automatic loop interchange. In Proc. of the 1985 SIGPLAN Syrup. on Compiler Construction (June 1984), pp. 233-246.

Digital Library

Google Scholar

[5]

AbLEN, J. R., KENNEDY, K., PORTEn- FIELD, C., AND WARREN, J. Conversion of control dependence to data dependence. In Proc. of the 1983 Syrup. on Principles of Programming Languages (Jan. 1983), pp. 177-189.

Digital Library

Google Scholar

[6]

C. POLYCHRONOPOULOS, D. KucK, D. P. Execution of parallel loops on parallel processor systems. In Proc. o} the 1986 lnt 'l Conj. on Parallel Processing (Aug. 1986), pp. 519-27.

Google Scholar

[7]

CALLAHAN, D., CocKs, J., aND KENNEDY, K. Estimating interlock and improving balance for pipelined architectures, in Proc. of the 1987 Int'l Conf. on Parallel Processing (Aug. 1987), pp. 297- 304.

Google Scholar

[8]

CYTRON, R. Compile-time Scheduling and Optimization for Asynchronous Machines. PhD thesis, Univ. of Illinois at Urbana-Champaign, 1984.

Digital Library

Google Scholar

[9]

CYTRON, R. Doacross: Beyond vectorization for muttiprocessors. In Proc. of the 1986 lnt'l Conf. on Parallel Processing (Aug. 1986), pp. 836-844.

Google Scholar

[10]

ENGIOGLU, K. A compilation technique for software pipelining of loops with conditional jumps. In Proc. of the 20th Annual Workshop on Microprogramming (Dec. 1987), pp. 69--79.

Digital Library

Google Scholar

[11]

Flsasa, J. A. Trace Scheduling: A technique for global microcode compaction. IEEE Trans. Comput. C-30, 7 (July 1981), 478-90.

Google Scholar

[12]

Ganzv, M. R., AND JOHNSON, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.

Digital Library

Google Scholar

[13]

KUCK, D., Kt;uN, R., PADua, D., LEA- SURE, B., AND WOLFE, M. Dependence graphs and compiler optimizations. In Proc. of the 1981 Syrup. on Principles of Programming Languages (Jan. 1981), pp. 207-218.

Digital Library

Google Scholar

[14]

LaM, M. A Systolic Array Optimizing Compiler. PhD thesis, Carnegie Mellon Univ., 1987.

Digital Library

Google Scholar

[15]

McMAnoN, F. H. Lawrence Livermore National Laboratory FORTRAN kernels: MFLOPS. Livermore, CA., 1983.

Google Scholar

[16]

MUNSHI, A., AND SIMONS, B. Scheduling sequential loops on parallel processors. Tech. Rep. 5546, IBM, 1987.

Google Scholar

[17]

PADUA-HAIEK, D. A. Multiprocessors: Discussion of Some Theoretical and Practical Problems. PhD thesis, Univ. of Illinois at Urbana-Champaign, 1979.

Google Scholar

[18]

SMITh, B. T., BOYLE, J. M., IKEnE, Y., KLgMA, V. C., riND MOLga, C. 13. M'atriz Eigensystem Routines: EISPACh' Guide, 2 ed. Springer-Verlag, New York, 1970.

Google Scholar

Cited By

View all

Levy BIshaq MSherman BKennard LMilanova AZikas VMeng WJensen CCremers CKirda E(2023)COMBINE: COMpilation and Backend-INdependent vEctorization for Multi-Party ComputationProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623181(2531-2545)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623181
Guo JYing M(2023)Software Pipelining for Quantum Loop ProgramsIEEE Transactions on Software Engineering10.1109/TSE.2022.323262349:4(2815-2828)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TSE.2022.3232623
Sharma RKulshreshtha SThakur MShirani POnut INg TKent KBaşar AOnut I(2022)ZS3: Marrying Static Analyzers and Constraint Solvers to Parallelize Loops in Managed RuntimesProceedings of the 32nd Annual International Conference on Computer Science and Software Engineering10.5555/3566055.3566082(213-220)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.5555/3566055.3566082
Show More Cited By

Recommendations

Optimal Loop Parallelization
Optimal loop parallelization for maximizing iteration-level parallelism
CASES '09: Proceedings of the 2009 international conference on Compilers, architecture, and synthesis for embedded systems

This paper solves the open problem of extracting the maximal number of iterations from a loop that can be executed in parallel on chip multiprocessors. Our algorithm solves it optimally by migrating the weights of parallelism-inhibiting dependences on ...
Advanced loop parallelization: dependence uniformization and trapezoid self-scheduling

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementation

June 1988

338 pages

ISBN:0897912691

DOI:10.1145/53990

Editor:
R. L. Wexelblat
Philips Laboratories, Briarcliff Manor, NY

ACM SIGPLAN Notices Volume 23, Issue 7
Proceedings of the SIGPLAN '88 conference on Programming language design and implementation
July 1988
338 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/960116
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 June 1988

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI88

Sponsor:

SIGPLAN

PLDI88: SIGPLAN 88

June 20 - 24, 1988

Georgia, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

191
Total Citations
View Citations
1,600
Total Downloads

Downloads (Last 12 months)175
Downloads (Last 6 weeks)25

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Levy BIshaq MSherman BKennard LMilanova AZikas VMeng WJensen CCremers CKirda E(2023)COMBINE: COMpilation and Backend-INdependent vEctorization for Multi-Party ComputationProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623181(2531-2545)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623181
Guo JYing M(2023)Software Pipelining for Quantum Loop ProgramsIEEE Transactions on Software Engineering10.1109/TSE.2022.323262349:4(2815-2828)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TSE.2022.3232623
Sharma RKulshreshtha SThakur MShirani POnut INg TKent KBaşar AOnut I(2022)ZS3: Marrying Static Analyzers and Constraint Solvers to Parallelize Loops in Managed RuntimesProceedings of the 32nd Annual International Conference on Computer Science and Software Engineering10.5555/3566055.3566082(213-220)Online publication date: 15-Nov-2022
https://dl.acm.org/doi/10.5555/3566055.3566082
Abe THosking AFinocchi I(2019)A type system for data independence of loop iterations in a directive-based PGAS languageProceedings of the 16th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3357390.3361021(50-62)Online publication date: 21-Oct-2019
https://dl.acm.org/doi/10.1145/3357390.3361021
Estebanez ALlanos DGonzalez-Escribano A(2016)A Survey on Thread-Level Speculation TechniquesACM Computing Surveys10.1145/293836949:2(1-39)Online publication date: 30-Jun-2016
https://dl.acm.org/doi/10.1145/2938369
Bocić IBultan TBertolino ACanfora GElbaum S(2015)Coexecutability for efficient verification of data model updatesProceedings of the 37th International Conference on Software Engineering - Volume 110.5555/2818754.2818844(744-754)Online publication date: 16-May-2015
https://dl.acm.org/doi/10.5555/2818754.2818844
Prihozhy ABezati EAb Rahman AMattavelli M(2015)Synthesis and Optimization of Pipelines for HW Implementations of Dataflow ProgramsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2015.242727834:10(1613-1626)Online publication date: Oct-2015
https://doi.org/10.1109/TCAD.2015.2427278
Bocic IBultan T(2015)Coexecutability for Efficient Verification of Data Model Updates2015 IEEE/ACM 37th IEEE International Conference on Software Engineering10.1109/ICSE.2015.87(744-754)Online publication date: May-2015
https://doi.org/10.1109/ICSE.2015.87
Zhang WGoswami DGoodarzi BDesai B(2014)On the Dynamic Scheduling of Task Farm Patterns on a Heterogeneous CPU-GPGPU EnvironmentProceedings of the 2014 International C* Conference on Computer Science & Software Engineering10.1145/2641483.2641530(1-7)Online publication date: 3-Aug-2014
https://dl.acm.org/doi/10.1145/2641483.2641530
Ebcioglu KNicolau A(2014)A global resource-constrained parallelization techniqueACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2667160(112-121)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2667160
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

Optimal Loop Parallelization

Optimal loop parallelization for maximizing iteration-level parallelism

Advanced loop parallelization: dependence uniformization and trapezoid self-scheduling