Transforming FORTRAN DO loops to improve performance on vector architectures

ABSTRACT

The performance of programs executing on vector computers is significantly improved when the number of accesses to memory can be reduced. Unrolling Fortran DO loops, followed by substitutions and eliminations in the unrolled code, can reduce the number of loads and stores. In this paper we characterize the unrolling transformation and associated transformations of Fortran DO loops and describe a set of software tools to carry out these transformations. The tools use the machinery available in Toolpack and have been integrated into that environment. We describe the results of applying these tools to a collection of linear algebra subroutines.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, Principles of Compiler Design (Addison-Wesley series in computer science and information processing), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 2: ANSI X3.9-1978. Programming Language FORTRAN. American National Standards Institute, Inc., New York, 1978.
• 3: COWELL, W. R., HAGUE, S. J., A~qD ILES, R. M.J. Toolpack/1 Introductory Guide. Publication NP1007, Numerical Algorithms Group, Downers Grove, Ill., and Oxford, U.K., 1985.
• 4: COWELL, W. R. The Toolpack Tools ISTUD, ISTCD, and ISTSB: Guide for Users and installers. MCS-TM-74, Argonne National Lab., Argonne, Ill., 1986 (also included on the Toolpack distribution tape).
• 5: DALY, C., AND DU CROZ, J. J. Performance of a subroutine library on vector processing machines. In Vector and Parallel Processors in Computational Science, I. S. Duff and J. K. Reid, Eds. North-Holland, Amsterdam, The Netherlands, 1985.
• 6: Jack J. Dongarra , Stanley C. Eisenstat, Squeezing the most out of an algorithm in CRAY FORTRAN, ACM Transactions on Mathematical Software (TOMS), v.10 n.3, p.219-230, Sept. 1984 [doi>10.1145/1271.319413]
• 7: DONGARRA, J. J., AND HINDS, A. R. Unrolling loops in FORTRAN. Softw. Pract. Exper. 9 (1979), 219-226.
• 8: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Array and vector processors

  D. Software
  D.2 SOFTWARE ENGINEERING

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Languages, Performance