Profile-driven compression scheme for embedded systems

ABSTRACT

The extensive usage of embedded systems involves running complex applications that require tightly limited resources such as memory and storage. One efficient way to satisfy the resource requirements is to reduce the code size through code compression. Our work describes a software-based code compression scheme that reduces the storage space of a program, which in turn induces a reduction of access time to off-chip memory in SoC embedded architectures. To select those sections of code that are most advantageous for compression, our scheme utilizes profiling information to evaluate and trade off storage space reduction for future run-time overhead. During run-time, the compressed parts are decompressed as necessary into a run-time buffer for execution. Experimental results on the SPEC CPU2000 and MediaBench suites show reduction in code size averaging 18.5%, along with reasonable memory consumption overhead averaging 3.8%, and a reasonable run-time overhead averaging 7.8%.

REFERENCES

• 1: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 2: Martin Bene_ , Steven M. Nowick , Andrew Wolfe, A Fast Asynchronous Huffman Decoder for Compressed-Code Embedded Processors, Proceedings of the 4th International Symposium on Advanced Research in Asynchronous Circuits and Systems, p.0043, March 30-April 02, 1998
• 3: Luca Benini , Alberto Macii , Massimo Poncino, Energy-aware design of embedded memories: A survey of technologies, architectures, and optimization techniques, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.1, p.5-32, February 2003 [doi>10.1145/605459.605461]
• 4: Saumya Debray , William Evans, Profile-guided code compression, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 5: M. Game and A. Booker. "CodePack: Code Compression for PowerPC Processors". MicroNews 5(1), IBM, 1999.
• 6: Darko Kirovski , Johnson Kin , William H. Mangione-Smith, Procedure based program compression, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.204-213, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 7: 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
• 8: C. Lefurgy, E. Piccininni and T. Mudge. Reducing Code Size with Run-time Decompression. In Proceedings of the 6th International Symposium on High Performance Computer Architecture (HPCA 2000), January 2000, pp. 218.
• 9: Charles Lefurgy , Peter Bird , I-Cheng Chen , Trevor Mudge, Improving code density using compression techniques, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.194-203, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 10: Haris Lekatsas , Wayne Wolf, Code compression for embedded systems, Proceedings of the 35th annual conference on Design automation, p.516-521, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277185]
• 11: Haris Lekatsas , Wayne Wolf, Random Access Decompression using Binary Arithmetic Coding, Proceedings of the Conference on Data Compression, p.306, March 29-31, 1999
• 12: 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
• 13: Wayne Lyons, Meeting the Embedded Design Needs of Automotive Applications, Proceedings of the conference on Design, Automation and Test in Europe, p.142-147, March 07-11, 2005 [doi>10.1109/DATE.2005.205]
• 14: MediaBench. http://cares.icsl.ucla.edu/mediabench.
• 15: I. Nahshon and D. Bernstein. FDPR - A Post-Pass Object Code Optimization Tool. In Proceedings of the Poster Session of the 6th International Conference on Compiler Construction (CC'96), April 1996, pp. 97--104.
• 16: M. Nelson. DataCompression.info. http://datacompression.info/.
• 17: Stacey Shogan , Bruce R. Childers, Compact Binaries with Code Compression in a Software Dynamic Translator, Proceedings of the conference on Design, automation and test in Europe, p.21052, February 16-20, 2004
• 18: SPEC CPU2000. http://www.spec.org/cpu2000/.
• 19: M. Timmermans. BICOM BIjective COMpressor. http://www3.sympatico.ca/mt0000/bicom/.
• 20: R. N. Williams. An Extremely Fast Ziv-Lempel Data Compression Algorithm. In Proceedings of the IEEE Data Compression Conference (DCC 1991), April 1991, pp. 362--371.
• 21: 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
• 22: Yuan Xie , Wayne Wolf , Haris Lekatsas, Profile-Driven Selective Code Compression, Proceedings of the conference on Design, Automation and Test in Europe, p.10462, March 03-07, 2003
• 23: Yukihiro Yoshida , Bao-Yu Song , Hiroyuki Okuhata , Takao Onoye , Isao Shirakawa, An object code compression approach to embedded processors, Proceedings of the 1997 international symposium on Low power electronics and design, p.265-268, August 18-20, 1997, Monterey, California, United States [doi>10.1145/263272.263349]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
code compression, code size reduction, run-time decompression