Offline compression for on-chip ram

ABSTRACT

We present offline RAM compression, an automated source-to-source transformation that reduces a program's data size. Statically allocated scalars, pointers, structures, and arrays are encoded and packed based on the results of a whole-program analysis in the value set and pointer set domains. We target embedded software written in C that relies heavily on static memory allocation and runs on Harvard-architecture microcontrollers supporting just a few KB of on-chip RAM. On a collection of embedded applications for AVR microcontrollers, our transformation reduces RAM usage by an average of 12%, in addition to a 10% reduction through a dead-data elimination pass that is also driven by our whole-program analysis, for a total RAM savings of 22%. We also developeda technique for giving developers access to a flexible spectrum of tradeoffs between RAM consumption, ROM consumption, and CPU efficiency. This technique is based on a model for estimating the cost/benefit ratio of compressing each variable and then selectively compressing only those variables that present a good value proposition in terms of the desired tradeoffs.

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: Lan S. Bai , Lei Yang , Robert P. Dick, Automated compile-time and run-time techniques to increase usable memory in MMU-less embedded systems, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176777]
• 3: Gogul Balakrishnan and Thomas Reps. Analyzing memory accesses in x86 executables. In Proc. of the Intl. Conf. on Compiler Construction (CC), pages 5--23, Bonita Springs, FL, April 2004.
• 4: Ross Bannatyne. Microcontrollers for the automobile. Micro Control Journal, 2004. http://www.mcjournal.com/articles/arc105/arc105.htm.
• 5: Max Baron and Cheryl Cadden. Strong growth to continue for MCU market, 2005. http://www.instat.com/press.asp?ID=1445&sku=IN0502457SI.
• 6: Volker Barthelmann, Inter-task register-allocation for static operating systems, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 7: 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]
• 8: David Brooks , Margaret Martonosi, Dynamically Exploiting Narrow Width Operands to Improve Processor Power and Performance, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.13, January 09-12, 1999
• 9: Mihai Budiu , Majd Sakr , Kip Walker , Seth Copen Goldstein, BitValue Inference: Detecting and Exploiting Narrow Bitwidth Computations, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.969-979, August 29-September 01, 2000
• 10: Dominique Chanet , Bjorn De Sutter , Bruno De Bus , Ludo Van Put , Koen De Bosschere, System-wide compaction and specialization of the linux kernel, Proceedings of the 2005 ACM SIGPLAN/SIGBED conference on Languages, compilers, and tools for embedded systems, June 15-17, 2005, Chicago, Illinois, USA
• 11: Trishul M. Chilimbi , Bob Davidson , James R. Larus, Cache-conscious structure definition, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.13-24, May 01-04, 1999, Atlanta, Georgia, United States
• 12: Nathan Cooprider , John Regehr, Pluggable abstract domains for analyzing embedded software, Proceedings of the 2006 ACM SIGPLAN/SIGBED conference on Language, compilers, and tool support for embedded systems, June 14-16, 2006, Ottawa, Ontario, Canada
• 13: 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
• 14: Dirk Grunwald , Richard Neves, Whole-program optimization for time and space efficient threads, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.50-59, October 01-04, 1996, Cambridge, Massachusetts, United States
• 15: 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
• 16: 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]
• 17: Chris Karlof , Naveen Sastry , David Wagner, TinySec: a link layer security architecture for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031515]
• 18: Chris Lattner , Vikram S. Adve, Transparent pointer compression for linked data structures, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111587]
• 19: Bhuvan Middha , Matthew Simpson , Rajeev Barua, MTSS: multi task stack sharing for embedded systems, 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.1086323]
• 20: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 21: Ozcan Ozturk , Mahmut Kandemir , Mary Jane Irwin, Increasing on-chip memory space utilization for embedded chip multiprocessors through data compression, 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.1084860]
• 22: The Paparazzi project, 2006. http://www.nongnu.org/paparazzi.
• 23: Rodric M. Rabbah , Krishna V. Palem, Data remapping for design space optimization of embedded memory systems, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.2, p.186-218, May 2003 [doi>10.1145/643470.643474]
• 24: Rahul Razdan , Michael D. Smith, A high-performance microarchitecture with hardware-programmable functional units, Proceedings of the 27th annual international symposium on Microarchitecture, p.172-180, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192749]
• 25: John Regehr , Alastair Reid , Kirk Webb, Eliminating stack overflow by abstract interpretation, ACM Transactions on Embedded Computing Systems (TECS), v.4 n.4, p.751-778, November 2005 [doi>10.1145/1113830.1113833]
• 26: Mark Stephenson , Jonathan Babb , Saman Amarasinghe, Bidwidth analysis with application to silicon compilation, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.108-120, June 18-21, 2000, Vancouver, British Columbia, Canada
• 27: Michael Stilkerich , Christian Wawersich , Andreas Gal , Wolfgang Schröder-Preikschat , Michael Franz, OSEK/VDX API for Java, Proceedings of the 3rd workshop on Programming languages and operating systems: linguistic support for modern operating systems, p.4-es, October 22-22, 2006, San Jose, California [doi>10.1145/1215995.1215999]
• 28: 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
• 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: Clark Verbrugge , Phong Co , Laurie J. Hendren, Generalized Constant Propagation: A Study in C, Proceedings of the 6th International Conference on Compiler Construction, p.74-90, April 24-26, 1996
• 31: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]
• 32: Lei Yang, Robert P. Dick, Haris Lekatsas, and Srimat Chakradhar. On-line memory compression for embedded systems. ACM Trans. Embedded Computing Systems (TECS), 2006.
• 33: Youtao Zhang , Rajiv Gupta, Compressing heap data for improved memory performance: Research Articles, Software—Practice & Experience, v.36 n.10, p.1081-1111, August 2006 [doi>10.1002/spe.v36:10]

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: Optimization

General Terms:
Languages, Performance

Keywords:
TinyOS, data compression, embedded software, memory optimization, sensor networks, static analysis