article

TinyVM: an energy-efficient execution infrastructure for sensor networks

Authors:

Bernd Burgstaller,

Bernhard ScholzAuthors Info & Claims

Software—Practice & Experience, Volume 42, Issue 10

Pages 1193 - 1209

https://doi.org/10.1002/spe.1123

Published: 01 October 2012 Publication History

Abstract

Energy-efficient implementation techniques for virtual machines (VMs) have received little attention yet: conventional wisdom claims that VMs have a diametrical effect on energy consumption, and VM-based applications are therefore short-lived. In this paper, we argue that bytecode interpretation is affordable if we synthesize VMs specifically for energy efficiency. We present TinyVM, an execution infrastructure that seamlessly integrates with C and nesC/TinyOS-based programming environments. TinyVM achieves high code density through the use of compressed bytecode as the primary program representation. Compressed bytecode allows rapid application deployment with low communication overhead. TinyVM executes compressed bytecode in place, which eliminates the need for a decompression stage and thereby reduces memory consumption on sensor nodes. Our infrastructure automates the creation of energy-efficient application-specific VMs. Applications are partitioned in machine code, bytecode, and VM instruction set extensions. Partitioning is manually controlled and/or fully guided by a discrete optimization problem that produces a partitioning with lowest energy consumption for a given program size limit. We provide experimental results for sensor network benchmarks and for selected applications on various CPU architectures including Atmega128-based motes and the ARM-based Intel iMote2. TinyVM has been released under the GNU General Public License. Copyright © 2011 John Wiley & Sons, Ltd.

References

[1]

Johnson M, Healy M, van de Ven P, Hayes MJ, Nelson J, Newe T, Lewis E. A comparative review of wireless sensor network mote technologies. Proc. IEEE Sensors 2009, IEEE, 2009.

[2]

Polastre J, Szewczyk R, Culler D. Telos: enabling ultra-low power wireless research. Proceedings of the 4th International Symposium on Information Processing in Sensor Networks, IPSN '05, IEEE Press, 2005.

Digital Library

[3]

Hempstead M, Tripathi N, Mauro P, Wei G, Brooks D. An ultra low power system architecture for sensor network applications. Proceedings of the 32nd Annual International Symposium on Computer Architecture, ISCA '05, IEEE Press, 2005; 208–219.

Digital Library

[4]

Hill J, Szewczyk R, Woo A, Hollar S, Culler D, Pister K. System architecture directions for networked sensors. Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS-IX, ACM Press, 2000; 93–104.

Digital Library

[5]

Beutel J. Fast-prototyping using the BTnode platform. Proceedings of the Conference on Design, Automation and Test in Europe, DATE '06, ACM Press, 2006.

Digital Library

[6]

Dutta P, Taneja J, Jeong J, Jiang X, Culler D. A building block approach to sensornet systems. Proceedings of the 6th ACM Conference on Embedded Network Sensor Systems, SenSys '08, ACM Press, 2008.

Digital Library

[7]

Nachman L, Kling R, Adler R, Huang J, Hummel V. The Intel mote platform: a bluetooth-based sensor network for industrial monitoring. Proceedings of the 4th International Symposium on Information Processing in Sensor Networks, IPSN '05, IEEE Press, 2005.

Digital Library

[8]

Müller R, Alonso G, Kossmann D. SwissQM: next generation data processing in sensor networks. Proceedings of the Third Biennial Conference on Innovative Data Systems Research, CIDR 2007, Online Proceedings, http://www.cidrdb.org/, 2007.

[9]

Lin JN, Huang JL. A virtual machine-based programming environment for rapid sensor application development. Proceedings of the 31st Annual International Computer Software and Applications Conference, COMPSAC '07, IEEE Computer Society, 2007; 87–95.

Digital Library

[10]

Simon D, Cifuentes C, Cleal D, Daniels J, White D. Java on the bare metal of wireless sensor devices: the squawk Java virtual machine. Proceedings of the 2nd International Conference on Virtual Execution Environments, VEE '06, ACM, 2006; 78–88.

