Compiler-Guided data compression for reducing memory consumption of embedded applications

ABSTRACT

Memory system presents one of the critical challenges on embedded system design and optimization. This is mainly due to ever-increasing code complexity of embedded applications and exponential increase witnessed in the amount of data they manipulate. As a result, reducing memory space occupancy of embedded applications is very important and will be even more important in the next decade. Motivated by this observation, this paper presents and evaluates a compiler-driven approach to data compression for reducing memory space occupancy. Our goal in this paper is to study how automated compiler support can help in deciding the set of data elements to compress/decompress and the points during execution at which these compressions/decompressions should be performed. The proposed compiler support achieves this by analyzing the source code of the application to be optimized and identifying the order in which the different data blocks are accessed. Based on this analysis, the compiler then automatically inserts compression/decompression calls in the application code. The compression calls target the data blocks that are not expected to be used in the near future, whereas the decompression calls target those data blocks with expected reuse but currently in compressed form.

REFERENCES

• 1: Bulent Abali , Mohammad Banikazemi , Xiawei Shen , Hubertus Franke , Dan E. Poff , T. Basil Smith, Hardware Compressed Main Memory: Operating System Support and Performance Evaluation, IEEE Transactions on Computers, v.50 n.11, p.1219-1233, November 2001 [doi>10.1109/12.966496]
• 2: Edward Ahn , Seung-Moon Yoo , Sung-Mo Steve Kang, Effective algorithms for cache-level compression, Proceedings of the 11th Great Lakes symposium on VLSI, p.89-92, March 2001, West Lafayette, Indiana, United States [doi>10.1145/368122.368872]
• 3: S. P. Amarasinghe, J. M. Anderson, M. S. Lam, and C. W. Tseng. The SUIF compiler for scalable parallel machines. In Proc. SIAM Conference on Parallel Processing for Scientific Computing, February, 1995.
• 4: T. M. Austin and D. Burger. The SimpleScalar architectural research tool set. http://www.cs.wisc.edu/~mscalar/simplescalar.html
• 5: L. Benini , D. Bruni , A. Macii , E. Macii, Hardware-Assisted Data Compression for Energy Minimization in Systems with Embedded Processors, Proceedings of the conference on Design, automation and test in Europe, p.449, March 04-08, 2002
• 6: C. D. Benveniste, P. A. Franaszek, and J. T. Robinson. Cache-Memory Interfaces in Compressed Memory Systems. In Proc. Workshop on Solving the Memory Wall Problem, June 2000.
• 7: M. Chen and M. L. Fowler. The importance of data compression for energy efficiency in sensor networks. In Proc. 2003 Conference on Information Sciences and Systems, The Johns Hopkins Univ., March 2003.
• 8: Stephanie Coleman , Kathryn S. McKinley, Tile size selection using cache organization and data layout, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.279-290, June 18-21, 1995, La Jolla, California, United States
• 9: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 10: 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
• 11: Design and Evaluation of a Selective Compressed Memory System, Proceedings of the 1999 IEEE International Conference on Computer Design, p.184, October 10-13, 1999
• 12: Chang Hong Lin , Yuan Xie , Wayne Wolf, LZW-Based Code Compression for VLIW Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.30076, February 16-20, 2004
• 13: LZO Algorithm. http://gnuwin32.sourceforge.net/packages/lzo.htm
• 14: The Omega Project. http://www.cs.umd.edu/projects/omega/
• 15: Montserrat Ros , Peter Sutton, Code Compression Based on Operand-Factorization for VLIW Processors, Proceedings of the Conference on Data Compression, p.559, March 23-25, 2004
• 16: B. P. Tunstall. Synthesis of Noiseless Compression Codes. PhD Thesis, Georgia Institute of Technology, Sept. 1967.
• 17: 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
• 18: 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
• 19: Yuan Xie , Wayne Wolf , Haris Lekatsas, Code compression for VLIW processors using variable-to-fixed coding, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581231]
• 20: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Memory technologies; Algorithms implemented in hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

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

General Terms:
Algorithms, Design, Performance