MEMMU: Memory expansion for MMU-less embedded systems

ABSTRACT

Random access memory (RAM) is tightly constrained in the least expensive, lowest-power embedded systems such as sensor network nodes and portable consumer electronics. The most widely used sensor network nodes have only 4 to 10KB of RAM and do not contain memory management units (MMUs). It is difficult to implement complex applications under such tight memory constraints. Nonetheless, price and power-consumption constraints make it unlikely that increases in RAM in these systems will keep pace with the increasing memory requirements of applications.

We propose the use of automated compile-time and runtime techniques to increase the amount of usable memory in MMU-less embedded systems. The proposed techniques do not increase hardware cost, and require few or no changes to existing applications. We have developed runtime library routines and compiler transformations to control and optimize the automatic migration of application data between compressed and uncompressed memory regions, as well as a fast compression algorithm well suited to this application. These techniques were experimentally evaluated on Crossbow TelosB sensor network nodes running a number of data-collection and signal-processing applications. Our results indicate that available memory can be increased by up to 50% with less than 10% performance degradation for most benchmarks.

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: Utpal K. Banerjee, Loop Transformations for Restructuring Compilers: The Foundations, Kluwer Academic Publishers, Norwell, MA, 1993
• 3: Surupa Biswas , Matthew Simpson , Rajeev Barua, Memory overflow protection for embedded systems using run-time checks, reuse and compression, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023872]
• 4: Choudhuri, S. and Givargis, T. 2005. Software virtual memory management for MU-less embedded systems. Tech. rep., Center for Embedded Computer Systems, University of California, Irvine.
• 5: Nathan Dean Cooprider , John David Regehr, Offline compression for on-chip ram, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 6: Douglis, F. 1993. The compression cache: Using online compression to extend physical memory. In Proceedings of the USENIX Conference. 519--529.
• 7: Dowding, C. H. and McKenna, L. M. 2005. Crack response to long-term and environmental and blast vibration effects. J. Geotech. Geoenviron. Eng. 131, 9, 1151--1161.
• 8: Vadim Engelson , Dag Fritzson , Peter Fritzson, Lossless Compression of High-volume Numerical Data from Simulations, Proceedings of the Conference on Data Compression, p.574, March 28-30, 2000
• 9: Björn Franke , Michael F. P. O'Boyle, Compiler Transformation of Pointers to Explicit Array Accesses in DSP Applications, Proceedings of the 10th International Conference on Compiler Construction, p.69-85, April 02-06, 2001
• 10: Prasanth Ganesan , Ramnath Venugopalan , Pushkin Peddabachagari , Alexander Dean , Frank Mueller , Mihail Sichitiu, Analyzing and modeling encryption overhead for sensor network nodes, 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.941372]
• 11: David Gay , Phil Levis , David Culler, Software design patterns for TinyOS, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 12: Gay, D., Levis, P., Culler, D., and Brewer, E. 2003. nesC 1.1 language reference manual. http://nescc.sourceforge.net/papers/nesc-ref.pdf.
• 13: Johannes Gehrke , Samuel Madden, Query Processing in Sensor Networks, IEEE Pervasive Computing, v.3 n.1, p.46-55, January 2004 [doi>10.1109/MPRV.2004.1269131]
• 14: Carlos Guestrin , Peter Bodik , Romain Thibaux , Mark Paskin , Samuel Madden, Distributed regression: an efficient framework for modeling sensor network data, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984624]
• 15: Carl Hartung , Richard Han , Carl Seielstad , Saxon Holbrook, FireWxNet: a multi-tiered portable wireless system for monitoring weather conditions in wildland fire environments, Proceedings of the 4th international conference on Mobile systems, applications and services, June 19-22, 2006, Uppsala, Sweden [doi>10.1145/1134680.1134685]
• 16: Joseph M. Hellerstein , Wei Wang, Optimization of in-network data reduction, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada [doi>10.1145/1052199.1052207]
• 17: Karlof, C. and Wagner, D. 2003. Secure routing in wireless sensor networks: attacks and countermeasures. Elsevier's AdHoc Networks J. 1, 2--3, 293--315.
• 18: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 19: Haris Lekatsas , Jörg Henkel , Wayne Wolf, Code compression for low power embedded system design, Proceedings of the 37th conference on Design automation, p.294-299, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337423]
• 20: Li, D., Wong, K., Hu, Y., and Sayeed, A. 2002. Detection, classification, and tracking of targets. Signal Process. Mag. 19, 2, 17--29.
• 21: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 22: Kathryn S. McKinley , Steve Carr , Chau-Wen Tseng, Improving data locality with loop transformations, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.424-453, July 1996 [doi>10.1145/233561.233564]
• 23: MEMMU. Memory expansion on embedded systems without MMUs. http://robertdick.org/tools/html.
• 24: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 25: Suman Nath , Phillip B. Gibbons , Srinivasan Seshan , Zachary R. Anderson, Synopsis diffusion for robust aggregation in sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031525]
• 26: Oberhumer, M. F. LZO real-time data compression library. http://www.oberhumer.com/opensource/lzo.
• 27: Pereira, C., Gupta, S., Niyogi, K., Lazaridis, I., Mehrotra, S., and Gupta, R. 2003. Energy efficient communication for reliability and quality aware sensor networks. Tech. rep., University of California at Irvine.
• 28: Joseph Polastre , Robert Szewczyk , David Culler, Telos: enabling ultra-low power wireless research, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 29: Joseph Polastre , Robert Szewczyk , Alan Mainwaring , David Culler , John Anderson, Analysis of wireless sensor networks for habitat monitoring, Wireless sensor networks, Kluwer Academic Publishers, Norwell, MA, 2004
• 30: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 31: Pradhan, S. S., Kusuma, J., and Ramchandran, K. 2002. Distributed compression in a dense microsensor network. IEEE Signal Process. Mag. 19, 2, 51--60.
• 32: Luigi Rizzo, A very fast algorithm for RAM compression, ACM SIGOPS Operating Systems Review, v.31 n.2, p.36-45, April 1997 [doi>10.1145/250007.250012]
• 33: Matthew Simpson , Bhuvan Middha , Rajeev Barua, Segment protection for embedded systems using run-time checks, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086307]
• 34: Szewczyk, R., Polastre, J., Mainwaring, A., and Culler, D. 2004. Lessons from a sensor network expedition. In Proceedings of the 1st European Workshop on Sensor Networks. Springer, Berlin, Germany.
• 35: Tarjan, D., Thoziyoor, S., and Jouppi, N. P. 2006. CACTI 4.0. Tech. rep., HP Laboratories.
• 36: 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]
• 37: Tremaine, B., Franaszek, P. A., Robinson, J. T., Schulz, C. O., Smith, T. B., Wazlowski, M., and Bland, P. M. 2001. IBM memory expansion technology. IBM J. Res. Dev. 45, 2, 271--285.
• 38: Irina Chihaia Tuduce , Thomas Gross, Adaptive main memory compression, Proceedings of the annual conference on USENIX Annual Technical Conference, p.29-29, April 10-15, 2005, Anaheim, CA
• 39: An Efficient Algorithm for Pointer-to-Array Access Conversion for Compiling and Optimizing DSP Applications, Proceedings of the Innovative Architecture for Future Generation High-Performance Processors and Systems (IWIA'01), p.80, January 18-19, 2001
• 40: Paul R. Wilson , Scott F. Kaplan , Yannis Smaragdakis, The case for compressed caching in virtual memory systems, Proceedings of the annual conference on USENIX Annual Technical Conference, p.8-8, June 06-11, 1999, Monterey, California
• 41: Lei Yang , Robert P. Dick , Haris Lekatsas , Srimat Chakradhar, CRAMES: compressed RAM for embedded systems, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084861]
• 42: Lei Yang , Haris Lekatsas , Robert P. Dick, High-performance operating system controlled memory compression, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147086]

INDEX TERMS

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

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Design, Experimentation, Management, Performance

Keywords:
Data compression, embedded system, wireless sensor network