The ExoVM system for automatic VM and application reduction

ABSTRACT

Embedded systems pose unique challenges to Java application developers and virtual machine designers. Chief among these challenges is the memory footprint of both the virtual machine and the applications that run within it. With the rapidly increasing set of features provided by the Java language, virtual machine designers are often forced to build custom implementations that make various tradeoffs between the footprint of the virtual machine and the subset of the Java language and class libraries that are supported. In this paper, we present the ExoVM, a system in which an application is initialized in a fully featured virtual machine, and then the code, data, and virtual machine features necessary to execute it are packaged into a binary image. Key to this process is feature analysis, a technique for computing the reachable code and data of a Java program and its implementation inside the VM simultaneously. The ExoVM reduces the need to develop customized embedded virtual machines by reusing a single VM infrastructure and automatically eliding the implementation of unused Java features on a per-program basis. We present a constraint-based instantiation of the analysis technique, an implementation in IBM's J9 Java VM, experiments evaluating our technique for the EEMBC benchmark suite, and some discussion of the individual costs of some of Java's features. Our evaluation shows that our system can reduce the non-heap memory allocation of the virtual machine by as much as 75%. We discuss VM and language design decisions that our work shows are important in targeting embedded systems, supporting the long-term goal of a common VM infrastructure spanning from motes to large servers.

REFERENCES

• 1: C. Scott Ananian , Martin Rinard, Data size optimizations for java programs, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 2: David F. Bacon , Peter F. Sweeney, Fast static analysis of C++ virtual function calls, Proceedings of the 11th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.324-341, October 06-10, 1996, San Jose, California, United States
• 3: G. Chen , M. Kandemir , N. Vijaykrishnan , M. J. Irwin , B. Mathiske , M. Wolczko, Heap compression for memory-constrained Java environments, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 4: Connected Limited Device Configuration (CLDC). http://java.sun.com/j2me
• 5: A. Courbot, G. Grimaud, and J.-J. Vandewalle. Romization: Early Deployment and Customization of Java Systems for Constrained Devices. In Proceedings of Second International Workshop on Construction and Analysis of Safe, Secure, and Interoperable Smart Devices (CASSIS). Nice, France, Mar 2005.
• 6: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 7: Joel Koshy , Raju Pandey, VMSTAR: synthesizing scalable runtime environments for sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098945]
• 8: Tamiya Onodera , Kiyokuni Kawachiya, A study of locking objects with bimodal fields, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.223-237, November 01-05, 1999, Denver, Colorado, United States
• 9: Daniel Spoonhower , Joshua Auerbach , David F. Bacon , Perry Cheng , David Grove, Eventrons: a safe programming construct for high-frequency hard real-time applications, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 10: Frank Tip , Chris Laffra , Peter F. Sweeney , David Streeter, Practical experience with an application extractor for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.292-305, November 01-05, 1999, Denver, Colorado, United States
• 11: Frank Tip , Jens Palsberg, Scalable propagation-based call graph construction algorithms, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.281-293, October 2000, Minneapolis, Minnesota, United States
• 12: Ben L. Titzer, Virgil: objects on the head of a pin, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 13: Sun Microsystems, J2ME Building Blocks for Mobile Devices, 2000.
• 14: Derek Rayside , Kostas Kontogiannis, Extracting Java library subsets for deployment on embedded systems, Science of Computer Programming, v.45 n.2-3, p.245-270, November 2002 [doi>10.1016/S0167-6423(02)00059-X]
• 15: Zhiqun Chen, Java Card Technology for Smart Cards: Architecture and Programmer's Guide, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 16: Derek Rayside , Evan Mamas , Erik Hons, Compact Java binaries for embedded systems, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.9, November 08-11, 1999, Mississauga, Ontario, Canada
• 17: Da-Wei Chang , Ruei-Chuan Chang, EJVM: an economic Java run-time environment for embedded devices, Software—Practice & Experience, v.31 n.2, p.129-146, Feb. 2001 [doi>10.1002/1097-024X(200102)31:2<129::AID-SPE359>3.0.CO;2-1]
• 18: Deepak Mulchandani, Java for Embedded Systems, IEEE Internet Computing, v.2 n.3, p.30-39, May 1998 [doi>10.1109/4236.683797]
• 19: Malcolm P. Atkinson , Misha Dmitriev , Craig Hamilton , Tony Printezis, Scalable and Recoverable Implementation of Object Evolution for the PJama1 Platform, Revised Papers from the 9th International Workshop on Persistent Object Systems, p.292-314, September 06-08, 2000

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

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

General Terms:
Design, Languages, Performance, Verification

Keywords:
VM design, VM modularity, dead code elimination, embedded systems, feature analysis, persistence, pre-initialization, static analysis, static compilation