Positivity, posynomials and tile size selection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Positivity, posynomials and tile size selection

Full text

Pdf (368 KB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 2008 ACM/IEEE conference on Supercomputing - Volume 00 table of contents

Austin, Texas

SECTION: Papers table of contents

Article No. 55

Year of Publication: 2008

ISBN:978-1-4244-2835-9

Authors

Lakshminarayanan Renganarayana	IBM T.J. Watson Research Center, Yorktown Heights, New York
Sanjay Rajopadhye	Colorado State University, Fort Collins, Colorado

Publisher

IEEE Press Piscataway, NJ, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 87, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

ABSTRACT

Tiling is a widely used loop transformation for exposing/exploiting parallelism and data locality. Effective use of tiling requires selection and tuning of the tile sizes. This is usually achieved by developing cost models that characterize the performance of the tiled program as a function of tile sizes. All previous approaches to tile size selection (TSS) are cost model specific. Due to this they are neither extensible (e.g., to richer program classes/newer architectures) nor scalable (e.g., to multiple levels of tiling).

This paper identifies positivity as a fundamental property shared by the functions and parameters commonly used in TSS models. We show how this positivity can be used as a basis to derive a TSS framework which is both efficient and scalable. We also show that almost all TSS models proposed in the literature (including those used in production compilers and auto-tuners) can be reduced to our framework.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	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]
	2	R. Schreiber and J. Dongarra, "Automatic blocking of nested loops," RIACS, NASA Ames Research Center, Tech. Rep. 90.38, Aug 1990.
	3	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
	4	Jingling Xue, Loop tiling for parallelism, Kluwer Academic Publishers, Norwell, MA, 2000
	5	Larry Carter , Jeanne Ferrante , Susan Flynn Hummel, Hierarchical tiling for improved superscalar performance, Proceedings of the 9th International Symposium on Parallel Processing, p.239-245, April 25-28, 1995
	6	K. Yotov, X. Li, G. Ren, M. J. S. Garzaran, D. Padua, K. Pingali, and P. Stodghill, "Is search really necessary to generate high-performance BLAS?" Proceedings of the IEEE, vol. 93, pp. 358--386, 2005.
	7	L. Renganarayanan, M. Harthi-kote, R. Dewri, and S. Rajopadhye, "Towards optimal multi-level tiling for stencil computations," in 21st IEEE International Parallel and Distributed Processing Symposium (IPDPS) (to appear), 2007.
	8	Muthu Manikandan Baskaran , Uday Bondhugula , Sriram Krishnamoorthy , J. Ramanujam , Atanas Rountev , P. Sadayappan, Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories, Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, February 20-23, 2008, Salt Lake City, UT, USA [doi>10.1145/1345206.1345210]
	9	Anant Agarwal , David A. Kranz , Venkat Natarajan, Automatic Partitioning of Parallel Loops and Data Arrays for Distributed Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.6 n.9, p.943-962, September 1995 [doi>10.1109/71.466632]
	10	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]
	11	Pierre-Yves Calland , Tanguy Risset, Precise Tiling for Uniform Loop Nests, Proceedings of the IEEE International Conference on Application Specific Array Processors, p.330, July 24-26, 1995
	12	Edin Hodzic , Weijia Shang, On Supernode Transformation with Minimized Total Running Time, IEEE Transactions on Parallel and Distributed Systems, v.9 n.5, p.417-428, May 1998 [doi>10.1109/71.679213]
	13	Hiroshi Ohta , Yasuhiko Saito , Masahiro Kainaga , Hiroyuki Ono, Optimal tile size adjustment in compiling general DOACROSS loop nests, Proceedings of the 9th international conference on Supercomputing, p.270-279, July 03-07, 1995, Barcelona, Spain [doi>10.1145/224538.224571]
	14	J. Ramanujam and P. Sadayappan, "Tiling multidimensional itertion spaces for multicomputers." J. Parallel Distrib. Comput., vol. 16, no. 2, pp. 108--120, 1992.
	15	R. Andonov, S. Balev, S. V. Rajopadhye, and N. Yanev, "Optimal semi-oblique tiling," IEEE Trans. Parallel Distrib. Syst., vol. 14, no. 9, pp. 944--960, 2003.
	16	Jingling Xue, Communication-minimal tiling of uniform dependence loops, Journal of Parallel and Distributed Computing, v.42 n.1, p.42-59, April 10, 1997 [doi>10.1006/jpdc.1997.1310]
	17	Jingling Xue , Wentong Cai, Time-minimal tiling when rise is larger than zero, Parallel Computing, v.28 n.6, p.915-939, June 2002 [doi>10.1016/S0167-8191(02)00098-4]
	18	Rumen Andonov , Sanjay V. Rajopadhye , Nicola Yanev, Optimal Orthogonal Tiling, Proceedings of the 4th International Euro-Par Conference on Parallel Processing, p.480-490, September 01-04, 1998
	19	C. Hsu and U. Kremer, "Tile selection algorithms and their performance models," CS Dept, Rutgers University, Tech. Rep. DCS-TR-401, Oct. 1999.
	20	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]
	21	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
	22	Fabrice Rastello , Yves Robert, Automatic Partitioning of Parallel Loops with Parallelepiped-Shaped Tiles, IEEE Transactions on Parallel and Distributed Systems, v.13 n.5, p.460-470, May 2002 [doi>10.1109/TPDS.2002.1003856]
	23	B. B. Fraguela, M. G. Carmueja, and D. Andrade, "Optimal tile size selection guided by analytical models." in PARCO, 2005, pp. 565--572.
	24	Vivek Sarkar, Optimized Unrolling of Nested Loops, International Journal of Parallel Programming, v.29 n.5, p.545-581, October 2001 [doi>10.1023/A:1012246031671]
	25	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]
	26	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
	27	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
	28	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]
	29	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
	30	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]
	31	T. Kisuki , P. M. W. Knijnenburg , M. F. P. O'Boyle, Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.237, October 15-19, 2000
	32	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]
	33	Kamen Yotov , Keshav Pingali , Paul Stodghill, Think globally, search locally, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088168]
	34	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, January 2004 [doi>10.1002/cpe.v16:2/3]
	35	Rumen Andonov , Sanjay Rajopadhye, Optimal orthogonal tiling of 2-D iterations, Journal of Parallel and Distributed Computing, v.45 n.2, p.159-165, Sept. 15, 1997 [doi>10.1006/jpdc.1997.1371]
	36	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]
	37	Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
	38	R. Duffin, E. Peterson, and C. Zener, Geometric Programming - Theory and Applications. John Wiley, 1967.
	39	S. Boyd, S. J. Kim, L. Vandenberghe, and A. Hassibi, "A tutorial on Geometric Programming," To appear in Optimization and Engineering, 2006.
	40	Chung-hsing Hsu , Ulrich Kremer, A Quantitative Analysis of Tile Size Selection Algorithms, The Journal of Supercomputing, v.27 n.3, p.279-294, March 2004 [doi>10.1023/B:SUPE.0000011388.54204.8e]
	41	K. Esseghir, "Improving data locality for caches," Master's thesis, Rice University, September 1993.
	42	S. Moon and R. Saavedra, "Hyperblocking: A data reorganization method to eliminate cache conflicts in tiled loop nests," University of Southern California, Tech. Rep. TR-98-671, February 1998.
	43	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
	44	Gabriel Rivera , Chau-Wen Tseng, A Comparison of Compiler Tiling Algorithms, Proceedings of the 8th International Conference on Compiler Construction, Held as Part of the European Joint Conferences on the Theory and Practice of Software, ETAPS'99, p.168-182, March 22-28, 1999
	45	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
	46	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]
	47	L. Renganarayana, R. Upadrasta, and S. Rajopadhye, "Optimal ILP and register tiling: Analytical model and optimization framework," in LCPC 2005: 12th International Workshop on Languages and Compilers for Parallel Computing. Springer Verlag, 2005.
	48	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]
	49	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
	50	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
	51	An updated set of basic linear algebra subprograms (BLAS), ACM Transactions on Mathematical Software (TOMS), v.28 n.2, p.135-151, June 2002 [doi>10.1145/567806.567807]
	52	J. Löfberg, "YALMIP: A toolbox for modeling and optimization in MATLAB," in Proceedings of the CACSD Conference, Taipei, Taiwan, 2004, available from http://control.ee.ethz.ch/~joloef/yalmip.php.
	53	U. Bondhugula, A. Hartono, J. Ramanujam, and P. Sadayappan, "A practical and fully automatic polyhedral program optimization system," in ACM SIGPLAN PLDI, Jun. 2008.
	54	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]
	55	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]
	56	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
	57	B. Meister and S. Verdoolaege, "Polynomial approximations in the polytope model: Bringing the power of quasi-polynomials to the masses," in ODES-6: 6th Workshop on Optimizations for DSP and Embedded Systems, Apr 2008, pp. 45--54.