Article

Free access

Compiling issues for supercomputers

Authors:

C. PolychronopoulosAuthors Info & Claims

Supercomputing '88: Proceedings of the 1988 ACM/IEEE conference on Supercomputing

Pages 164 - 173

Published: 01 November 1988 Publication History

Abstract

Accurate and fast methods for computing data dependencies are vital to the efficiency of vectorizing and parallelizing compilers. Program transformations employed by these compilers are effective only if dependencies are computed as accurately as possible. In this paper we consider two issues for supercomputer compilers. First, we discuss in detail exact and inexact tests for computing data dependencies and focus on the linearization scheme. We then discuss a program transformation call loop spreading which allows us to execute in parallel adjacent loops with interloop dependencies.

References

[1]

Aho A. V., R. Sethi, J. D. Ullman. Compilers: Principles, Techniques, and Tools, Addison- Wesley, Reading, Massachusetts, 1986.

Digital Library

[2]

Allen F. E., J. Cocke. A Catalogue of Optimixing Transformations in Design and Optimization of Compilers, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, New Jersey, 1972, pp. 1-30.

[3]

Allen F. E. et. al. An overview of the PTRAN analysis system, Proceedings of the 1987 International Conference on Supercomputing, Springer-Verlag, LNCS, February 1988.

Digital Library

[4]

Allen J. R., K. Kennedy. PFC: A Program to Convert Fortran to Parallel Form, Tech. Rept. MASC-TR82-6, Rice University, Houston, Texas, March 1982.

[5]

Allen R., K. Kennedy. Automatic Translation of FORTRAN Programs to Vector Form, ACM Transactions on Programming Languages and Systems, Vol. 9, No. 4, October 1987.

Digital Library

[6]

Banerjee U. Data Dependence in Ordinary Programa, M.S. Thesis, University of Illinois, DCS Report No. UIUCDCS-R-76-837, November 1976.

[7]

Banerjee U. Speedup of Ordinary Programa, Ph.D. Thesis, University of Illinois at Urbana- Champaign, DCS Report No. UIUCDCS-R-79- 989, October 1979.

Digital Library

[8]

Bernstein A. J. Analysis of Programs for Parallel Processing, IEEE Trans. on Electronic Computers, Vol. EC-15, No. 5, October 1966, pp. 757-763.

[9]

Burke M., Cytron R. Interprocedural Dependence Analysis and Parullelitation, Proceedings of the SIGPLAN 86 Symposium on Compiler Construction, 21(7), July 1986 pp. 162-175.

Digital Library

[10]

Cytron R. G. Doacross: Beyond Vectorization for Multiprocessors (Exended Abstract), Proceedings of the 1986 International Conference on Parallel Processing, St. Charles, IL, August, 1986, pp. 836-844.

[11]

Hardy C. II., E. M. Wright An Introduction to the Theory of Numbers, Oxford, 1979.

[12]

Knuth D. E. The Art of Computer Programming, Vol. 2 / Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969.

Digital Library

[13]

Kuck D. J. The Structure of Computers and Computatiotu, Volume 1, John Wiley and Sons, New York, 1978.

Digital Library

[14]

Kuck D. J., E. S. Davidson, D. H. Lawrie, A. H. Sameh. Parallel Supercomputing Today and the Cedar Approach, Science, Vol. 231, 4740, February 28, 1986, pp. 967-974.

[15]

Kuck D. J., R. H. Kuhn, B. Leasure, M. Wolfe. The Structure of an Advanced Vectoriter for Pipelined Processors, Fourth International Computer Software and Applications Conference, October, 1980.

[16]

Kuck D. J., R. Kuhn, D. Padua, B. Leasure, M. Wolfe. Dependence Graphs and Compiler Optimizations, Proceedings of the 8-th ACM Symposium on Principles of Programming Languages, January 1981, pp. 207-218.

Digital Library

[17]

Malm D. G. A Computer Laboratory Manual for Number Theory, COMPress, Inc., Wentworth, New Hampshire, 1980.

[18]

Midkiff S. P., D. A. Padua. Compiler Generated Synchronization for DO Loops, Proc. of the 1986 International Conference on Parallel Processing, St. Charles, IL, August, 1986, pp. 544-551.

[19]

Nicolau A., Parallelism, Memory Anti-Aliasing and Correctness for Tmce Scheduling Compilers, Ph.D. Thesis, Yale University, June 1984.

Digital Library

[20]

Padua D. A., D. J. Kuck, D. H. Lawrie. High- Speed Multiprocessors and Compilation Techniquea, IEEE Transactions on Computers, Vol. C-29, No. 9, September 1980.

[21]

