Profitable loop fusion and tiling using model-driven empirical search

ABSTRACT

Loop fusion and tiling are both recognized as effective transformations for improving memory performance of scientific applications. However, because of their sensitivity to the underlying cache architecture and their interaction with each other it is difficult to determine a good heuristic for applying these transformations profitably across architectures. In this paper, we present a model-guided empirical tuning strategy for profitable application of loop fusion and tiling. Our strategy consists of a detailed cost model that characterizes the interaction between the two transformations at different levels of the memory hierarchy. The novelty of our approach is in exposing key architectural parameters within the model for automatic tuning through empirical search. Preliminary experiments with a set of applications on four different platforms show that our strategy achieves significant performance improvement over fully optimized code generated by state-of-the-art commercial compilers. The time spent in searching for the best parameters is considerably less than with other search strategies.

REFERENCES

• 1: Jeff Bilmes , Krste Asanovic , Chee-Whye Chin , Jim Demmel, Optimizing matrix multiply using PHiPAC: a portable, high-performance, ANSI C coding methodology, Proceedings of the 11th international conference on Supercomputing, p.340-347, July 07-11, 1997, Vienna, Austria [doi>10.1145/263580.263662]
• 2: 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]
• 3: 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
• 4: K. Cooper, D. Subramanian, and L. Torczon. Adaptive optimizing compilers for the 21st century. In Proceedings of the Los Alamos Computer Science Institute Second Annual Symposium, Santa Fe, NM, Oct. 2001.
• 5: C. Ding and K. Kennedy. Resource-constrained loop fusion. Technical report, Dept. of Computer Science, Rice University, Oct. 2000.
• 6: Chen Ding , Ken Kennedy, Improving Effective Bandwidth through Compiler Enhancement of Global Cache Reuse, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.38, April 23-27, 2001
• 7: Matteo Frigo, A fast Fourier transform compiler, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.169-180, May 01-04, 1999, Atlanta, Georgia, United States
• 8: Guang R. Gao , R. Olsen , Vivek Sarkar , Radhika Thekkath, Collective Loop Fusion for Array Contraction, Proceedings of the 5th International Workshop on Languages and Compilers for Parallel Computing, p.281-295, August 03-05, 1992
• 9: G. G. Fursin, M. F. P. O'Boyle, and P. M. W. Knijnenburg. Evaluating iterative compilation. In Proceedings of the Fifteenth International Workshop on Languages and Compilers for Parallel Computing, College Park, Maryland, July 2002.
• 10: Ken Kennedy, Fast greedy weighted fusion, Proceedings of the 14th international conference on Supercomputing, p.131-140, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335244]
• 11: P. M. W. Knijnenburg , T. Kisuki , K. Gallivan , M. F. P. O'Boyle, The effect of cache models on iterative compilation for combined tiling and unrolling: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.2-3, p.247-270, February 2004 [doi>10.1002/cpe.v16:2/3]
• 12: Prasad Kulkarni , Stephen Hines , Jason Hiser , David Whalley , Jack Davidson , Douglas Jones, Fast searches for effective optimization phase sequences, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 13: A. Lim and M. Lam. Cache optimizations with affine partitioning. In Proceedings of the Tenth SIAM Conference on Parallel Processing for Scientific Computing, Portsmouth, Virginia, Mar. 2001.
• 14: 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]
• 15: 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, Dec. 1998 [doi>10.1023/A:1018782528453]
• 16: A. Qasem and K. Kennedy. A cache-conscious profitability model for empirical tuning of loop fusion. In Proceedings of the Eighteenth International Workshop on Languages and Compilers for Parallel Computing, Hawthorne, NY, Oct. 2005.
• 17: A. Qasem, K. Kennedy, and J. Mellor-Crummey. Automatic tuning of whole applications using direct search and a performance-based transformation system. In Proceedings of the Los Alamos Computer Science Institute Second Annual Symposium, Santa Fe, NM, Oct. 2004.
• 18: Yonghong Song , Rong Xu , Cheng Wang , Zhiyuan Li, Data locality enhancement by memory reduction, Proceedings of the 15th international conference on Supercomputing, p.50-64, June 2001, Sorrento, Italy [doi>10.1145/377792.377806]
• 19: O. Temam , C. Fricker , W. Jalby, Cache interference phenomena, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.261-271, May 16-20, 1994, Nashville, Tennessee, United States
• 20: Spyridon Triantafyllis , Manish Vachharajani , Neil Vachharajani , David I. August, Compiler optimization-space exploration, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 21: S. Verdoolaege, M. Bruynooghe, G. Jenssens, and F. Catthoor. Multi-dimensional incremental loop fusion for data locality. In Proceedings of the IEEE International Conference on Application Specific Systems, Architectures, and Processors, June 2003.
• 22: 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
• 23: Michael E. Wolf , Dror E. Maydan , Ding-Kai Chen, Combining loop transformations considering caches and scheduling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.274-286, December 02-04, 1996, Paris, France
• 24: 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
• 25: Jianxin Xiong , Jeremy Johnson , Robert Johnson , David Padua, SPL: a language and compiler for DSP algorithms, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.298-308, June 2001, Snowbird, Utah, United States
• 26: Kamen Yotov , Xiaoming Li , Gang Ren , Michael Cibulskis , Gerald DeJong , Maria Garzaran , David Padua , Keshav Pingali , Paul Stodghill , Peng Wu, A comparison of empirical and model-driven optimization, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 27: H. You, K. Seymour, and J. Dongarra. An effective empirical search method for automatic software tuning. Technical report, University of Tennessee, Feb. 2005.
• 28: Y. Zhao, Q. Yi, K. Kennedy, D. Quinlan, and R. Vuduc. Parameterizing loop fusion for automated empirical tuning. Technical report, Lawrence Livermore National Laboratory, Dec. 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

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

General Terms:
Design, Experimentation, Performance

Keywords:
empirical tuning, loop fusion, memory hierarchy, tiling