High-level adaptive program optimization with ADAPT

ABSTRACT

Compile-time optimization is often limited by a lack of target machine and input data set knowledge. Without this information, compilers may be forced to make conservative assumptions to preserve correctness and to avoid performance degradation. In order to cope with this lack of information at compile-time, adaptive and dynamic systems can be used to perform optimization at runtime when complete knowledge of input and machine parameters is available. This paper presents a compiler-supported high-level adaptive optimization system. Users describe, in a domain specific language, optimizations performed by stand-alone optimization tools and backend compiler flags, as well as heuristics for applying these optimizations dynamically at runtime. The ADAPT compiler reads these descriptions and generates application-specific runtime systems to apply the heuristics. To facilitate the usage of existing tools and compilers, overheads are minimized by decoupling optimization from execution. Our system, ADAPT, supports a range of paradigms proposed recently, including dynamic compilation, parameterization and runtime sampling. We demonstrate our system by applying several optimization techniques to a suite of benchmarks on two target machines. ADAPT is shown to consistently outperform statically generated executables, improving performance by as much as 70%.

REFERENCES

• 1: M. Litzkow, M. Livny, and M. W. Mutka. Condor - a hunter of idle workstations. In Proc. of the 8th Int'l Conf. of Distributed Computing Systems, pages 104-111, June 1988.
• 2: Nirav H. Kapadia , Jose' A. B. Fortes, On the Design of a Demand-Based Network-Computing System: The Purdue University Network-Computing Hubs, Proceedings of the The Seventh IEEE International Symposium on High Performance Distributed Computing, p.71, July 28-31, 1998
• 3: Ian Foster and Carl Kesselmann. Globus: A Metacomputing Infrastructure Toolkit. International Journal of Supercomputing Applications, 11(2):115-128, January 1997.
• 4: M. Byler, J.R.B. Davies, C. Huson, B. Leasure, and M. Wolfe. Multiple version loops. In International Conf. on Parallel Processing, pages 312-318, August 1987.
• 5: 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
• 6: R. Gupta , R. Bodik, Adaptive loop transformations for scientific programs, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.368, October 25-28, 1995
• 7: 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
• 8: 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]
• 9: Dawson R. Engler, VCODE: a retargetable, extensible, very fast dynamic code generation system, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.160-170, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 10: 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
• 11: 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
• 12: 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
• 13: William Blume , Ramon Doallo , Rudolf Eigenmann , John Grout , Jay Hoeflinger , Thomas Lawrence , Jaejin Lee , David Padua , Yunheung Paek , Bill Pottenger , Lawrence Rauchwerger , Peng Tu, Parallel Programming with Polaris, Computer, v.29 n.12, p.78-82, December 1996 [doi>10.1109/2.546612]
• 14: Rafael H. Saavedra , Daeyeon Park, Improving the Effectiveness of Software Prefetching with Adaptive Execution, Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques, p.68, October 20-23, 1996
• 15: Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991 [doi>10.1109/12.88484]
• 16: Lawrence Rauchwerger , David Padua, The privatizing DOALL test: a run-time technique for DOALL loop identification and array privatization, Proceedings of the 8th international conference on Supercomputing, p.33-43, July 11-15, 1994, Manchester, England [doi>10.1145/181181.181254]
• 17: Lawrence Rauchwerger , David Padua, The LRPD test: speculative run-time parallelization of loops with privatization and reduction parallelization, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.218-232, June 18-21, 1995, La Jolla, California, United States
• 18: Mary W. Hall and Margaret Martonosi. Adaptive parallelism in compiler-parallelized code. In Proc. of the 2nd SUIF Compiler Workshop, August 1997.
• 19: 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
• 20: Renaud Marlet , Charles Consel , Philippe Boinot, Efficient incremental run-time specialization for free, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.281-292, May 01-04, 1999, Atlanta, Georgia, United States
• 21: Massimiliano Poletto , Wilson C. Hsieh , Dawson R. Engler , M. Frans Kaashoek, C and tcc: a language and compiler for dynamic code generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.2, p.324-369, March 1999 [doi>10.1145/316686.316697]
• 22: Michael P. Plezbert , Ron K. Cytron, Does “just in time” = “better late than never”?, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.120-131, January 15-17, 1997, Paris, France [doi>10.1145/263699.263713]
• 23: Sun Microsystems. The Java HotSpot Performance Engine Architecture. Technical White Paper, http://java.sun.com/products/hotspot/whitepaper.html, April 1999.
• 24: 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

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Design, Experimentation, Languages, Measurement, Performance, Theory