More Web Proxy on the site http://driver.im/

article

Open access

Automatic translation of FORTRAN programs to vector form

Editor: Susan L. Graham Authors:

Ken KennedyAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 9, Issue 4

Pages 491 - 542

https://doi.org/10.1145/29873.29875

Published: 01 October 1987 Publication History

Abstract

The recent success of vector computers such as the Cray-1 and array processors such as those manufactured by Floating Point Systems has increased interest in making vector operations available to the FORTRAN programmer. The FORTRAN standards committee is currently considering a successor to FORTRAN 77, usually called FORTRAN 8x, that will permit the programmer to explicitly specify vector and array operations.

Although FORTRAN 8x will make it convenient to specify explicit vector operations in new programs, it does little for existing code. In order to benefit from the power of vector hardware, existing programs will need to be rewritten in some language (presumably FORTRAN 8x) that permits the explicit specification of vector operations. One way to avoid a massive manual recoding effort is to provide a translator that discovers the parallelism implicit in a FORTRAN program and automatically rewrites that program in FORTRAN 8x.

Such a translation from FORTRAN to FORTRAN 8x is not straightforward because FORTRAN DO loops are not always semantically equivalent to the corresponding FORTRAN 8x parallel operation. The semantic difference between these two constructs is precisely captured by the concept of dependence. A translation from FORTRAN to FORTRAN 8x preserves the semantics of the original program if it preserves the dependences in that program.

The theoretical background is developed here for employing data dependence to convert FORTRAN programs to parallel form. Dependence is defined and characterized in terms of the conditions that give rise to it; accurate tests to determine dependence are presented; and transformations that use dependence to uncover additional parallelism are discussed.

References

[1]

AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass, 1974.

[2]

ALLEN, F. E., COCKE, J., AND KENNEDY, K. Reduction of operator strength. In Program Flow Analysis: Theory and Applications, N. D. Jones and S. S. Muchnick, Eds. Prentice-Hall, Englewood Cliffs, N.J., 1981.

[3]

ALLEN, J. R., KENNEDY, K., PORTERFIELD, C., AND WARREN, J. Conversion of control dependence to data dependence. In Proceedings of the Tenth Annual ACM Symposium on Principles of Programming Languages (Austin, Tx., Jan. 1983). ACM, New York, 1983.

[4]

ALLEN, J. R. Dependence analysis for subscripted variables and its application to program transformations. Ph.D. dissertation, Dept. of Mathematical Sciences, Rice University, Houston, Tx., April 1983.

[5]

American National Standards Institute, Inc. Proposals approved for Fortran 8x. X3J3/S6.80 (preliminary document). ANSI, New York, Nov. 30, 1981.

[6]

BANERJEE, U. Data dependence in ordinary programs. Report 76-837, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Ill., Nov. 1976.

[7]

Burroughs Corporation. Implementation of FORTRAN. Burroughs Scientific Processor Brochure, 1977.

[8]

COCKE, J., AND KENNEDY, g. An algorithm for reduction of operator strength. Commun. ACM 20, 11 (Nov. 1977), 850-856.

[9]

COHAGEN, W. L. Vector optimization for the ASC. In Proceedings of the Seventh Annual Princeton Conference on Information Sciences and Systems (Dept. of Electrical Engineering, Princeton, N.J., 1973), pp. 169-174.

[10]

Cray Research, Inc. Cray-1 Computer System Reference Manual. Publication 2240004, Cray Research, Inc., Bloomington, Minn., 1976.

[11]

Cray Research, Inc. Cray-1 Computer System FORTRAN (CFT) Reference Manual. Publication 2240009, Cray Research, Inc., Mendota Heights, Minn., 1980.

[12]

Department of Energy, Advanced Computing Committee Language Working Group. FORTRAN language requirements, fourth report. Draft report, Department of Energy, Aug. 1979.

[13]

Floating Point Systems, Inc. AP-120 Programmers Reference Manual. Publication 860-7319- 000, Floating Point Systems, Inc., Beaverton, Ore., 1978.

[14]

GRIFFIN, H. Elementary Theory of Numbers. McGraw-Hill, New York, 1954.

[15]

