Think globally, search locally

ABSTRACT

A key step in program optimization is the determination of optimal values for code optimization parameters such as cache tile sizes and loop unrolling factors. One approach, which is implemented in most compilers, is to use analytical models to determine these values. The other approach, used in library generators like ATLAS, is to perform a global empirical search over the space of parameter values.Neither approach is completely suitable for use in general-purpose compilers that must generate high quality code for large programs running on complex architectures. Model-driven optimization may incur a performance penalty of 10-20% even for a relatively simple code like matrix multiplication. On the other hand, global search is not tractable for optimizing large programs for complex architectures because the optimization space is too large.In this paper, we advocate a methodology for generating high-performance code without increasing search time dramatically. Our methodology has three components: (i) modeling, (ii) local search, and (iii) model refinement. We demonstrate this methodology by using it to eliminate the performance gap between code produced by a model-driven version of ATLAS described by us in prior work, and code produced by the original ATLAS system using global search.

REFERENCES

• 1: Automatically Tuned Linear Algebra Software (ATLAS). http://math-atlas.sourceforge.net/.
• 2: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 3: Gianfranco Bilardi , Paolo D'Alberto , Alexandru Nicolau, Fractal Matrix Multiplication: A Case Study on Portability of Cache Performance, Proceedings of the 5th International Workshop on Algorithm Engineering, p.26-38, August 28-31, 2001
• 4: 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
• 5: Paolo D'Alberto and Alex Nicolau. Juliusc: A practical approach for the analysis of divide-and-conquer algorithms. In LCPC, 2004.
• 6: Jack Dongarra. Personal communication.
• 7: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Register Pipelining: An Integrated Approach to Register Allocation for Scalar and Subscripted Variables, Proceedings of the 4th International Conference on Compiler Construction, p.192-206, October 05-07, 1992
• 8: Matteo Frigo and Steven G. Johnson. The design and implementation of FFTW3. Proceedings of the IEEE, 93(2), 2005. special issue on "Program Generation, Optimization, and Adaptation".
• 9: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 10: Daniel M. Lavery , Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, The Importance of Prepass Code Scheduling for Superscalar and Superpipelined Processors, IEEE Transactions on Computers, v.44 n.3, p.353-370, March 1995 [doi>10.1109/12.372029]
• 11: William Press, Saul Teukolsky, William Vetterling, and Brian Flannery. Numerical Recipes in C. Cambridge University Press, 2002.
• 12: Markus Püschel, José M. F. Moura, Jeremy Johnson, David Padua, Manuela Veloso, Bryan W. Singer, Jianxin Xiong, Franz Franchetti, Aca Gaĉić, Yevgen Voronenko, Kang Chen, Robert W. Johnson, and Nick Rizzolo. SPIRAL: Code generation for DSP transforms. Proceedings of the IEEE, 93(2), 2005. special issue on "Program Generation, Optimization, and Adaptation".
• 13: Rafael H. Saavedra-Barrera , Alan J Smith, Measuring Cache and TLB Performance and Their Effect of Benchmark Run, University of California at Berkeley, Berkeley, CA, 1993
• 14: Jack Dongarra , Robert Schreiber, Automatic Blocking of Nested Loops, University of Tennessee, Knoxville, TN, 1990
• 15: R. Clint Whaley. http://sourceforge.net/mailarchive/forum.php? thread_id=1569256&forum_id%=426.
• 16: R. Clint Whaley, Antoine Petitet, and Jack J. Dongarra. Automated empirical optimization of software and the ATLAS project. Parallel Computing, 27(1-2):3--35, 2001.
• 17: 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
• 18: Kamen Yotov, Xiaoming Li, Gang Ren, Maria Garzaran, David Padua, Keshav Pingali, and Paul Stodghill. Is search really necessary to generate high-performance BLAS? Proceedings of the IEEE, 93(2), 2005. special issue on "Program Generation, Optimization, and Adaptation".
• 19: Kamen Yotov , Keshav Pingali , Paul Stodghill, Automatic measurement of memory hierarchy parameters, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada