Increasing temporal locality with skewing and recursive blocking

ABSTRACT

We present a strategy, called recursive prismatic time skewing, that increase temporal reuse at all memory hierarchy levels, thus improving the performance of scientific codes that use iterative methods. Prismatic time skewing partitions iteration space of multiple loops into skewed prisms with both spatial and temporal (or convergence) dimensions. Novel aspects of this work include: multi-dimensional loop skewing; handling carried data dependences in the skewed loops without additional storage; bi-directional skewing to accommodate periodic boundary conditions; and an analysis and transformation strategy that works inter-procedurally. We combine prismatic skewing with a recursive blocking strategy to boost reuse at all levels in a memory hierarchy. A preliminary evaluation of these techniques shows significant performance improvements compared both to original codes and to methods described previously in the literature. With an inter-procedural application of our techniques, we were able to reduce total primary cache misses of a large application code by 27% and secondary cache misses by 119%.

REFERENCES

• 1: Vikram Adve , Guohua Jin , John Mellor-Crummey , Qing Yi, High performance Fortran compilation techniques for parallelizing scientific codes, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-23, November 07-13, 1998, San Jose, CA
• 2: Vikram Adve , John Mellor-Crummey, Using integer sets for data-parallel program analysis and optimization, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.186-198, June 17-19, 1998, Montreal, Quebec, Canada
• 3: Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Synthesizing transformations for locality enhancement of imperfectly-nested loop nests, Proceedings of the 14th international conference on Supercomputing, p.141-152, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335245]
• 4: Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Tiling imperfectly-nested loop nests, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.31-es, November 04-10, 2000, Dallas, Texas, United States
• 5: Nawaaz Ahmed , Keshav Pingali, Automatic Generation of Block-Recursive Codes, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.368-378, August 29-September 01, 2000
• 6: Peter N. Brown , Robert D. Falgout , Jim E. Jones, Semicoarsening Multigrid on Distributed Memory Machines, SIAM Journal on Scientific Computing, v.21 n.5, p.1823-1834, April 2000 [doi>10.1137/S1064827598339141]
• 7: 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
• 8: S. Carr , K. Kennedy, Compiler blockability of numerical algorithms, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.114-124, November 16-20, 1992, Minneapolis, Minnesota, United States
• 9: 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]
• 10: Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.279-290, June 18-21, 1995, La Jolla, California, United States
• 11: Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, Proceedings of the sixth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.206-216, June 18-21, 1997, Las Vegas, Nevada, United States
• 12: Mary W. Hall , Ken Kennedy , Kathryn S. McKinley, Interprocedural transformations for parallel code generation, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.424-434, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.126055]
• 13: Induprakas Kodukula , Nawaaz Ahmed , Keshav Pingali, Data-centric multi-level blocking, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.346-357, June 16-18, 1997, Las Vegas, Nevada, United States
• 14: Monica D. Lam , Edward E. Rothberg , Michael E. Wolf, The cache performance and optimizations of blocked algorithms, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.63-74, April 08-11, 1991, Santa Clara, California, United States
• 15: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 16: Nicholas Mitchell , Karin Högstedt , Larry Carter , Jeanne Ferrante, Quantifying the Multi-Level Nature of Tiling Interactions, International Journal of Parallel Programming, v.26 n.6, p.641-670, December 1998 [doi>10.1023/A:1018782528453]
• 17: H. Prokop. Cache-oblivious algorithms. Master's thesis, Department of Electrical Engineering, MIT, June 1999.
• 18: Yonghong Song , Zhiyuan Li, A Compiler Framework for Tiling Imperfectly-Nested Loops, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.185-200, August 04-06, 1999
• 19: Yonghong Song , Zhiyuan Li, New tiling techniques to improve cache temporal locality, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.215-228, May 01-04, 1999, Atlanta, Georgia, United States
• 20: Michael Wolfe, Loop skewing: the wavefront method revisited, International Journal of Parallel Programming, v.15 n.4, p.279-293, Oct. 1986 [doi>10.1007/BF01407876]
• 21: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 22: D. Wonnacott. Time skewing: A value-based approach to optimizing for memory locality. Submitted for publication.
• 23: Qing Yi , Vikram Adve , Ken Kennedy, Transforming loops to recursion for multi-level memory hierarchies, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.169-181, June 18-21, 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Memory design

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Algorithms, Design, Performance