Adaptive java optimisation using instance-based learning

ABSTRACT

This paper describes a portable,machine learning-based approach to Java optimisation. This approach uses an instance-based learning scheme to select good transformations drawn from Pugh 's Unified Transformation Framework [11]. This approach was implemented and applied to a number of numerical Java benchmarks on two platforms. Using this scheme, we are able to gain over 70% of the performance improvement found when using an exhaustive iterative search of the best compiler optimisations. Thus we have a scheme that gives a high level of portable performance without any excessive compilations.

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: B. Alpern, A. Cocchi, D. Lieber, M. Mergen and V. Sarkar. Jalapeno - a compiler-supported Java virtual machine for servers. Workshop on Compiler Support for Software System (WCSSS99), 1999.
• 3: Eva Andreasson , Frank Hoffmann , Olof Lindholm, To Collect or Not to Collect? Machine Learning for Memory Management, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.27-39, August 01-02, 2002
• 4: S. Beaty and S. Colcord. Using genetic algorithm to fine-tune instruction scheduling heuristics. International Conference on Massively Parallel Computer Systems, 1996.
• 5: A. Bik and D. Gannon. javar - a prototype Java reconstructing compiler. Concurrency, Practice and Experience. 9(11), 1997.
• 6: M. Bull, L. Smith, M. Westhead, D. Henty and R. Davey. A benchmark suite for high performance Java. Concurrency, Practice and Experience, 12, 2000.
• 7: 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]
• 8: L. Davis. Handbook of genetic algorithm. Van Nostrand Reihold, 1991.
• 9: G. Fursin, M. O'Boyle and P. Knijnenburg. Evaluating iterative compilation. The 15th Workshop on Languages and Compilers for Parallel Computers (LCPC'02), 2002.
• 10: Java Grande Forum. Making Java work for high-end computing. SC98: High Performance Networking and Computing, 1998.
• 11: Wayne Kelly , William Pugh, A framework for unifying reordering transformations, University of Maryland at College Park, College Park, MD, 1993
• 12: 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
• 13: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 14: S. Long and M. O'Boyle. Towards an adaptive Java optimising compiler, an empirical evaluation of program transformations. The 3rd Workshop on Java for High Performance Computing, 2001.
• 15: S. Long. Adaptive Java optimisation using machine learning techniques. PhD thesis, School of Informatics, The University of Edinburgh. 2004.
• 16: Antoine Monsifrot , François Bodin, Computer aided hand tuning (CAHT): “applying case-based reasoning to performance tuning”, Proceedings of the 15th international conference on Supercomputing, p.196-203, June 2001, Sorrento, Italy [doi>10.1145/377792.377831]
• 17: Antoine Monsifrot , François Bodin , Rene Quiniou, A Machine Learning Approach to Automatic Production of Compiler Heuristics, Proceedings of the 10th International Conference on Artificial Intelligence: Methodology, Systems, and Applications, p.41-50, September 04-06, 2002
• 18: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 19: Eliot Moss , Paul Utgoff , John Cavazos , Carla Brodley , David Scheeff , Doina Precup , Darko Stefanović, Learning to schedule straight-line code, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.929-935, July 1998, Denver, Colorado, United States
• 20: A. Nisbet. GAPS: iterative feedback directed parallelisation using genetic algorithms. The 12nd ACM International Conference for Supercomputing (ICS'98), 1998.
• 21: M. O'Boyle, P. Knijnenburg and G. Frusin. Feedback directed iterative compilation. The 15th Workshop on Languages and Compilers for Parallel Computing (LCPC'02), 2002.
• 22: Jack Shirazi, Java Performance Tuning, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 23: Bryan Singer , Manuela M. Veloso, Learning to Generate Fast Signal Processing Implementations, Proceedings of the Eighteenth International Conference on Machine Learning, p.529-536, June 28-July 01, 2001
• 24: Bryan Singer , Manuela Veloso, Stochastic search for signal processing algorithm optimization, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.22-22, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582056]
• 25: M. Stephenson, U. O'Reilly, M. Martin and S. Amarasinghe. Genetic programming applied to compiler heuristic optimisation. The 6th European Conference on Genetic Programming, 2003.
• 26: 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

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Languages, Performance

Keywords:
adaptive optimisation, instance-based learning, java, optimisation space