Digital Library

[11]

Levis P, Gay D, Culler D. Active sensor networks. Proceedings of the 2nd Symposium on Networked Systems Design & Implementation, NSDI'05, USENIX Association, 2005.

Digital Library

[12]

Koshy J, Pandey R. VMSTAR: synthesizing scalable runtime environments for sensor networks. Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems, SenSys '05, ACM Press, 2005; 243–254.

Digital Library

[13]

Balani R, Han CC, Rengaswamy RK, Tsigkogiannis I, Srivastava M. Multi-level software reconfiguration for sensor networks. Proceedings of the 6th ACM & IEEE International Conference on Embedded Software, EMSOFT '06, ACM, 2006; 112–121.

Digital Library

[14]

Levis P, Culler D. Maté: a tiny virtual machine for sensor networks,Proceedings of the 10th International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS-X, ACM Press, 2002.

Digital Library

[15]

Ertl MA, Gregg D, Krall A, Paysan B. <span>vmgen</span>—a generator of efficient virtual machine interpreters. Software-Practice and Experience. 2002; 32(3): 265–294.

Digital Library

[16]

Gay D, Levis P, v Behren R, Welsh M, Brewer E, Culler D. The nesC language: a holistic approach to networked embedded systems. Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation, PLDI '03, ACM Press, 2003; 1–11.

Digital Library

[17]

List of WSN motes. http://en.wikipedia.org/wiki/List_of_wireless_sensor_nodes, {September 2010}.

[18]

Hanson DR, Fraser CW. A Retargetable C Compiler: Design and Implementation. Addison Wesley Publishing Company: Redwood City, CA, 1995.

Digital Library

[19]

Burgstaller B, Scholz B, Ertl A. An embedded systems programming environment for C. Proceedings of the European Conference on Parallel Computing, Euro-Par 2006, Springer LNCS, 2006; 1204–1216.

Digital Library

[20]

Ernst J, Evans WS, Fraser CW, Lucco S, Proebsting TA. Code compression. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '97, ACM, 1997; 358–365.

Digital Library

[21]

Fraser CW, Myers EW, Wendt AL. Analyzing and compressing assembly code. SIGPLAN Notes. 1984; 19(6): 117–121.

Digital Library

[22]

Liao S, Devadas S, Keutzer K. Code density optimization for embedded DSP processors using data compression techniques. Proceedings of the 16th Conference on Advanced Research in VLSI, ARVLSI '95, IEEE Computer Society, 1995.

Digital Library

[23]

Kozuch M, Wolfe A. Compression of embedded system programs. Proceedings of the 1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, ICCS '94, IEEE Computer Society, 1994; 270–277.

Digital Library

[24]

Lekatsas H, Wolf W. SAMC: a code compression algorithm for embedded processors. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1999; 18(12): 1689–1701.

Digital Library

[25]

Cooper KD, McIntosh N. Enhanced code compression for embedded RISC processors. Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation, PLDI '99, ACM, 1999; 139–149.

Digital Library

[26]

Debray S, Evans W. Profile-guided code compression. Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation, PLDI '02, ACM, 2002; 95–105.

Digital Library

[27]

Latendresse M, Feeley M. Generation of fast interpreters for Huffman compressed bytecode. Science of Computer Programming. 2005; 57(3): 295–317.

Digital Library

[28]

Fourer R, Gay DM, Kernighan B. 1989. AMPL: a mathematical programming language. In Algorithms and Model Formulations in Mathematical Programming, Wallace SW (ed.). Springer-Verlag: New York; 150–151.

Digital Library

[29]

Nazhandali L, Minuth M, Austin T. SenseBench: toward an accurate evaluation of sensor network processors. Proceedings of the 2005 IEEE International Symposium on Workload Characterization, IEEE Computer Society, 2005; 197–203.

