Procedure based program compression

ABSTRACT

Cost and power consumption are two of the most important design factors for many embedded systems, particularly consumer devices. Products such as personal digital assistants, pagers with integrated data services and smart phones have fixed performance requirements but unlimited appetites for reduced cost and increased battery life. Program compression is one technique that can be used to attack both of these problems. Compressed programs require less memory, thus reducing the cost of both direct materials and manufacturing. Furthermore, by relying on compressed memory, the total number of memory references is reduced. This reduction saves power by lowering the traffic on high-capacitance buses. This paper discusses a new approach to implementing transparent program compression that requires little or no hardware support. Procedures are compressed individually, and a directory structure is used to bind them together at run-time. Decompressed procedures are explicitly cached in ordinary RAM as complete units, thus resolving references within each procedure. This approach has been evaluated on a set of 25 embedded multimedia and communications applications, and results in an average memory reduction of 40% with a run-time performance overhead of 10%.

REFERENCES

• 1: Vincent Cate , Thomas Gross, Combining the concepts of compression and caching for a two-level filesystem, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.200-211, April 08-11, 1991, Santa Clara, California, United States
• 2: Andrew Wolfe , Alex Chanin, Executing compressed programs on an embedded RISC architecture, Proceedings of the 25th annual international symposium on Microarchitecture, p.81-91, December 01-04, 1992, Portland, Oregon, United States
• 3: Michael Kozuch , Andrew Wolfe, Compression of Embedded System Programs, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.270-277, October 10-12, 1994
• 4: D.A. Huffman, "A Method for the Construction of Minimum Redundancy Codes," Proceedings of the IEEE, vol. 40, pp. 1098-1101, 1952.
• 5: S. Y. Liao , S. Devadas , K. Keutzer, Code density optimization for embedded DSP processors using data compression techniques, Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95), p.272, March 27-29, 1995
• 6: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.358-365, June 16-18, 1997, Las Vegas, Nevada, United States
• 7: L. Peter Deutsch , Allan M. Schiffman, Efficient implementation of the smalltalk-80 system, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.297-302, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800542]
• 8: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Nancy J. Warter , Wen-mei W. Hwu, IMPACT: an architectural framework for multiple-instruction-issue processors, Proceedings of the 18th annual international symposium on Computer architecture, p.266-275, May 27-30, 1991, Toronto, Ontario, Canada
• 9: C. Lee, M. Potkonjak, and W. H. Mangione-Smith, "MediaBench: A Tool for Evaluating Multimedia and Communications Systems," Micro 30, 1997.
• 10: R. N. Williams, "An Extremely Fast ZivoLempel Data Compression Algorithm," Data Compression Conference, 1991.
• 11: Martin Benes , Andrew Wolfe , Steven M. Nowick, A High-Speed Asynchronous Decompression Circuit for Embedded Processors, Proceedings of the 17th Conference on Advanced Research in VLSI (ARVLSI '97), p.219, September 15-16, 1997

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS
      Subjects: Consumer products

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
RAM, battery life, cached procedures, communications applications, compressed memory, consumer devices, cost, design factors, directory structure, embedded systems, high-capacitance bus traffic, integrated data services, memory reduction, memory references, multimedia applications, pagers, performance requirements, personal digital assistants, power consumption, procedural reference resolution, procedure-based program compression, run-time performance overhead, smart telephones, source coding, transparent program compression