Transformations for imperfectly nested loops

ABSTRACT

Loop transformations are critical for compiling high-performance code for modern computers. Existing work has focused on transformations for perfectly nested loops (that is, loops in which all assignment statements are contained within the innermost loop of a loop nest). In practice, most loop nests, such as those in matrix factorization codes, are imperfectly nested. In some programs, imperfectly nested loops can be transformed into perfectly nested loops by loop distribution, but this is not always legal. In this paper, we present an approach to transforming imperfectly nested loops directly. Our approach is an extension of the linear loop transformation framework for perfectly nested loops, and it models permutation, reversal, skewing, scaling, alignment, distribution and jamming. We also give a completion procedure which generates a complete transformation from a partial transformation.

REFERENCES

• 1: Corinne Ancourt , François Irigoin, Scanning polyhedra with DO loops, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.39-50, April 21-24, 1991, Williamsburg, Virginia, United States
• 2: Eduard Ayguadé , Jordi Torres, Partitioning the statement per iteration space using non-singular matrices, Proceedings of the 7th international conference on Supercomputing, p.407-415, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.166021]
• 3: Utpal Banerjee, A theory of loop permutations, Selected papers of the second workshop on Languages and compilers for parallel computing, p.54-74, May 1990, Urbana, Illinois, United States
• 4: Uptal Banerjee. Unimodular transformations of double loops. In Languages and compilers for parallel computing, pages 192-219, 1990.
• 5: W. Blume, R. Eigenmann, K. Faigin, J. Grout, J. Hoeflinger, D. Padua, P. Petersen, W. Pottenger, L. Rauchwerger, P. Tu, and S. Weatherford. Polaris: The next generation in parallelizing compilers. Technical Report 1375, Center for Supercomputing Research and Development (CSRD), University of Illinois Urbana-Champaign.
• 6: Paul Feautrier, Some efficient solutions to the affine scheduling problem: I. One-dimensional time, International Journal of Parallel Programming, v.21 n.5, p.313-348, Oct. 1992 [doi>10.1007/BF01407835]
• 7: Paul Feautrier. Some efficient solutions to the affine scheduling problem - part ii: multi-dimensional time. International Journal of Parallel Programming, December 1992.
• 8: W. Kelly , W. Pugh , E. Rosser, Code generation for multiple mappings, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.332, February 06-09, 1995
• 9: S. Y. Kung, VLSI array processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 10: Wei Li , Keshav Pingali, A singular loop transformation framework based on non-singular matrices, International Journal of Parallel Programming, v.22 n.2, p.183-205, April 1994 [doi>10.1007/BF02577874]
• 11: William Pugh, A practical algorithm for exact array dependence analysis, Communications of the ACM, v.35 n.8, p.102-114, Aug. 1992 [doi>10.1145/135226.135233]
• 12: J. Ramanujam. Optimal code parallelization using unimodular transformations. In Proceedings of Supercomputing, 1992.
• 13: M. E. Wolf and M. S. Lam. An algorithmic approach to compound loop transformations. In Languages and compilers for parallel computing, pages 243-273, 1990.
• 14: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Languages, Performance, Theory