Peir J. K. Pmgmm Partitioning and Synchronization on Multiprocessor Systems, Depaxtment of Computer Science, University of lllinois at Urbana-Champaign, DCS Report No. UIUCCDCS-R-86-1259, March 1986.

Digital Library

[22]

Polychronopoulos C. D. hfore on Advanced Loop Optimizations, CSRD Technical Report No. 667, Center for Supercomputing Research and Development, University of Illinois, 1987.

[23]

Potychronopoulos C. D. On Program Restructuring, Scheduling, and Communication for Parallel Processor Systems, Ph.D. Thesis, CSRD Technical Report No. 595, Center for Supercomputing Research and Development, University of Illinois, August, 1986.

Digital Library

[24]

Polychronopoulos C. D., D. J. Kuck Guided Self- Scheduling: A Practical Scheduling Scheme for Parallel Supercomputers, IEEE Trans. on Computers, Vol. 36, No. 12, December 1987.

Digital Library

[25]

Wolfe M. J. Optimizing Supercompilers for Supercomputers, Ph.D. Thesis, University of Illinois at Urbana-Champaign, DCS Report No. UIUCCDCS-R-82-1105, 1982.

Digital Library

Cited By

Psarris K(1996)The Banerjee-Wolfe and GCD Tests on Exact Data Dependence InformationJournal of Parallel and Distributed Computing10.1006/jpdc.1996.000932:2(119-138)Online publication date: 1-Feb-1996
https://dl.acm.org/doi/10.1006/jpdc.1996.0009
Graham SLucco SSharp O(1993)Orchestrating interactions among parallel computationsACM SIGPLAN Notices10.1145/173262.15510028:6(100-111)Online publication date: 1-Jun-1993
https://dl.acm.org/doi/10.1145/173262.155100
Graham SLucco SSharp O(1993)Orchestrating interactions among parallel computationsProceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation10.1145/155090.155100(100-111)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1145/155090.155100
Show More Cited By

Recommendations

Optimizing supercompilers for supercomputers
Optimizing Supercompilers for Supercomputers
A study of scalar compilation techniques for pipelined supercomputers
ASPLOS II: Proceedings of the second international conference on Architectual support for programming languages and operating systems

This paper studies two compilation techniques for enhancing scalar performance in high-speed scientific processors: software pipelining and loop unrolling. We study the impact of the architecture (size of the register file) and of the hardware (size of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Supercomputing '88: Proceedings of the 1988 ACM/IEEE conference on Supercomputing

November 1988

458 pages

ISBN:081860882X

Chairman:
G. A. Michael
Lawrence Livermore National Laboratory

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS: Computer Society

In-Cooperation

NSF: National Science Foundation
NASA: National Aeronatics and Space Administration
Supercomputer Edu & Resch Ctr: Supercomputer Edu & Resch Ctr

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 November 1988

Check for updates

Qualifiers

Article

Conference

Supercomputing88

Sponsor:

SIGARCH
IEEE-CS

Supercomputing88: International Conference for High Performance Computing, Networking, Storage and Analysis

November 12 - 17, 1988

Florida, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
228
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)5

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Psarris K(1996)The Banerjee-Wolfe and GCD Tests on Exact Data Dependence InformationJournal of Parallel and Distributed Computing10.1006/jpdc.1996.000932:2(119-138)Online publication date: 1-Feb-1996
https://dl.acm.org/doi/10.1006/jpdc.1996.0009
Graham SLucco SSharp O(1993)Orchestrating interactions among parallel computationsACM SIGPLAN Notices10.1145/173262.15510028:6(100-111)Online publication date: 1-Jun-1993
https://dl.acm.org/doi/10.1145/173262.155100
Graham SLucco SSharp O(1993)Orchestrating interactions among parallel computationsProceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation10.1145/155090.155100(100-111)Online publication date: 1-Aug-1993
https://dl.acm.org/doi/10.1145/155090.155100
Psarris KKennedy KPolychronopoulos C(1992)On exact data dependence analysisProceedings of the 6th international conference on Supercomputing10.1145/143369.143424(303-312)Online publication date: 1-Aug-1992
https://dl.acm.org/doi/10.1145/143369.143424
Goff GKennedy KTseng C(1991)Practical dependence testingACM SIGPLAN Notices10.1145/113446.11344826:6(15-29)Online publication date: 1-May-1991
https://dl.acm.org/doi/10.1145/113446.113448
Goff GKennedy KTseng CWise D(1991)Practical dependence testingProceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation10.1145/113445.113448(15-29)Online publication date: 1-May-1991
https://dl.acm.org/doi/10.1145/113445.113448

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