PEAK—a fast and effective performance tuning system via compiler optimization orchestration

ABSTRACT

Compile-time optimizations generally improve program performance. Nevertheless, degradations caused by individual compiler optimization techniques are to be expected. Feedback-directed optimization orchestration systems generate optimized code versions under a series of optimization combinations, evaluate their performance, and search for the best version. One challenge to such systems is to tune program performance quickly in an exponential search space. Another challenge is to achieve high program performance, considering that optimizations interact. Aiming at these two goals, this article presents an automated performance tuning system, PEAK, which searches for the best compiler optimization combinations for the important code sections in a program. The major contributions made in this work are as follows: (1) An algorithm called Combined Elimination (CE) is developed to explore the optimization space quickly and effectively; (2) Three fast and accurate rating methods are designed to evaluate the performance of an optimized code section based on a partial execution of the program; (3) An algorithm is developed to identify important code sections as candidates for performance tuning by trading off tuning speed and tuned program performance; and (4) A set of compiler tools are implemented to automate optimization orchestration. Orchestrating optimization options in SUN Forte compilers at the whole-program level, our CE algorithm improves performance by 10.8% over the SPEC CPU2000 FP baseline setting, compared to 5.6% improved by manual tuning. Orchestrating GCC O3 optimizations, CE improves performance by 12% over O3, the highest optimization level. Applying the rating methods, PEAK reduces tuning time from 2.19 hours to 5.85 minutes on average, while achieving equal or better program performance.

REFERENCES

