Parametric multi-level tiling of imperfectly nested loops

ABSTRACT

Tiling is a crucial loop transformation for generating high performance code on modern architectures. Efficient generation of multi-level tiled code is essential for maximizing data reuse in systems with deep memory hierarchies. Tiled loops with parametric tile sizes (not compile-time constants) facilitate runtime feedback and dynamic optimizations used in iterative compilation and automatic tuning. Previous parametric multi-level tiling approaches have been restricted to perfectly nested loops, where all assignment statements are contained inside the innermost loop of a loop nest. Previous solutions to tiling for imperfect loop nests have only handled fixed tile sizes. In this paper, we present an approach to parametric multi-level tiling of imperfectly nested loops. The tiling technique generates loops that iterate over full rectangular tiles, making them amenable to compiler optimizations such as register tiling. Experimental results using a number of computational benchmarks demonstrate the effectiveness of the developed tiling approach.

REFERENCES

• 1: PrimeTile: A Parametric Multi-Level Tiler for Imperfect Loop Nests. http://primetile.sourceforge.net.
• 2: 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
• 3: Nawaaz Ahmed , Nikolay Mateev , Keshav Pingali, Synthesizing Transformations for Locality Enhancement of Imperfectly-Nested Loop Nests, International Journal of Parallel Programming, v.29 n.5, p.493-544, October 2001 [doi>10.1023/A:1012293814832]
• 4: 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
• 5: Workshop on Automatic Tuning for Petascale Systems. http://cscads.rice.edu/workshops/summer08/autotuning.
• 6: C. Bastoul. Efficient code generation for automatic parallelization and optimization. In ISPDC, page 23, 2003.
• 7: Cedric Bastoul, Code Generation in the Polyhedral Model Is Easier Than You Think, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.7-16, September 29-October 03, 2004 [doi>10.1109/PACT.2004.11]
• 8: U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan. A practical automatic polyhedral program optimization system. In PLDI'08, 2008.
• 9: Pierre Boulet , Alain Darte , Tanguy Risset , Yves Robert, (Pen)-ultimate tiling?, Integration, the VLSI Journal, v.17 n.1, p.33-51, Aug. 1994 [doi>10.1016/0167-9260(94)90019-1]
• 10: 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
• 11: Chun Chen , Jacqueline Chame , Mary Hall, Combining Models and Guided Empirical Search to Optimize for Multiple Levels of the Memory Hierarchy, Proceedings of the international symposium on Code generation and optimization, p.111-122, March 20-23, 2005 [doi>10.1109/CGO.2005.10]
• 12: C. Chen, J. Chame, and M. Hall. Chill: A framework for composing high-level loop transformations. Technical Report 08-897, USC Computer Science Technical Report, June 2008.
• 13: CLooG: The Chunky Loop Generator. http://www.cloog.org.
• 14: 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
• 15: P. Feautrier. Dataflow analysis of array and scalar references. IJPP, 20(1):23--53, 1991.
• 16: G. Goumas, M. Athanasaki, and N. Koziris. An Efficient Code Generation Technique for Tiled Iteration Spaces. IEEE Trans. Parallel Distrib. Syst., 14(10):1021--1034, 2003.
• 17: M. Griebl. Automatic Parallelization of Loop Programs for Distributed Memory Architectures. FMI, University of Passau, 2004. Habilitation Thesis.
• 18: A. Hartono, M. Baskaran, C. Bastoul, A. Cohen, S. Krishnamoorthy, B. Norris, J. Ramanujam, and P. Sadayappan. Primetile: A parametric multi-level tiler for imperfect loop nests. Technical Report OSU-CISRC-2/09-TR04, The Ohio State University, Feb. 2009.
• 19: HiTLoG: Hierarchical Tiled Loop Generator. Available at http://www.cs.colostate.edu/MMAlpha/tiling/.
• 20: Karin Högstedt , Larry Carter , Jeanne Ferrante, Selecting tile shape for minimal execution time, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.201-211, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305641]
• 21: F. Irigoin , R. Triolet, Supernode partitioning, Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.319-329, January 10-13, 1988, San Diego, California, United States [doi>10.1145/73560.73588]
• 22: Marta Jiménez , José M. Llabería , Agustín Fernández, Register tiling in nonrectangular iteration spaces, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.4, p.409-453, July 2002 [doi>10.1145/567097.567101]
• 23: M. Jiménez, J. Llabería, and A. Fernández. A cost-effective implementation of multilevel tiling. IEEE Trans. Parallel Distrib. Syst., 14(10):1006--1020, 2003.
• 24: D. Kim and S. Rajopadhye. Parameterized tiling for imperfectly nested loops. Technical Report CS-09-101, Colorado State University, Department of Computer Science, February 2009.
• 25: DaeGon Kim , Lakshminarayanan Renganarayanan , Dave Rostron , Sanjay Rajopadhye , Michelle Mills Strout, Multi-level tiling: M for the price of one, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362691]
• 26: Amy Wingmui Lim , Monica S. Lam, Improving parallelism and data locality with affine partitioning, 2001
• 27: Amy W. Lim , Gerald I. Cheong , Monica S. Lam, An affine partitioning algorithm to maximize parallelism and minimize communication, Proceedings of the 13th international conference on Supercomputing, p.228-237, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305197]
• 28: Amy W. Lim , Monica S. Lam, Maximizing parallelism and minimizing synchronization with affine partitions, Parallel Computing, v.24 n.3-4, p.445-475, May, 1998 [doi>10.1016/S0167-8191(98)00021-0]
• 29: Amy W. Lim , Shih-Wei Liao , Monica S. Lam, Blocking and array contraction across arbitrarily nested loops using affine partitioning, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.103-112, June 2001, Snowbird, Utah, United States
• 30: Pluto: A polyhedral automatic parallelizer and locality optimizer for multicores. Available at http://pluto-compiler.sourceforge.net.
• 31: 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]
• 32: Fabien Quilleré , Sanjay Rajopadhye , Doran Wilde, Generation of Efficient Nested Loops from Polyhedra, International Journal of Parallel Programming, v.28 n.5, p.469-498, Oct. 2000 [doi>10.1023/A:1007554627716]
• 33: J. Ramanujam and P. Sadayappan. Tiling multidimensional iteration spaces for multicomputers. JPDC, 16(2):108--230, 1992.
• 34: Lakshminarayanan Renganarayanan , DaeGon Kim , Sanjay Rajopadhye , Michelle Mills Strout, Parameterized tiled loops for free, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 35: Lakshminarayanan Renganarayana , Sanjay Rajopadhye, A Geometric Programming Framework for Optimal Multi-Level Tiling, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.18, November 06-12, 2004 [doi>10.1109/SC.2004.3]
• 36: Gabriel Rivera , Chau-Wen Tseng, Locality optimizations for multi-level caches, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.2-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331534]
• 37: Jack Dongarra , Robert Schreiber, Automatic Blocking of Nested Loops, University of Tennessee, Knoxville, TN, 1990
• 38: 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
• 39: A. Tiwari, C. Chen, J. Chame, M. Hall, and J. Hollingsworth. Scalable autotuning framework for compiler optimization. In IPDPS'09, May 2009.
• 40: TLoG: A Parametrized Tiled Loop Generator. Available at http://www.cs.colostate.edu/MMAlpha/tiling/.
• 41: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA
• 42: R. Whaley, A. Petitet, and J. Dongarra. Automated Empirical Optimizations of Software and the ATLAS Project. Parallel Computing Journal, 2000.
• 43: David B. Whalley, Tuning High Performance Kernels through Empirical Compilation, Proceedings of the 2005 International Conference on Parallel Processing, p.89-98, June 14-17, 2005 [doi>10.1109/ICPP.2005.77]
• 44: Jingling Xue, Loop tiling for parallelism, Kluwer Academic Publishers, Norwell, MA, 2000
• 45: Qing Yi , Ken Kennedy , Vikram Adve, Transforming Complex Loop Nests for Locality, The Journal of Supercomputing, v.27 n.3, p.219-264, March 2004 [doi>10.1023/B:SUPE.0000011386.69245.f5]

INDEX TERMS

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

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

General Terms:
Algorithms, Design, Performance

Keywords:
imperfectly nested loops, parametric tiling