A Geometric Programming Framework for Optimal Multi-Level Tiling

ABSTRACT

Determining the optimal tile size-one that minimizes the execution time-is a classical problem in compilation and performance tuning of loop kernels. Designing a model of the overall execution time of a tiled loop nest is an important subproblem. Both problems become harder when tiling is applied at multiple levels. We present a framework for determining the optimal tile sizes for a fully permutable, perfectly nested, rectangular loop with uniform dependences. Our framework supports multiple levels of tiling and uses a BSP style high level model for estimating the overall execution time of a loop program. In our framework, the problem of determining the optimal tile sizes, subject to memory capacity and bandwidth constraints, is modeled as a geometric program and transformed into a convex optimization problem, which can be solved efficiently. The model is validated through experimental results obtained by running twenty loop programs for different levels of tiling and different program and tile parameters. Our framework is very general and can also be used to solve the optimal tile size problem with many other models of execution time.

REFERENCES

• 1: Jaume Abella, Near-Optimal Loop Tiling by Means of Cache Miss Equations and Genetic Algorithms, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.568, August 18-21, 2002
• 2: [2] R Andonov, S. Balev, S Rajopadhye, and N. Yanev. Optimal semi-oblique tiling. IEEE Transactions on Parallel and Distributed Systems, 14(9):944-960, 2003.
• 3: 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]
• 4: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 5: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 6: [6] L. Carter, J. Ferrante, F. Hummel, B. Alpern, and K.S. Gatlin. Hierarchical tiling: A methodology for high performance. Technical Report CS96-508, UCSD, Nov. 1996.
• 7: Calin CaΒcaval , David A. Padua, Estimating cache misses and locality using stack distances, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782836]
• 8: Jacqueline Chame , Sungdo Moon, A tile selection algorithm for data locality and cache interference, Proceedings of the 13th international conference on Supercomputing, p.492-499, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305245]
• 9: Siddhartha Chatterjee , Erin Parker , Philip J. Hanlon , Alvin R. Lebeck, Exact analysis of the cache behavior of nested loops, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.286-297, June 2001, Snowbird, Utah, United States
• 10: Philippe Clauss, Counting solutions to linear and nonlinear constraints through Ehrhart polynomials: applications to analyze and transform scientific programs, Proceedings of the 10th international conference on Supercomputing, p.278-285, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237617]
• 11: 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
• 12: [12] R.J. Duffin, E.L. Peterson, and C. Zener. Geometric Programming - Theory and Applications. John Wiley, 1967.
• 13: 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
• 14: Somnath Ghosh , Margaret Martonosi , Sharad Malik, Cache miss equations: a compiler framework for analyzing and tuning memory behavior, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.703-746, July 1999 [doi>10.1145/325478.325479]
• 15: John S. Harper , Darren J. Kerbyson , Graham R. Nudd, Analytical Modeling of Set-Associative Cache Behavior, IEEE Transactions on Computers, v.48 n.10, p.1009-1024, October 1999 [doi>10.1109/12.805152]
• 16: Karin Högstedt , Larry Carter , Jeanne Ferrante, On the Parallel Execution Time of Tiled Loops, IEEE Transactions on Parallel and Distributed Systems, v.14 n.3, p.307-321, March 2003 [doi>10.1109/TPDS.2003.1189587]
• 17: [17] C. Hsu and U. Kremer. Tile selection algorithms and their performance models. Technical Report DCS-TR-401, CS Dept., Rutgers University, Oct. 1999.
• 18: 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]
• 19: [19] M. Jimenez, J.M. Llaberia, and A. Fernandez. A cost-effective implementation of multilevel tiling. IEEE Transactions on Parallel and Distributed Computing, 14(10):1006 1020, 2003.
• 20: K. O. Kortanek , Xiaojie Xu , Yinyu Ye, An infeasible interior-point algorithm for solving primal and dual geometric programs, Mathematical Programming: Series A and B, v.76 n.1, p.155-181, Jan. 2, 1997 [doi>10.1007/BF02614382]
• 21: [21] Computational Optimization Laboratory. User's guide of COPL_GP: Compuational optimization program lihary: Geometric programming. (available at: http://dollar.biz.uiowa.edu/col/). Technical Report Department of Management Science, The University of Iowa, May 2000.
• 22: 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
• 23: 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]
• 24: [24] MOSEK optimization tools. see http://www.mosek.com/products/3/tools/help.
• 25: Juan J. Navarro , Toni Juan , Tomás Lang, MOB forms: a class of multilevel block algorithms for dense linear algebra operations, Proceedings of the 8th international conference on Supercomputing, p.354-363, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181561]
• 26: Gabriel Rivera , Chau-Wen Tseng, Data transformations for eliminating conflict misses, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.38-49, June 17-19, 1998, Montreal, Quebec, Canada
• 27: Gabriel Rivera , Chau-Wen Tseng, Eliminating conflict misses for high performance architectures, Proceedings of the 12th international conference on Supercomputing, p.353-360, July 1998, Melbourne, Australia [doi>10.1145/277830.277917]
• 28: 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
• 29: V. Sarkar , N. Megiddo, An analytical model for loop tiling and its solution, Proceedings of the 2000 IEEE International Symposium on Performance Analysis of Systems and Software, p.146-153, April 24-25, 2000
• 30: Jack Dongarra , Robert Schreiber, Automatic Blocking of Nested Loops, University of Tennessee, Knoxville, TN, 1990
• 31: 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
• 32: O. Temam , E. D. Granston , W. Jalby, To copy or not to copy: a compile-time technique for assessing when data copying should be used to eliminate cache conflicts, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.410-419, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169762]
• 33: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 34: 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
• 35: 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
• 36: Michael Wolfe, Iteration Space Tiling for Memory Hierarchies, Proceedings of the Third SIAM Conference on Parallel Processing for Scientific Computing, p.357-361, December 01-04, 1987
• 37: David Wonnacott, Time Skewing for Parallel Computers, Proceedings of the 12th International Workshop on Languages and Compilers for Parallel Computing, p.477-480, August 04-06, 1999
• 38: Jingling Xue, Loop tiling for parallelism, Kluwer Academic Publishers, Norwell, MA, 2000