Automatic translation of FORTRAN programs to vector form

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: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 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: J. R. Allen , Ken Kennedy , Carrie Porterfield , Joe Warren, Conversion of control dependence to data dependence, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.177-189, January 24-26, 1983, Austin, Texas [doi>10.1145/567067.567085]
• 4: John Randal Allen, Dependence analysis for subscripted variables and its application to program transformations, 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: John Cocke , Ken Kennedy, An algorithm for reduction of operator strength, Communications of the ACM, v.20 n.11, p.850-856, Nov. 1977 [doi>10.1145/359863.359888]
• 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: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 17: David J. Kuck, A Survey of Parallel Machine Organization and Programming, ACM Computing Surveys (CSUR), v.9 n.1, p.29-59, March 1977 [doi>10.1145/356683.356686]
• 18: David L. Kuck, Structure of Computers and Computations, John Wiley & Sons, Inc., New York, NY, 1978
• 19: D. J. Kuck , R. H. Kuhn , D. A. Padua , B. Leasure , M. Wolfe, Dependence graphs and compiler optimizations, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.207-218, January 26-28, 1981, Williamsburg, Virginia [doi>10.1145/567532.567555]
• 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: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 31: TARZAN, R.E. Depth first search and linear graph algorithms. SlAM J. Comput. 1, 2 (1972), 146-160.
• 32: Ross Albert Towle, Control and data dependence for program transformations., 1976
• 33: Dorothy Wedel, Fortran for the Texas Instruments ASC system, ACM SIGPLAN Notices, v.10 n.3, p.119-132, March 1975
• 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.

INDEX TERMS

Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Languages