Optimized unrolling of nested loops

ABSTRACT

In this paper, we address the problems of automatically selecting unroll factors for perfectly nested loops, and generating compact code for the selected unroll factors. Compared to past work, the contributions of our work include a) a more detailed cost model that includes ILP and 1-cache considerations, b) a new code generation algorithm for unrolling nested loops that generates more compact code (with fewer remainder loops) than the unroll-and-jam transformation, and c) a new algorithm for efficiently enumerating feasible unroll vectors.Our experimental results confirm the wide applicability of our approach by showing a 2.2X speedup on matrix multiply, and an average 1.08X speedup on seven of the SPEC95fp benchmarks (with a 1.2X speedup for two benchmarks). These speedups are significant because the baseline compiler used for comparison is the IBM XL Fortran product compiler which generates high quality code with unrolling and software pipelining of innermost loops enabled. Larger performance improvements due to unrolling of nested loops can be expected on processors that have larger numbers of registers and larger degrees of instruction-level parallelism than the processor used for our measurements (PowerPC 604).

REFERENCES

• 1: Michael J. Alexander, Mark W. Barley, Bruce R.. Childers, Jack W. Davidson, and Sanjay Jinturkar. Memory bandwidth optimizations for wide-bus machines. Proceedings of the ~fith Hawaii International Conference on System Sciences, Wailea, Hawaii, pages 466-475, January 1993.
• 2: F. E. Allen and J. Cocke. A catalogue of optimizing transformations. In Design and Optimization of Compilers, pages 1-30. Prentice-Hall, 1972.
• 3: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
• 4: Mauricio Breternitz, Michael Lai, Vivek Sarkar, and Barbara Simons. Compiler Solutions for the Stale-Data and False-Sharing Problems. Technical report, IBM Santa Teresa Laboratory, April 1993. TR 03.466.
• 5: David Callahan , Steve Carr , Ken Kennedy, Improving register allocation for subscripted variables, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.53-65, June 1990, White Plains, New York, United States
• 6: Steve Carr , Yiping Guan, Unroll-and-jam using uniformly generated sets, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.349-357, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 7: Steve Carr , Ken Kennedy, Improving the ratio of memory operations to floating-point operations in loops, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.6, p.1768-1810, Nov. 1994 [doi>10.1145/197320.197366]
• 8: Steve Carr , Ken Kennedy, Scalar replacement in the presence of conditional control flow, Software—Practice & Experience, v.24 n.1, p.51-77, Jan. 1994 [doi>10.1002/spe.4380240104]
• 9: The Standard Performance Evaluation Corporation. SPEC CPU95 Benchmarks. http://open.specbench.org/osg/cpu95/, 1997.
• 10: Jack W. Davidson , Sanjay Jinturkar, Aggressive Loop Unrolling in a Retargetable Optimizing Compiler, Proceedings of the 6th International Conference on Compiler Construction, p.59-73, April 24-26, 1996
• 11: J. J. Dongarra and A. R. Hinds. Unrolling Loops in Fortran. Software - Practice and Exper/ence, 9(3):219- 226, March 1979.
• 12: Jeanne Ferrante , Vivek Sarkar , W. Thrash, On Estimating and Enhancing Cache Effectiveness, Proceedings of the Fourth International Workshop on Languages and Compilers for Parallel Computing, p.328-343, August 07-09, 1991
• 13: Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.37-47, June 17-22, 1984, Montreal, Canada
• 14: Reese B. Jones , Vicki H. Allan, Software pipelining: an evaluation of enhanced pipelining, Proceedings of the 24th annual international symposium on Microarchitecture, p.82-92, September 1991, Albuquerque, New Mexico, Puerto Rico [doi>10.1145/123465.123481]
• 15: Daniel M. Lavery , Wen-Mei W. Hwu, Unrolling-based optimizations for modulo scheduling, Proceedings of the 28th annual international symposium on Microarchitecture, p.327-337, November 29-December 01, 1995, Ann Arbor, Michigan, United States
• 16: Todd Carl Mowry, Tolerating latency through software-controlled data prefetching, Stanford University, Stanford, CA, 1995
• 17: Allan Kennedy Porterfield , K. W. Kennedy, Software methods for improvement of cache performance on supercomputer applications, 1989
• 18: B. Ramakrishna Rau, Iterative modulo scheduling: an algorithm for software pipelining loops, Proceedings of the 27th annual international symposium on Microarchitecture, p.63-74, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192731]
• 19: V. Sarkar, Automatic partitioning of a program dependence graph into parallel tasks, IBM Journal of Research and Development, v.35 n.5-6, p.779-804, Sept./Nov. 1991
• 20: V. Sarkar, Automatic selection of high-order transformations in the IBM XL FORTRAN compilers, IBM Journal of Research and Development, v.41 n.3, p.233-264, May 1997
• 21: Vivek Sarkar and Barbara Simons. Don't Waste Those Cycles: An In-Depth Look at Scheduling Instructions in Basic Blocks and Loops. Video Lecture in University Video Communication's Distinguished Lecture Series IX, August 1994.
• 22: Vivek Sarkar , Radhika Thekkath, A general framework for iteration-reordering loop transformations, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.175-187, June 15-19, 1992, San Francisco, California, United States
• 23: Bogong Su , Shiyuan Ding , Jian Wang , Jinshi Xia, GURPR—a method for global software pipelining, Proceedings of the 20th annual workshop on Microprogramming, p.88-96, December 01-04, 1987, Colorado Springs, Colorado, United States [doi>10.1145/255305.255322]
• 24: Shlomo Weiss , James E. Smith, A study of scalar compilation techniques for pipelined supercomputers, Proceedings of the second international conference on Architectual support for programming languages and operating systems, p.105-109, October 1987, Palo Alto, California, United States
• 25: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 26: Michael Joseph Wolfe, Optimizing Supercompilers for Supercomputers, MIT Press, Cambridge, MA, 1990

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Concurrent programming structures
      D.3.4 Processors
          Subjects: Code generation

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Experimentation, Languages, Measurement, Performance, Theory