[1] Virgil: Objects on the Head of a Pin.
ABSTRACT
Embedded microcontrollers are becoming increasingly prolific, serving as the primary or auxiliary processor in products and research systems from microwaves to sensor networks. Microcontrollers represent perhaps the most severely resource-constrained embedded processors, often with as little as a few bytes of memory and a few kilobytes of code space. Language and compiler technology has so far been unable to bring the benefits of modern object-oriented languages to such processors. In this paper, I will present the design and implementation of Virgil, a lightweight object-oriented language designed with careful consideration for resource-limited domains. Virgil explicitly separates initialization time from runtime, allowing an application to build complex data structures during compilation and then run directly on the bare hardware without a virtual machine or any language runtime. This separation allows the entire program heap to be available at compile time and enables three new data-sensitive optimizations: reachable members analysis, reference compression, and ROM-ization. Experi-mental results demonstrate that Virgil is well suited for writing microcontroller programs, with five demonstrative applications fitting in less than 256 bytes of RAM with fewer than 50 bytes of metadata. Further results show that the optimizations presented in this paper reduced code size between 20% and 80% and RAM size by as much as 75%.
CITATION
Ben L. Titzer. Virgil: Objects on the Head of a Pin. In Proceedings of the 21st Annual Conference on Object-Oriented Systems, Languages, and Applications (OOPSLA '06). October 2006.
AVAILABILITY
Conference version: [virgil-oopsla06.pdf] 427kb.[2] Vertical Object Layout and Compression for Fixed Heaps
ABSTRACT
Research into embedded sensor networks has placed increased focus on the problem of developing reliable and flexible software for microcontroller-class devices. Languages such as nesC [8] and Virgil [14] have brought higher-level programming idioms to this lowest layer of software, thereby adding expressiveness. Both languages are marked by the absence of dynamic memory allocation, which removes the need for a runtime system to manage memory. To provide data structures, nesC offers modules, and Virgil offers the application an opportunity to allocate and initialize objects during compilation. This paper explores techniques for compressing fixed object heaps with the goal of reducing the RAM footprint of a program. We explore table-based compression and introduce a novel form of object layout called vertical object layout. We provide experimental results that measure the impact on RAM size, code size, and execution time for a set of Virgil programs. Our results show that compressed vertical layout has better execution time and code size than table-based compression while achieving more than 20% heap reduction on 6 of 12 benchmark programs.
CITATION
Ben L. Titzer and Jens Palsberg. Vertical Object Layout and Compression for Fixed Heaps. In Proceedings of the International Conference on Compilers, Architecture, and Synthesis for Embedded Systems (CASES '07). Salzburg, Austria. To appear.
AVAILABILITY
Conference version: [vertical-cases07.pdf] 576kb.[3] Objects to Bits: Efficient Implementation of Object-oriented Languages for Very Small Devices
ABSTRACT
The accelerating digital automation of the world around us has placed increased focus
on the problem of developing reliable and flexible software for microcontroller-class
devices. Today, microcontrollers serve as the primary or auxiliary processor in products
and research systems from microwaves to sensor networks. Microcontrollers represent perhaps
the most severely resource-constrained embedded processors, often with as little as a few
bytes of memory and a few kilobytes of code space. Language and compiler technology has so
far been unable to bring the benefits of modern object-oriented languages to such processors.
In this dissertation, I will establish that advanced language and compiler technology can
bring the benefits of object-oriented programming to even the most constrained of embedded
systems.
I present two systems I have developed that significantly advance the state of the art in
this area: Virgil, a new lightweight object-oriented language which I have designed with
careful consideration for resource-limited domains, and the ExoVM, a system that I built
for specializing the IBM J9 Java virtual machine on a per-application basis. These two
systems echo three recurrent themes: pre-initialization, reachability, and compression.
Virgil explores these themes in a pristine setting where the language, compiler, and
applications can be rebuilt from the ground up. To avoid dynamic memory allocation and
the resulting system complexity, Virgil introduces initialization time, where an application
can build complex data structures during compilation. This exposes the entire heap of the
program to the compiler and allows new heap-sensitive compiler optimizations: reachable
members analysis for combined dead code and data elimination, and reference compression
and vertical object layout for more memory-efficient object representation. In contrast,
the ExoVM explores these three key ideas in a scenario where the primary goal is to reuse
a large-scale industrial strength virtual machine, but reduce footprint by automatically
removing dead code in the program and the virtual machine on a per-application basis.
CITATION
Ben L. Titzer. Objects to Bits: Efficient Implementation of Object-oriented Languages for Very Small Devices. PhD Dissertation. Los Angeles, CA. August 2007.