The design, implementation, and evaluation of adaptive code unloading for resource-constrained devices

ABSTRACT

Java Virtual Machines (JVMs) for resource-constrained devices, e.g., hand-helds and cell phones, commonly employ interpretation for program translation. However, compilers are able to produce significantly better code quality, and, hence, use device resources more efficiently than interpreters, since compilers can consider large sections of code concurrently and exploit optimization opportunities. Moreover, compilation-based systems store code for reuse by future invocations obviating the redundant computation required for reinterpretation of repeatedly executed code.However, code storage required for compilation can increase the memory footprint of the virtual machine (VM) significantly. As a result, for devices with limited memory resources, this additional code storage may preclude some programs from executing, significantly increase memory management overhead, and substantially reduce the amount of memory available for use by the application.To address the limitations of native code storage, we present the design, implementation, and empirical evaluation of a compiled-code management system that can be integrated into any compilation-based JVM. The system unloads compiled code to reduce the memory footprint of the VM. It does so by dynamically identifying and unloading dead or infrequently used code; if the code is later reused, it is recompiled by the system. As such, our system adaptively trades off memory footprint and its associated memory management costs, with recompilation overhead. Our empirical evaluation shows that our code management system significantly reduces the memory requirements of a compile-only JVM, while maintaining the performance benefits enabled by compilation.We investigate a number of implementation alternatives that use dynamic program behavior and system resource availability to determine when to unload as well as what code to unload. From our empirical evaluation of these alternatives, we identify a set of strategies that enable significant reductions in the memory overhead required for application code. Our system reduces code size by 36--62%, on average, which translates into significant execution-time benefits for the benchmarks and JVM configurations that we studied.

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 , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 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: Arnold, M., Fink, S., Grove, D., Hind, M., and Sweeney, P. F. 2000b. Adaptive optimization in the Jalapeño JVM: The controller's analytical mode. In Proceedings of the 3rd ACM Workshop on Feedback-Directed and Dynamic Optimization (FDDO-3).
• 5: 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
• 6: Don Box , Ted Pattison, Essential .NET: The Common Language Runtime, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 7: James Gosling , Bill Joy , Guy Steele , Gilad Bracha, Java Language Specification, Second Edition: The Java Series, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 8: Bruening, D. and Duesterwald, E. 2000. Exploring optimal compilation unit shapes for an embedded Just-In-Time compiler. In Proceedings of the 3rd ACM Workshop on Feedback-Directed and Dynamic Optimization (FDDO-3).
• 9: 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
• 10: ChaiVM. http://www.chai.hp.com.
• 11: 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
• 12: CLDC 2003. The cldc hotspot(tm) implementation virtual machine. White Paper. http://web2.java.sun.com/products/cldc/wp/CLDC_HotSpot_WhitePaper.pdf.
• 13: Saumya Debray , William Evans, Profile-guided code compression, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 14: Bertrand Delsart , Vania Joloboff , Eric Paire, JCOD: A Lightweight Modular Compilation Technology for Embedded Java, Proceedings of the Second International Conference on Embedded Software, p.197-212, October 07-09, 2002
• 15: Giuseppe Desoli , Nikolay Mateev , Evelyn Duesterwald , Paolo Faraboschi , Joseph A. Fisher, DELI: a new run-time control point, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 16: Milenko Drinić , Darko Kirovski , Hoi Vo, Code optimization for code compression, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 17: Kemal Ebcioglu , Erik Altman , Michael Gschwind , Sumedh Sathaye, Dynamic Binary Translation and Optimization, IEEE Transactions on Computers, v.50 n.6, p.529-548, June 2001 [doi>10.1109/12.931892 ]
• 18: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.358-365, June 16-18, 1997, Las Vegas, Nevada, United States
• 19: Keith I. Farkas , Jason Flinn , Godmar Back , Dirk Grunwald , Jennifer M. Anderson, Quantifying the energy consumption of a pocket computer and a Java virtual machine, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.252-263, June 18-21, 2000, Santa Clara, California, United States
• 20: Stephen J. Fink , Feng Qian, Design, implementation and evaluation of adaptive recompilation with on-stack replacement, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 21: Kim Hazelwood , Michael D. Smith, Code Cache Management Schemes for Dynamic Optimizers, Proceedings of the Sixth Annual Workshop on Interaction between Compilers and Computer Architectures, p.102, February 03-03, 2002
• 22: Kim Hazelwood , Michael D. Smith, Generational Cache Management of Code Traces in Dynamic Optimization Systems, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.169, December 03-05, 2003
• 23: Kim Hazelwood , James E. Smith, Exploring Code Cache Eviction Granularities in Dynamic Optimization Systems, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.89, March 20-24, 2004, Palo Alto, California
• 24: HotSpot 2001. The Java HotSpot Virtual Machine. White Paper. http://java.sun.com/products/hotspot/docs/whitepaper/Java_HotSpot_WP_Final_4_30_01.ps.
• 25: Kaffe 1998. Kaffe---An opensource Java virtual machine. http://www.kaffe.org.
• 26: A. Krall, Efficient JavaVM Just-in-Time Compilation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.205, October 12-18, 1998
• 27: Chandra Krintz, Coupling on-line and off-line profile information to improve program performance, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 28: Chandra Krintz , Brad Calder, Using annotations to reduce dynamic optimization time, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.156-167, June 2001, Snowbird, Utah, United States
• 29: Krintz, C., Grove, D., Sarkar, V., and Calder, B. 2001. Reducing the overhead of dynamic compilation. Software-Practice and Experience 31, 8, 717--738.
• 30: KVM 2000. Java(TM) 2 Platform Micro Edition(J2ME(TM)) Technology for creating mobile devices. White Paper. http://java.sun.com/products/cldc/wp/KVMwp.pdf.
• 31: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 32: Steven Lucco, Split-stream dictionary program compression, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.27-34, June 18-21, 2000, Vancouver, British Columbia, Canada
• 33: SpecJVM98. SpecJVM'98 Benchmarks. http://www.spec.org/osg/jvm98.
• 34: SSCLI 2002. Rotor - the shared source cli. http://research.microsoft.com/programs/europe/rotor/default.aspx.
• 35: David Stutz , Ted Neward , Geoff Shilling, Shared Source Cli Essentials, O'Reilly & Associates, Inc., Sebastopol, CA, 2002
• 36: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 37: Takahashi, D. 2001. Java chips make a comeback. Red Herring.
• 38: Vijaykrishnan, N., Kandemir, M., Tomar, S., Kim, S., Sivasubramaniam, A., and Irwin, M. J. 2001. Energy characterization of Java applications from a memory perspective. In Proceedings of the USENIX Java Virtual Machine Research and Technology Symposium.
• 39: John Whaley, Partial method compilation using dynamic profile information, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.166-179, October 14-18, 2001, Tampa Bay, FL, USA
• 40: Byung-Sun Yang , Soo-Mook Moon , Seongbae Park , Junpyo Lee , SeungIl Lee , Jinpyo Park , Yoo C. Chung , Suhyun Kim , Kemal Ebcioglu , Erik Altman, LaTTe: A Java VM Just-in-Time Compiler with Fast and Efficient Register Allocation, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.128, October 12-16, 1999
• 41: Lingli Zhang , Chandra Krintz, Adaptive code unloading for resource-constrained JVMs, Proceedings of the 2004 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 11-13, 2004, Washington, DC, USA
• 42: Lingli Zhang , Chandra Krintz, Profile-driven code unloading for resource-constrained JVMs, Proceedings of the 3rd international symposium on Principles and practice of programming in Java, June 16-18, 2004, Las Vegas, Nevada

INDEX TERMS

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

Keywords:
Code unloading, JIT, JVM, code-size reduction, resource-constrained devices