A comparison of empirical and model-driven optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A comparison of empirical and model-driven optimization

Full text

Pdf (449 KB)

Source

Conference on Programming Language Design and Implementation archive
Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation table of contents

San Diego, California, USA

SESSION: Code optimization I table of contents

Pages: 63 - 76

Year of Publication: 2003

ISBN:1-58113-662-5

Also published in ...

Authors

Kamen Yotov	Cornell University
Xiaoming Li	University of Illinois at Urbana-Champaign
Gang Ren	University of Illinois at Urbana-Champaign
Michael Cibulskis	University of Illinois at Urbana-Champaign
Gerald DeJong	University of Illinois at Urbana-Champaign
Maria Garzaran	University of Illinois at Urbana-Champaign
David Padua	University of Illinois at Urbana-Champaign
Keshav Pingali	Cornell University
Paul Stodghill	Cornell University
Peng Wu	IBM T.J. Watson Research Center

Sponsors

ACM: Association for Computing Machinery
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 60, Citation Count: 30

Additional Information:

abstract references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/781131.781140 What is a DOI?

ABSTRACT

Empirical program optimizers estimate the values of key optimization parameters by generating different program versions and running them on the actual hardware to determine which values give the best performance. In contrast, conventional compilers use models of programs and machines to choose these parameters. It is widely believed that model-driven optimization does not compete with empirical optimization, but few quantitative comparisons have been done to date. To make such a comparison, we replaced the empirical optimization engine in ATLAS (a system for generating a dense numerical linear algebra library called the BLAS) with a model-driven optimization engine that used detailed models to estimate values for optimization parameters, and then measured the relative performance of the two systems on three different hardware platforms. Our experiments show that model-driven optimization can be surprisingly effective, and can generate code whose performance is comparable to that of code generated by empirical optimizers for the BLAS.

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	Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
	2	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]
	3	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]
	4	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]
	5	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
	6	Jack Dongarra , Robert Schreiber, Automatic Blocking of Nested Loops, University of Tennessee, Knoxville, TN, 1990
	7	Basilio B. Fraguela , Ramon Doallo , Emilio L. Zapata, Automatic Analytical Modeling for the Estimation of Cache Misses, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.221, October 12-16, 1999
	8	M. Frigo and S. G. Johnson. FFTW: An adaptive software architecture for the FFT. In proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), volume 3, pages 1381--1384, 1998
	9	John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
	10	T. Kisuki, P. M. W. Knijnenburg, M. F. P. O'Boyle, and H. A. G. Wijshoff . Iterative compilation in program optimization. In proceedings of Compilers for Parallel Computers, pages (CPC), pages 35--44, 2000
	11	Toru Kisuki , Peter M. W. Knijnenburg , Michael F. P. O'Boyle , François Bodin , Harry A. G. Wijshoff, A Feasibility Study in Iterative Compilation, Proceedings of the Second International Symposium on High Performance Computing, p.121-132, May 26-28, 1999
	12	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
	13	R. L. Mattson, J. Gecsei, D. R. Slutz, and I. L. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal 9, 2, 78--117, 1970
	14	A. C. McKellar , E. G. Coffman, Jr., Organizing matrices and matrix operations for paged memory systems, Communications of the ACM, v.12 n.3, p.153-165, March 1969 [doi>10.1145/362875.362879]
	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	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]
	17	J. Ramanujam and P. Sadayappan, Tiling multidimensional iteration spaces for multicomputers, Journal of Parallel and Distributed Computing, 16(2):108--120, 1992
	18	R. C J.Dongarra, Automatically Tuned Linear Algebra Software, University of Tennessee, Knoxville, TN, 1997
	19	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
	20	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
	21	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