• 1: Ali-Reza Adl-Tabatabai , Michał Cierniak , Guei-Yuan Lueh , Vishesh M. Parikh , James M. Stichnoth, Fast, effective code generation in a just-in-time Java compiler, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.280-290, June 17-19, 1998, Montreal, Quebec, Canada
• 2: 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 [doi>10.1109/CGO.2006.37]
• 3: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 4: Matthew Arnold , Michael Hind , Barbara G. Ryder, Online feedback-directed optimization of Java, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 5: Joel Auslander , Matthai Philipose , Craig Chambers , Susan J. Eggers , Brian N. Bershad, Fast, effective dynamic compilation, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.149-159, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 6: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 7: Derek Bruening , Timothy Garnett , Saman Amarasinghe, An infrastructure for adaptive dynamic optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 8: John Cavazos , Michael F. P. O'Boyle, Method-specific dynamic compilation using logistic regression, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 9: Chow, K. and Wu, Y. 1999. Feedback-directed selection and characterization of compiler optimizations. In Proceedings of the 2nd Workshop on Feedback Directed Optimizations. Israel.
• 10: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.13-26, June 18-21, 2000, Vancouver, British Columbia, Canada
• 11: Cliff Click , Keith D. Cooper, Combining analyses, combining optimizations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.181-196, March 1995 [doi>10.1145/201059.201061]
• 12: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 13: Keith D. Cooper , Alexander Grosul , Timothy J. Harvey , Steven Reeves , Devika Subramanian , Linda Torczon , Todd Waterman, ACME: adaptive compilation made efficient, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 14: 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]
• 15: Francis H. Dang , Hao Yu , Lawrence Rauchwerger, The R-LRPD Test: Speculative Parallelization of Partially Parallel Loops, Proceedings of the 16th International Parallel and Distributed Processing Symposium, p.318, April 15-19, 2002
• 16: 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
• 17: Evelyn Duesterwald , Vasanth Bala, Software profiling for hot path prediction: less is more, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.202-211, November 2000, Cambridge, Massachusetts, United States
• 18: Kemal Ebcioğlu , Erik R. Altman, DAISY: dynamic compilation for 100% architectural compatibility, Proceedings of the 24th annual international symposium on Computer architecture, p.26-37, June 01-04, 1997, Denver, Colorado, United States
• 19: Dawson R. Engler, VCODE: a retargetable, extensible, very fast dynamic code generation system, ACM SIGPLAN Notices, v.31 n.5, p.160-170, May 1996
• 20: Dawson R. Engler , Todd A. Proebsting, DCG: an efficient, retargetable dynamic code generation system, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.263-272, October 05-07, 1994, San Jose, California, United States
• 21: GNU. 2005. GCC online documentation. http://gcc.gnu.org/onlinedocs/.
• 22: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• 23: Granston, E. D. and Holler, A. 2001. Automatic recommendation of compiler options. In Proceedings of the 4th Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4).
• 24: 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
• 25: M. Haneda , P. M. W. Knijnenburg , H. A. G. Wijshoff, Generating new general compiler optimization settings, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088171]
• 26: Hedayat, A., Sloane, N., and Stufken, J. 1999. Orthogonal Arrays: Theory and Applications. Springer-Verlag, New York.
• 27: Rajeev Joshi , Greg Nelson , Keith Randall, Denali: a goal-directed superoptimizer, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 28: Karp, R. 1972. Reducibility among combinatorial problems. In Proceedings of the Symposium on the Complexity of Computer Computations. Plenum Press, New York, 85--103.
• 29: Thomas Kistler , Michael Franz, Continuous program optimization: A case study, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.4, p.500-548, July 2003 [doi>10.1145/778559.778562]
• 30: 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
• 31: 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
• 32: Prasad Kulkarni , Stephen Hines , Jason Hiser , David Whalley , Jack Davidson , Douglas Jones, Fast searches for effective optimization phase sequences, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 33: Prasad A. Kulkarni , David B. Whalley , Gary S. Tyson , Jack W. Davidson, Exhaustive Optimization Phase Order Space Exploration, Proceedings of the International Symposium on Code Generation and Optimization, p.306-318, March 26-29, 2006 [doi>10.1109/CGO.2006.15]
• 34: Jeremy Lau , Matthew Arnold , Michael Hind , Brad Calder, Online performance auditing: using hot optimizations without getting burned, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 35: 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
• 36: Mark Leone , Peter Lee, Dynamic specialization in the Fabius system, ACM Computing Surveys (CSUR), v.30 n.3es, Sept. 1998 [doi>10.1145/289121.289144]
• 37: Matthew C. Merten , Andrew R. Trick , Ronald D. Barnes, An Architectural Framework for Runtime Optimization, IEEE Transactions on Computers, v.50 n.6, p.567-589, June 2001 [doi>10.1109/12.931894]
• 38: Matthew C. Merten , Andrew R. Trick , Christopher N. George , John C. Gyllenhaal , Wen-mei W. Hwu, A hardware-driven profiling scheme for identifying program hot spots to support runtime optimization, Proceedings of the 26th annual international symposium on Computer architecture, p.136-147, May 01-04, 1999, Atlanta, Georgia, United States
• 39: 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]
• 40: Nandy, S., Gao, X., and Ferrante, J. 2003. TFP: Time-sensitive, flow-specific profiling at runtime. In Proceedings of the Workshop on Languages and Compiling for Parallel Computing (LCPC).
• 41: Erik M. Nystrom , Ronald D. Barnes , Matthew C. Merten , Wen-mei W. Hwu, Code Reordering and Speculation Support for Dynamic Optimization System, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.163-174, September 08-12, 2001
• 42: Pan, Z. and Eigenmann, R. 2004a. Compiler optimization orchestration for peak performance. Tech. Rep. TR-ECE-04-01, School of Electrical and Computer Engineering, Purdue University.
• 43: 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 [doi>10.1109/SC.2004.47]
• 44: Zhelong Pan , Rudolf Eigenmann, Fast and Effective Orchestration of Compiler Optimizations for Automatic Performance Tuning, Proceedings of the International Symposium on Code Generation and Optimization, p.319-332, March 26-29, 2006 [doi>10.1109/CGO.2006.38]
• 45: R. P. J. Pinkers , P. M. W. Knijnenburg , M. Haneda , H. A. G. Wijshoff, Statistical Selection of Compiler Options, Proceedings of the The IEEE Computer Society's 12th Annual International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunications Systems, p.494-501, October 04-08, 2004
• 46: Lawrence Rauchwerger , David A. Padua, The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.160-180, February 1999 [doi>10.1109/71.752782]
• 47: Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA [doi>10.1145/514191.514229]
• 48: SPEC. 2000. SPEC CPU2000 Results. http://www.spec.org/cpu2000/results.
• 49: 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
• 50: Michelle Mills Strout , Larry Carter , Jeanne Ferrante, Compile-time composition of run-time data and iteration reorderings, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 51: Sun. 2000. Forte C 6 /Sun WorkShop 6 Compilers C User's Guide. http://docs.sun.com/app/docs/doc/806-3567.
• 52: 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
• 53: 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
• 54: Michael J. Voss , Rudolf Eigemann, High-level adaptive program optimization with ADAPT, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.93-102, June 2001, Snowbird, Utah, United States
• 55: 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
• 56: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Compilers; Run-time environments

General Terms:
Performance

Keywords:
Performance tuning, dynamic compilation, optimization orchestration