An array operation synthesis scheme to optimize Fortran 90 programs

ABSTRACT

An increasing number of programming languages, such as Fortran 90 and APL, are providing a rich set of intrinsic array functions and array expressions. These constructs which constitute an important part of data parallel languages provide excellent opportunities for compiler optimizations. In this paper, we present a new approach to combine consecutive data access patterns of array constructs into a composite access function to the source arrays. Our scheme is based on the composition of access functions, which is similar to a composition of mathematic functions. Our new scheme can handle not only data movements of arrays of different numbers of dimensions and segmented array operations but also masked array expressions and multiple sources array operations. As a result, our proposed scheme is the first synthesis scheme which can synthesize Fortran 90 RESHAPE, EOSHIFT, MERGE, and WHERE constructs together. Experimental results show speedups from 1.21 to 2.95 for code fragments from real applications on a Sequent multiprocessor machine by incorporating the proposed optimizations.

REFERENCES

• 1: Jeanne C. Adams , Walter S. Brainerd , Jeanne T. Martin , Brian T. Smith , Jerrold L. Wagener, Fortran 90 handbook: complete ANSI/ISO reference, Intertext Publications, Inc.,/McGraw-Hill, Inc., New York, NY, 1993
• 2: Walter S. Brainerd , Charles Goldberg , Jeanne Adams, Programmer's guide to Fortran 90, Intertext Publications, Inc.,/McGraw-Hill, Inc., New York, NY, 1990
• 3: Timothy A. Budd, An APL Compiler for a Vector Processor, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.297-313, July 1984 [doi>10.1145/579.357248]
• 4: Leo J. Guibas , Douglas K. Wyatt, Compilation and delayed evaluation in APL, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-8, January 23-25, 1978, Tucson, Arizona [doi>10.1145/512760.512761]
• 5: Dz-ching Ju, Chuan-lin Wu, and Paul Carini, The Synthesis of Array Functions and its Use in Parallel Computation, Proceeding of International Conference on Parallel Processing, pp. 293-296, 1992.
• 6: Dz-Ching Ju, The optimization and parallelization of array language programs, University of Texas at Austin, Austin, TX, 1992
• 7: J. K. Lee , D. Gannon, Object oriented parallel programming: experiments and results, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.273-282, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.105186]
• 8: C. L. Liu. Elements of Discrete mathematics, Second Edition, 1985.
• 9: A. Mohamer, G. Fox, G. Laszewski, M. Parashar, T. Haupt, K. Mills, Y. Lu, N. Lin, N. and Yeh. Applications Benchmark Set for Fortran-D and Hzgh Performance Fortran, Technical Report SCCS327, NPAC, Syracuse University.
• 10: J.R. Rice, J. Jing. Problems to Test Parallel and Vector Languages, Purdue University Tech. Rep. CSD-TR- 1016, 1990.
• 11: High Performance Fortran Forum, High Performance Fortran Language Specification, Technical Report CRPC-TR92225, Rice University, Houston, TX, 1993.
• 12: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

INDEX TERMS

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

General Terms:
Theory