Removing the memory limitations of sensor networks with flash-based virtual memory

ABSTRACT

Virtual memory has been successfully used in different domains to extend the amount of memory available to applications. We have adapted this mechanism to sensor networks, where, traditionally, RAM is a severely constrained resource. In this paper we show that the overhead of virtual memory can be significantly reduced with compile-time optimizations to make it usable in practice, even with the resource limitations present in sensor networks.

Our approach, ViMem, creates an efficient memory layout based on variable access traces obtained from simulation tools. This layout is optimized to the memory access patterns of the application and to the specific properties of the sensor network hardware.

Our implementation is based on TinyOS. It includes a pre-compiler for nesC code that translates virtual memory accesses into calls of ViMem's runtime component. ViMem uses flash memory as secondary storage. In order to evaluate our system we have modified nontrivial existing applications to make use of virtual memory. We show that its runtime overhead is small even for large data sizes.

REFERENCES

• 1: H. Abrach , S. Bhatti , J. Carlson , H. Dai , J. Rose , A. Sheth , B. Shucker , J. Deng , R. Han, MANTIS: system support for multimodAl NeTworks of in-situ sensors, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941358]
• 2: Atmel Corporation. 4-megabit DataFlash AT45DB041B Datasheet, 2005.
• 3: J. Beutel, O. Kasten, F. Mattern, K. Römer, F. Siegemund, and L. Thiele. Prototyping wireless sensor network applications with BTnodes. In Proc. of the 1st European Workshop on Sensor Networks, pp. 323--338, 2004.
• 4: Brad Calder , Chandra Krintz , Simmi John , Todd Austin, Cache-conscious data placement, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.139-149, October 02-07, 1998, San Jose, California, United States
• 5: Hui Dai , Michael Neufeld , Richard Han, ELF: an efficient log-structured flash file system for micro sensor nodes, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031516]
• 6: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 7: Adam Dunkels , Bjorn Gronvall , Thiemo Voigt, Contiki - A Lightweight and Flexible Operating System for Tiny Networked Sensors, Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks, p.455-462, November 16-18, 2004 [doi>10.1109/LCN.2004.38]
• 8: P. K. Dutta , D. E. Culler, System software techniques for low-power operation in wireless sensor networks, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.925-932, November 06-10, 2005, San Jose, CA
• 9: Eran Gal , Sivan Toledo, Algorithms and data structures for flash memories, ACM Computing Surveys (CSUR), v.37 n.2, p.138-163, June 2005 [doi>10.1145/1089733.1089735]
• 10: D. Gay, P. Levis, D. Culler, and E. Brewer. nesC 1.2 Language Reference Manual, 2005.
• 11: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 12: Lin Gu , John A. Stankovic, t-kernel: providing reliable OS support to wireless sensor networks, Proceedings of the 4th international conference on Embedded networked sensor systems, October 31-November 03, 2006, Boulder, Colorado, USA [doi>10.1145/1182807.1182809]
• 13: Rajiv Gupta, Compiler optimization of data storage, California Institute of Technology, Pasadena, CA, 1992
• 14: Chih-Chieh Han , Ram Kumar , Roy Shea , Eddie Kohler , Mani Srivastava, A dynamic operating system for sensor nodes, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067188]
• 15: S. J. Hartley, Compile-Time Program Restructuring in Multiprogrammed Virtual Memory Systems, IEEE Transactions on Software Engineering, v.14 n.11, p.1640-1644, November 1988 [doi>10.1109/32.9051]
• 16: D. J. Hatfield and J. Gerald. Program restructuring for virtual memory. IBM Systems Journal, 10(3):168--192, 1971.
• 17: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 18: Jonathan W. Hui , David Culler, The dynamic behavior of a data dissemination protocol for network programming at scale, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031506]
• 19: J. Koshy and R. Pandey. Remote incremental linking for energy-efficient reprogramming of sensor networks. In Proc. of the 2nd European Workshop on Wireless Sensor Networks, pp. 354--365, 2005.
• 20: O. Landsiedel , K. Wehrle , S. Gotz, Accurate prediction of power consumption in sensor networks, Proceedings of the 2nd IEEE workshop on Embedded Networked Sensors, p.37-44, April 30-May 01, 2005
• 21: Philip Levis , David Gay , David Culler, Active sensor networks, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.343-356, May 02-04, 2005
• 22: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, The design of an acquisitional query processor for sensor networks, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872817]
• 23: P. J. Marrón, M. Gauger, A. Lachenmann, D. Minder, O. Saukh, and K. Rothermel. FlexCup: A flexible and efficient code update mechanism for sensor networks. In Proc. of the Third European Workshop on Wireless Sensor Networks, pp. 212--227, 2006.
• 24: Maté web page. http://www.cs.berkeley.edu/~pal/mate-web/.
• 25: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 26: Abraham Silberschatz , Peter Baer Galvin , Greg Gagne, Operating System Concepts, John Wiley & Sons, 2006
• 27: James W. Stamos, Static grouping of small objects to enhance performance of a paged virtual memory, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.155-180, May 1984 [doi>10.1145/190.194]
• 28: TinyOS CVS repository. http://tinyos.cvs.sourceforge.net/tinyos/.
• 29: Ben L. Titzer , Daniel K. Lee , Jens Palsberg, Avrora: scalable sensor network simulation with precise timing, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 30: Ben L. Titzer , Jens Palsberg, Nonintrusive precision instrumentation of microcontroller software, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 31: Gilman Tolle , Joseph Polastre , Robert Szewczyk , David Culler , Neil Turner , Kevin Tu , Stephen Burgess , Todd Dawson , Phil Buonadonna , David Gay , Wei Hong, A macroscope in the redwoods, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098925]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Preprocessors

General Terms:
Algorithms, Design, Performance

Keywords:
flash memory, memory layout, virtual memory, wireless sensor networks