CITED BY 30

	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
	Cemal Yilmaz , Arvind S. Krishna , Atif Memon , Adam Porter , Douglas C. Schmidt , Aniruddha Gokhale , Balachandran Natarajan, Main effects screening: a distributed continuous quality assurance process for monitoring performance degradation in evolving software systems, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA
	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
	Tilak Agerwala , Siddhartha Chatterjee, Computer Architecture: Challenges and Opportunities for the Next Decade, IEEE Micro, v.25 n.3, p.58-69, May 2005
	Alan F. Karr , Adam A. Porter, Distributed performance testing using statistical modeling, ACM SIGSOFT Software Engineering Notes, v.30 n.4, July 2005
	Albert Cohen , Marc Sigler , Sylvain Girbal , Olivier Temam , David Parello , Nicolas Vasilache, Facilitating the search for compositions of program transformations, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
	Richard Vuduc , James W. Demmel , Jeff A. Bilmes, Statistical Models for Empirical Search-Based Performance Tuning, International Journal of High Performance Computing Applications, v.18 n.1, p.65-94, February 2004
	J. Dongarra , G. Bosilca , Z. Chen , V. Eijkhout , G. E. Fagg , E. Fuentes , J. Langou , P. Luszczek , J. Pjesivac-Grbovic , K. Seymour , H. You , S. S. Vadhiyar, Self-adapting numerical software (SANS) effort, IBM Journal of Research and Development, v.50 n.2/3, p.223-238, March 2006
	Apan Qasem , Ken Kennedy , John Mellor-Crummey, Automatic tuning of whole applications using direct search and a performance-based transformation system, The Journal of Supercomputing, v.36 n.2, p.183-196, May 2006
	Uday Bondhugula , Albert Hartono , J. Ramanujam , P. Sadayappan, A practical automatic polyhedral parallelizer and locality optimizer, ACM SIGPLAN Notices, v.43 n.6, June 2008
	Leonardo Bachega , Siddhartha Chatterjee , Kenneth A. Dockser , John A. Gunnels , Manish Gupta , Fred G. Gustavson , Christopher A. Lapkowski , Gary K. Liu , Mark P. Mendell , Charles D. Wait , T. J. Chris Ward, A High-Performance SIMD Floating Point Unit for BlueGene/L: Architecture, Compilation, and Algorithm Design, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.85-96, September 29-October 03, 2004
	Xiaoming Li , María Jesús Garzarán , David Padua, A Dynamically Tuned Sorting Library, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.111, March 20-24, 2004, Palo Alto, California
	John Cavazos , Christophe Dubach , Felix Agakov , Edwin Bonilla , Michael F. P. O'Boyle , Grigori Fursin , Olivier Temam, Automatic performance model construction for the fast software exploration of new hardware designs, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea
	John Cavazos , Michael F. P. O'Boyle, Method-specific dynamic compilation using logistic regression, ACM SIGPLAN Notices, v.41 n.10, October 2006
	Albert Cohen , Sébastien Donadio , Maria-Jesus Garzaran , Christoph Herrmann , Oleg Kiselyov , David Padua, In search of a program generator to implement generic transformations for high-performance computing, Science of Computer Programming, v.62 n.1, p.25-46, September 2006
	Jeremy Lau , Matthew Arnold , Michael Hind , Brad Calder, Online performance auditing: using hot optimizations without getting burned, ACM SIGPLAN Notices, v.41 n.6, June 2006
	Apan Qasem , Ken Kennedy, Profitable loop fusion and tiling using model-driven empirical search, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
	Arvind S. Krishna , Aniruddha S. Gokhale , Douglas C. Schmidt, Context-specific middleware specialization techniques for optimizing software product-line architectures, ACM SIGOPS Operating Systems Review, v.40 n.4, October 2006
	Uday Bondhugula , J. Ramanujam , P. Sadayappan, Automatic mapping of nested loops to FPGAS, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
	Min Zhao , Bruce R. Childers , Mary Lou Soffa, An approach toward profit-driven optimization, ACM Transactions on Architecture and Code Optimization (TACO), v.3 n.3, p.231-262, September 2006
	F. Agakov , E. Bonilla , J. Cavazos , B. Franke , G. Fursin , M. F. P. O'Boyle , J. Thomson , M. Toussaint , C. K. I. Williams, Using Machine Learning to Focus Iterative Optimization, Proceedings of the International Symposium on Code Generation and Optimization, p.295-305, March 26-29, 2006
	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
	Mark Stephenson , Saman Amarasinghe, Predicting Unroll Factors Using Supervised Classification, Proceedings of the international symposium on Code generation and optimization, p.123-134, March 20-23, 2005
	Zhelong Pan , Rudolf Eigenmann, Rating Compiler Optimizations for Automatic Performance Tuning, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.14, November 06-12, 2004
	David Parello , Olivier Temam , Albert Cohen , Jean-Marie Verdun, Towards a Systematic, Pragmatic and Architecture-Aware Program Optimization Process for Complex Processors, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.15, November 06-12, 2004
	John Cavazos , Grigori Fursin , Felix Agakov , Edwin Bonilla , Michael F. P. O'Boyle , Olivier Temam, Rapidly Selecting Good Compiler Optimizations using Performance Counters, Proceedings of the International Symposium on Code Generation and Optimization, p.185-197, March 11-14, 2007
	Van Bui , Boyana Norris , Kevin Huck , Lois Curfman McInnes , Li Li , Oscar Hernandez , Barbara Chapman, A component infrastructure for performance and power modeling of parallel scientific applications, Proceedings of the 2008 compFrame/HPC-GECO workshop on Component based high performance, October 16-17, 2008, Karlsruhe, Germany
	Cemal Yilmaz , Adam Porter , Arvind S. Krishna , Atif M. Memon , Douglas C. Schmidt , Aniruddha S. Gokhale , Balachandran Natarajan, Reliable Effects Screening: A Distributed Continuous Quality Assurance Process for Monitoring Performance Degradation in Evolving Software Systems, IEEE Transactions on Software Engineering, v.33 n.2, p.124-141, February 2007
	Hugh Leather , Edwin Bonilla , Michael O'Boyle, Automatic Feature Generation for Machine Learning Based Optimizing Compilation, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.81-91, March 22-25, 2009
	Jason Ansel , Cy Chan , Yee Lok Wong , Marek Olszewski , Qin Zhao , Alan Edelman , Saman Amarasinghe, PetaBricks: a language and compiler for algorithmic choice, ACM SIGPLAN Notices, v.44 n.6, June 2009