[30]

Malan DJ. Crypto for tiny objects, Technical Report TR-04-04, Harvard University, 2004.

[31]

Guthaus MR, Ringenberg JS, Ernst D, Austin TM, Mudge T, Brown RB. MiBench: a free, commercially representative embedded benchmark suite. Proceedings of the 2001 IEEE International Workshop on Workload Characterization, IEEE Computer Society, 2001; 3–14.

Digital Library

[32]

Titzer B, Lee D, Palsberg J. Avrora: scalable sensor network simulation with precise timing. Proceedings of the 4th International Symposium on Information Processing in Sensor Networks, IPSN '05, IEEE Press, 2005; 477–482.

Digital Library

[33]

Costa N, Pereira A, Serodio C. Virtual machines applied to WSN's: the state-of-the-art and classification. Proceedings of the Second International Conference on Systems and Networks Communications, ICSNC '07, IEEE Computer Society, 2007.

Digital Library

[34]

Bay H, Ess A, Tuytelaars T, Van Gool L. Speeded-up robust features (SURF). Computer Vision and Image Understanding. 2008; 110(3): 346–359.

Digital Library

[35]

Standard Performance Evaluation Corporation. Spec CPU 2000, 2000. http://www.spec.org/.

[36]

Hong K, Park J, Kim T, Kim S, Kim H, Ko Y, Park J, Burgstaller B, Scholz B. TinyVM, an efficient virtual machine infrastructure for sensor networks. Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, SenSys '09, ACM, 2009; 399–400.

Digital Library

[37]

Kim H, Hong K, Kim S, Kim T, Park J, Ko Y, Burgstaller B, Scholz B. Billy get your guns: fast barrel-shift decoding for in-place execution of Huffman-encoded bytecode streams. Proceedings of the 3rd International Conference on Ubiquitous Information Technologies and Applications, Korea Information Processing Society, IEEE Technical Co-Sponsorship, 2008.

[38]

Kim H, Hong K, Kim S, Kim T, Park J, Ko Y, Burgstaller B, Scholz B. Billy get your guns: fast barrel-shift decoding for in-place execution of Huffman-encoded bytecode streams, Technical Report TR-0001, Yonsei University, Dept. Computer Science, ELC Lab, Seoul, Korea, 2008.

[39]

Kim T, Kim S, Hong K, Kim H, Park J, Ko Y, Burgstaller B, Scholz B. An efficient mixed-mode execution environment for C on mobile phone platforms. Proceedings of the 2009 WRI World Congress on Computer Science and Information Engineering, IEEE Computer Society, 2009; 320–328.

Digital Library

[40]

Park Jiin, Park Jinhyung, Song W, Yoon S, Burgstaller B, Scholz B. Treegraph-based instruction scheduling for stack-based virtual machines. Proceedings of the Sixth Workshop on Bytecode Semantics, Verification, Analysis and Transformation (Bytecode 2011), Electronic Notes in Theoretical Computer Science, Elsevier, 2011.

Digital Library

[41]

Park J, Jeong Y, Burgstaller B. An LLVM backend for stack-based virtual machines. Proceedings of the 5th International Symposium on Embedded Technology, ISET 2010, Institute of Embedded Engineering of Korea, 2010.

[42]

TinyVM Web Site. http://elc.yonsei.ac.kr/TinyVM.htm.

Cited By

Vikash Mishra LVarma S(2021)Middleware Technologies for Smart Wireless Sensor Networks towards Internet of Things: A Comparative ReviewWireless Personal Communications: An International Journal10.1007/s11277-020-07748-7116:3(1539-1574)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s11277-020-07748-7
Reijers NShih C(2019)Improved Ahead-of-time Compilation of Stack-based JVM Bytecode on Resource-constrained DevicesACM Transactions on Sensor Networks10.1145/334117015:3(1-44)Online publication date: 13-Aug-2019
https://dl.acm.org/doi/10.1145/3341170
Giri ADutta SNeogy SDahal KPervez ZHamdan HBoubiche DKlett F(2017)Internet of things (IoT)Proceedings of the 1st International Conference on Internet of Things and Machine Learning10.1145/3109761.3109768(1-12)Online publication date: 17-Oct-2017
https://dl.acm.org/doi/10.1145/3109761.3109768

Index Terms

TinyVM: an energy-efficient execution infrastructure for sensor networks
1. Software and its engineering
  1. Software notations and tools
    1. Development frameworks and environments

Recommendations

TinyVM, an efficient virtual machine infrastructure for sensor networks
SenSys '09: Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems

We present TinyVM, a Virtual Machine (VM) for nesC and C applications on sensor motes. TinyVM executes compressed bytecode on-the-fly to conserve memory. To facilitate creation of application-specific VMs, partitioning of applications into bytecode, VM ...
Energy-Efficient Virtual Machine Consolidation

A novel approach to virtual machine (VM) consolidation, based on energy-efficient storage migration and live VM migration, is implemented using Eucalyptus, an open source clone of the Amazon Elastic Compute Cloud. Several experiments demonstrate the ...
An energy efficient clustering method for wireless sensor networks
EHAC'07: Proceedings of the 6th WSEAS International Conference on Electronics, Hardware, Wireless and Optical Communications

Wireless sensor networks have many sensor nodes with a limited energy in a limited area. One of key issues in wireless sensor networks is to prolong the network lifetime. In this paper, we propose a scheme to construct an energy-efficient cluster ...

Reviews

Reviewer: William M. Waite

TinyVM has a typical stack architecture, but in this paper, no details of its instruction set or register structure are given. Rather, the authors present a complex infrastructure for creating energy-efficient execution images on a variety of hardware. Their basic idea is to decompose a program into components, each of which is implemented in one of three ways: as byte code for TinyVM, as a domain-specific extension of TinyVM, or as native code for the underlying machine. Each implementation technique has advantages and disadvantages with respect to speed, space, and energy consumption. The trick is to find the best combination according to some predefined criteria. The paper begins with a discussion of the compilation environment that allows a program to be split, with each part processed appropriately, and the results to be combined. The authors then consider the problem of performing the split automatically. They prove that this multi-objective problem is nondeterministic polynomial-time (NP) hard, but provide an approximation algorithm. Results from the approximation algorithm are then presented and discussed, and related work reviewed. I found the paper interesting, particularly the range of technology that the authors used to build their infrastructure. The explanations of the infrastructure are clear, but to get some of the subtleties, I found it necessary to look into the paper's extensive references. Nevertheless, the material is accessible to anyone with a rudimentary understanding of compiler construction. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Software

Software Volume 42, Issue 10

October 2012

119 pages

ISSN:0038-0644

EISSN:1097-024X

Issue’s Table of Contents

Publisher

John Wiley & Sons, Inc.

United States

Publication History

Published: 01 October 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Vikash Mishra LVarma S(2021)Middleware Technologies for Smart Wireless Sensor Networks towards Internet of Things: A Comparative ReviewWireless Personal Communications: An International Journal10.1007/s11277-020-07748-7116:3(1539-1574)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s11277-020-07748-7
Reijers NShih C(2019)Improved Ahead-of-time Compilation of Stack-based JVM Bytecode on Resource-constrained DevicesACM Transactions on Sensor Networks10.1145/334117015:3(1-44)Online publication date: 13-Aug-2019
https://dl.acm.org/doi/10.1145/3341170
Giri ADutta SNeogy SDahal KPervez ZHamdan HBoubiche DKlett F(2017)Internet of things (IoT)Proceedings of the 1st International Conference on Internet of Things and Machine Learning10.1145/3109761.3109768(1-12)Online publication date: 17-Oct-2017
https://dl.acm.org/doi/10.1145/3109761.3109768

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents