Rating Compiler Optimizations for Automatic Performance Tuning

ABSTRACT

To achieve maximum performance gains through compiler optimization, most automatic performance tuning systems use a feed-back directed approach to rate the code versions generated under different optimization options and to search for the best one. They all face the problem that code versions are only comparable if they run under the same execution context. This paper proposes three accurate, fast and flexible rating approaches that address this problem. The three methods identify comparable execution contexts, model relationships between contexts, or force re-execution of the code under the same context, respectively. We apply these methods in an automatic offline tuning scenario. Our performance tuning system improves the program performance of a selection of SPEC CPU 2000 benchmarks by up to 178% (26% on average). Our techniques reduce program tuning time by up to 96% (80% on average), compared to the state-of-the-art tuning scenario that compares optimization techniques using whole-program execution.

REFERENCES

• 1: William Blume , Rudolf Eigenmann, Symbolic range propagation, Proceedings of the 9th International Symposium on Parallel Processing, p.357-363, April 25-28, 1995
• 2: [2] Kingsum Chow and Youfeng Wu. Feedback-directed selection and characterization of compiler optimizations. In Second Workshop on Feedback Directed Optimizations, Israel, November 1999.
• 3: Keith D. Cooper , Devika Subramanian , Linda Torczon, Adaptive Optimizing Compilers for the 21st Century, The Journal of Supercomputing, v.23 n.1, p.7-22, August 2002 [doi>10.1023/A:1015729001611]
• 4: Pedro C. Diniz , Martin C. Rinard, Dynamic feedback: an effective technique for adaptive computing, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.71-84, June 16-18, 1997, Las Vegas, Nevada, United States
• 5: [5] Free Software Foundation, http://gcc.gnu.org/onlinedocs/gcc-3.3.3/gcc/. GCC online documentation, 2003.
• 6: [6] Elana D. Granston and Anne Holler. Automatic recommendation of compiler options. In 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4). December 2001.
• 7: Brian Grant , Matthai Philipose , Markus Mock , Craig Chambers , Susan J. Eggers, An evaluation of staged run-time optimizations in DyC, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.293-304, May 01-04, 1999, Atlanta, Georgia, United States
• 8: 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
• 9: Peter Lee , Mark Leone, Optimizing ML with run-time code generation, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.137-148, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 10: Markus Mock , Craig Chambers , Susan J. Eggers, Calpa: a tool for automating selective dynamic compilation, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.291-302, December 2000, Monterey, California, United States [doi>10.1145/360128.360158]
• 11: [11] Zhelong Pan and Rudolf Eigenmann. Compiler optimization orchestration for peak performance. Technical Report TR-ECE-04-01, School of Electrical and Computer Engineering, Purdue University, 2004.
• 12: Mark Stephenson , Saman Amarasinghe , Martin Martin , Una-May O'Reilly, Meta optimization: improving compiler heuristics with machine learning, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 13: 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
• 14: Michael J. Voss , Rudolf Eigenmann, ADAPT: Automated De-Coupled Adaptive Program Transformation, Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, p.163, August 21-24, 2000
• 15: Michael J. Voss , Rudolf Eigemann, High-level adaptive program optimization with ADAPT, ACM SIGPLAN Notices, v.36 n.7, p.93-102, July 2001
• 16: R. C J.Dongarra, Automatically Tuned Linear Algebra Software, University of Tennessee, Knoxville, TN, 1997
• 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