HIGBEE, L. Vectorization and conversion of FORTRAN programs for the Cray-1 CFT compiler. Publication 2240207, Cray Research Inc., Mendota Heights, Minn., June 1979.

[16]

KNUTH, D. E. The Art of Computer Programming, Vol. 1: Fundamental Algorithms. Addison- Wesley, Reading, Mass., 1973.

[17]

KUCK, D.J. A survey of parallel machine organization and programming. Comput. Surv. 9, 1 (March 1977), 29-59.

[18]

KUCK, D.J. The Structure of Computers and Computations, Vol. 1, Wiley, New York, 1978.

[19]

KUCK, D. J., KUHN, R. H., LEASURE, B., PADUA, D. A., AND WOLFE, M. Compiler transformation of dependence graphs. In Conference Record of the Eighth ACM Symposium on Principles of Programming Languages (Williamsburg, Va., Jan. 1981). ACM, New York, 1981.

[20]

KUCK, D. J., KUHN, R. H., LEASURE, B., AND WOLFE, M. The structure of an advanced vectorizer for pipelined processors. In Proceedings of the IEEE Computer Society Fourth International Computer Software and Applications Conference (Chicago, Oct. 1980). IEEE, New York, 1980.

[21]

LEASURE, B. R. Compiling serial languages for parallel machines. Report-76-805, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Ill., Nov. 1976.

[22]

LEVESQUE, J. M. Application of the Vectorizer for effective use of high-speed computers. In High Speed Computer and Algorithm Organization, D. J. Kuck, D. H. Lawrie, and A. H. Sameh, Eds. Academic Press, New York, 1977, pp. 447-449.

[23]

MCCLUSKEY, E.g. Minimization of Boolean functions. Bell System Tech. J. 35, 5 (Nov. 1956), 1417-1444.

[24]

MURAOKA, Y. Parallelism exposure and exploitation in programs. Report 71-414, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana Ill., Feb. 1971.

[25]

MYSZEWSKI, M. The Vectorizer System: Current and proposed capabilities. Report CA-17809- 1511 Massachusetts Computer Associates, Inc., Wakefield, Mass., Sept. 1978.

[26]

PAUL, G., private communication, 1980.

[27]

PAUL, G., ANO WILSON, M. W. An Introduction to VECTRAN and its use in scientific applications programming. In Proceedings of the LASL Workshop on Vector and Parallel Processors. (Los Alamos, N.M., Sept. 1978). University of California, Los Alamos Scientific Laboratory, Los Alamos, N.M., 1978, pp. 176-204.

[28]

PAUL, G., AND WILSON, M.W. The VECTRAN language: An experimental language for vector/ matrix array processing. IBM Palo Alto Scientific Center Report G320-3334, Palo Alto, Calif., Aug. 1975.

[29]

QUINE, W.V. The problem of simplifying truth functions. Am. Math. Monthly 59, 8 (Oct. 1952), 521-531.

[30]

RUSSELL, R.M. The CRAY-1 computer system. Cornmun. ACM 21, I (Jan. 1978), 63-72.

[31]

TARZAN, R.E. Depth first search and linear graph algorithms. SlAM J. Comput. 1, 2 (1972), 146-160.

[32]

TOWLE, R.A. Control and data dependence for program transformations. Ph.D. dissertation, Report. 76-788, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Ill., March 1976.

[33]

WEOEL, D. Fortran for the Texas Instruments ASC system. ACM SIGPLAN Not. 10, 3 (March 1975), 119-132.

[34]

WETHERELL, C. Array processing for FORTRAN. Report CID-30175, Lawrence Livermore Laboratory, Livermore, Calif., April 1979.

[35]

WIq~MAYER, W. R. Array processor provides high throughput rates. Comput. Des~n (March 1978).

[36]

WOLFE, M.J. Techniques for improving the inherent parallelism in programs. Report 78-929, Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, Ill., July 1978.

Cited By

Gartmann AMüller MEvans KSchenk O(2024)Using Read-After-Read Dependencies to Control Task-GranularityProceedings of the Platform for Advanced Scientific Computing Conference10.1145/3659914.3659921(1-12)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3659914.3659921
Zhao WYuan LYan BMa PZhang YWang LWang Z(2024)Stencil Computation with Vector Outer ProductProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656611(247-258)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3650200.3656611
Zhou HHan QShi HZhang YYao JTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Boost Linear Algebra Computation Performance via Efficient VNNI UtilizationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651333(149-163)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651333
Show More Cited By

Index Terms

Automatic translation of FORTRAN programs to vector form

Recommendations

Cedar Fortran and other Vector and parallel Fortran dialects
Supercomputing '88: Proceedings of the 1988 ACM/IEEE conference on Supercomputing

The introduction of vector processors and multiprocessors punctuate the most dramatic changes in Fortran and its dialects. The emerging generation of supercomputers utilize both vector processing and multiprocessing simultaneously. The challenge is to ...
PCFORT: a Fortran-to-Pcode translator
Postprocessor for structured FORTRAN
ACMSE '76: Proceedings of the 14th annual ACM Southeast Regional Conference

Structured FORTRAN is an extension of FORTRAN language with constructs like DO WHILE, CASE, IF THEN ELSE, etc., that will allow people to write structured programs in FORTRAN. Many preprocessors have been. developed for various versions of structured ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 9, Issue 4

Oct. 1987

213 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/29873

Editor:
Susan L. Graham

Issue’s Table of Contents

Copyright © 1987 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1987

Published in TOPLAS Volume 9, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

542
Total Citations
View Citations
2,075
Total Downloads

Downloads (Last 12 months)202
Downloads (Last 6 weeks)30

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Gartmann AMüller MEvans KSchenk O(2024)Using Read-After-Read Dependencies to Control Task-GranularityProceedings of the Platform for Advanced Scientific Computing Conference10.1145/3659914.3659921(1-12)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3659914.3659921
Zhao WYuan LYan BMa PZhang YWang LWang Z(2024)Stencil Computation with Vector Outer ProductProceedings of the 38th ACM International Conference on Supercomputing10.1145/3650200.3656611(247-258)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3650200.3656611
Zhou HHan QShi HZhang YYao JTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Boost Linear Algebra Computation Performance via Efficient VNNI UtilizationProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651333(149-163)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651333
Thomas SBornholt JTsafrir DMUSUVATHI MGupta RAbu-Ghazaleh N(2024)Automatic Generation of Vectorizing Compilers for Customizable Digital Signal ProcessorsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3617232.3624873(19-34)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3617232.3624873
Mustafa DAlkhasawneh RObeidat FShatnawi A(2024)MIMD Programs Execution Support on SIMD Machines: A Holistic SurveyIEEE Access10.1109/ACCESS.2024.337299012(34354-34377)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3372990
Wei HZhang YLiu CHuang QJia PXu ZGuo Y(2024)The Strategic Random Search (SRS) – A new global optimizer for calibrating hydrological modelsEnvironmental Modelling & Software10.1016/j.envsoft.2023.105914172:COnline publication date: 17-Apr-2024
https://dl.acm.org/doi/10.1016/j.envsoft.2023.105914
Tayeb HPaillat LBramas B(2023)Autovesk: Automatic Vectorized Code Generation from Unstructured Static Kernels Using Graph TransformationsACM Transactions on Architecture and Code Optimization10.1145/363170921:1(1-25)Online publication date: 9-Nov-2023
https://dl.acm.org/doi/10.1145/3631709
Root AAhmad MSharlet DAdams AKamil SRagan-Kelley JAamodt TSwift MJerger N(2023)Fast Instruction Selection for Fast Digital Signal ProcessingProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 410.1145/3623278.3624768(125-137)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3623278.3624768
Kim JRoss KSedlar EStadler L(2023)AMULET: Adaptive Matrix-Multiplication-Like TasksProceedings of the 19th International Workshop on Data Management on New Hardware10.1145/3592980.3595301(77-81)Online publication date: 18-Jun-2023
https://dl.acm.org/doi/10.1145/3592980.3595301
Bagnall AStewart GBanerjee A(2023)Formally Verified Samplers from Probabilistic Programs with Loops and ConditioningProceedings of the ACM on Programming Languages10.1145/35912207:PLDI(1-24)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591220
Show More Cited By

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents