Access pattern-based code compression for memory-constrained systems

ABSTRACT

As compared to a large spectrum of performance optimizations, relatively less effort has been dedicated to optimize other aspects of embedded applications such as memory space requirements, power, real-time predictability, and reliability. In particular, many modern embedded systems operate under tight memory space constraints. One way of addressing this constraint is to compress executable code and data as much as possible. While researchers on code compression have studied efficient hardware and software based code compression strategies, many of these techniques do not take application behavior into account; that is, the same compression/decompression strategy is used irrespective of the application being optimized. This article presents an application-sensitive code compression strategy based on control flow graph (CFG) representation of the embedded program. The idea is to start with a memory image wherein all basic blocks of the application are compressed, and decompress only the blocks that are predicted to be needed in the near future. When the current access to a basic block is over, our approach also decides the point at which the block could be compressed. We propose and evaluate several compression and decompression strategies that try to reduce memory requirements without excessively increasing the original instruction cycle counts. Some of our strategies make use of profile data, whereas others are fully automatic. Our experimental evaluation using seven applications from the MediaBench suite and three large embedded applications reveals that the proposed code compression strategy is very successful in practice. Our results also indicate that working at a basic block granularity, as opposed to a procedure granularity, is important for maximizing memory space savings.

REFERENCES

• 1: Abali, B., Franke, H., Poff, D. E., Saccone, R. A., Schulz, C. O., Herger, L. M., and Smith, T. B. 2001. Memory expansion technology (mxt): Software support and performance. IBM J. Resea. Devel. 45, 2.
• 2: Guido Araujo , Paulo Centoducatte , Mario Cartes , Ricardo Pannain, Code compression based on operand factorization, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.194-201, November 1998, Dallas, Texas, United States
• 3: Todd Austin , Eric Larson , Dan Ernst, SimpleScalar: An Infrastructure for Computer System Modeling, Computer, v.35 n.2, p.59-67, February 2002 [doi>10.1109/2.982917]
• 4: Oren Avissar , Rajeev Barua , Dave Stewart, An optimal memory allocation scheme for scratch-pad-based embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.6-26, November 2002 [doi>10.1145/581888.581891]
• 5: Rajeshwari Banakar , Stefan Steinke , Bo-Sik Lee , M. Balakrishnan , Peter Marwedel, Scratchpad memory: design alternative for cache on-chip memory in embedded systems, Proceedings of the tenth international symposium on Hardware/software codesign, May 06-08, 2002, Estes Park, Colorado [doi>10.1145/774789.774805]
• 6: 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
• 7: Luca Benini , Alberto Macii , Enrico Macii , Massimo Poncino, Selective instruction compression for memory energy reduction in embedded systems, Proceedings of the 1999 international symposium on Low power electronics and design, p.206-211, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313927]
• 8: Caroline D. Benveniste , Peter A. Franaszek , John T. Robinson, Cache-Memory Interfaces in Compressed Memory Systems, IEEE Transactions on Computers, v.50 n.11, p.1106-1116, November 2001 [doi>10.1109/12.966489]
• 9: Árpád Beszédes , Rudolf Ferenc , Tibor Gyimóthy , André Dolenc , Konsta Karsisto, Survey of code-size reduction methods, ACM Computing Surveys (CSUR), v.35 n.3, p.223-267, September 2003 [doi>10.1145/937503.937504]
• 10: Talal Bonny , Joerg Henkel, Using Lin-Kernighan algorithm for look-up table compression to improve code density, Proceedings of the 16th ACM Great Lakes symposium on VLSI, April 30-May 01, 2006, Philadelphia, PA, USA [doi>10.1145/1127908.1127969]
• 11: Talal Bonny , Joerg Henkel, Efficient code density through look-up table compression, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 12: Enhanced compression techniques to simplify program decompression and execution, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.170, October 12-15, 1997
• 13: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• 14: Keith D. Cooper , Timothy J. Harvey, Compiler-controlled memory, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.2-11, October 02-07, 1998, San Jose, California, United States
• 15: 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
• 16: Dipankar Das , Rajeev Kumar , P. P. Chakrabarti, Dictionary Based Code Compression for Variable Length Instruction Encodings, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design, p.545-550, January 03-07, 2005 [doi>10.1109/ICVD.2005.81]
• 17: 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
• 18: Debray, S., Evans, W., and Muth, R. 1999. Compiler techniques for code compression. Tech. rep. TR99-07. Friday, 23.
• 19: Saumya Debray , William S. Evans, Cold code decompression at runtime, Communications of the ACM, v.46 n.8, August 2003 [doi>10.1145/859670.859698]
• 20: Milenko Drinić , Darko Kirovski , Hoi Vo, Code optimization for code compression, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 21: 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
• 22: Poletti Francesco , Paul Marchal , David Atienza , Luca Benini , Francky Catthoor , Jose M. Mendias, An integrated hardware/software approach for run-time scratchpad management, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996634]
• 23: Michael Franz, Adaptive Compression of Syntax Trees and Iterative Dynamic Code Optimization: Two Basic Technologies for Mobile Object Systems, Selected Presentations and Invited Papers Second International Workshop on Mobile Object Systems - Towards the Programmable Internet, p.263-276, July 08-09, 1996
• 24: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 25: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, ACM SIGPLAN Notices, v.19 n.6, p.117-121, June 1984
• 26: Fraser, C. W. and Proebsting, T. A. 1995. Custom instruction set for code compression. Unpublished manuscript. http://research.microsoft.com/~toddpro/papers/pldiz.ps.
• 27: Mary W. Hall , Ken Kennedy, Efficient call graph analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.3, p.227-242, Sept. 1992 [doi>10.1145/151640.151643]
• 28: Jan Hoogerbrugge , Lex Augusteijn , Jeroen Trum , Rik Van De Wiel, A code compression system based on pipelined interpreters, Software—Practice & Experience, v.29 n.11, p.1005-2023, Sept. 1999 [doi>10.1002/(SICI)1097-024X(199909)29:11<1005::AID-SPE270>3.0.CO;2-F]
• 29: M. Kandemir , J. Ramanujam , J. Irwin , N. Vijaykrishnan , I. Kadayif , A. Parikh, Dynamic management of scratch-pad memory space, Proceedings of the 38th conference on Design automation, p.690-695, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379049]
• 30: T. M. Kemp , R. K. Montoye , J. D. Harper , J. D. Palmer , D. J. Auerbach, A decompression core for powerPC, IBM Journal of Research and Development, v.42 n.6, p.807-812, November 1998
• 31: 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
• 32: Kissel, K. D. 1997. Mips16: High-density mips for the embedded market. In Proceedings of Real Time Systems.
• 33: Sergei Y. Larin , Thomas M. Conte, Compiler-driven cached code compression schemes for embedded ILP processors, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.82-92, November 16-18, 1999, Haifa, Israel
• 34: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 35: 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
• 36: Charles Lefurgy , Eva Piccininni , Trevor Mudge, Evaluation of a high performance code compression method, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.93-102, November 16-18, 1999, Haifa, Israel
• 37: Lefurgy, C., Piccininni, E., and Mudge, T. 2000. Reducing code size with run-time decompression. In Proceedings of the 6th International Symposium on High-Performance Computer Architecture. 218--227.
• 38: Haris Lekatsas , Henkel Henkel , Srimat Chakradhar , Venkata Jakkula, Cypress: Compression and Encryption of Data and Code for Embedded Multimedia Systems, IEEE Design & Test, v.21 n.5, p.406-415, September 2004 [doi>10.1109/MDT.2004.55]
• 39: Haris Lekatsas , Jorg Henkel , Venkata Jakkula , Srimat Chakradhar, A Unified Architecture for Adaptive Compression of Data and Code on Embedded Systems, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design, p.117-123, January 03-07, 2005 [doi>10.1109/ICVD.2005.36]
• 40: Haris Lekatsas , Jörg Henkel , Wayne Wolf, Code compression as a variable in hardware/software co-design, Proceedings of the eighth international workshop on Hardware/software codesign, p.120-124, May 2000, San Diego, California, United States [doi>10.1145/334012.334035]
• 41: 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]
• 42: Lempel, Ziv, and Oberhumer. Lzo algorithm.
• 43: 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
• 44: 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
• 45: L. Lingappan , S. Ravi , A. Raghunathan , N. K. Jha , S. T. Chakradhar, Heterogeneous and Multi-Level Compression Techniques for Test Volume Reduction in Systems-on-Chip, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design, p.65-70, January 03-07, 2005 [doi>10.1109/ICVD.2005.104]
• 46: Ltd. A. R. M. 1996. An introduction to thumb. http://www.win.tue.nl/cs/ps/rikvdw/papers/ARM95.pdf
• 47: Steven Lucco, Split-stream dictionary program compression, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.27-34, June 18-21, 2000, Vancouver, British Columbia, Canada
• 48: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 49: O. Ozturk , H. Saputra , M. Kandemir , I. Kolcu, Access Pattern-Based Code Compression for Memory-Constrained Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.882-887, March 07-11, 2005 [doi>10.1109/DATE.2005.46]
• 50: Preeti Ranjan Panda , Alexandru Nicolau , Nikil Dutt, Memory Issues in Embedded Systems-on-Chip: Optimizations and Exploration, Kluwer Academic Publishers, Norwell, MA, 1998
• 51: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 52: 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
• 53: Montserrat Ros , Peter Sutton, A post-compilation register reassignment technique for improving hamming distance code compression, 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.1086311]
• 54: Seok-Won Seong , Prabhat Mishra, A bitmask-based code compression technique for embedded systems, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233551]
• 55: Seok-Won Seong , Prabhat Mishra, An efficient code compression technique using application-aware bitmask and dictionary selection methods, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 56: 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
• 57: Tunstall, B. 1967. Synthesis of noiseless compression codes. Ph.D. thesis, Georgia Institute of Technology, Atlanta, GA.
• 58: Sumesh Udayakumaran , Rajeev Barua, Compiler-decided dynamic memory allocation for scratch-pad based embedded systems, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951747]
• 59: William E. Weihl, Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.83-94, January 28-30, 1980, Las Vegas, Nevada [doi>10.1145/567446.567455]
• 60: 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
• 61: 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
• 62: Jun Yang , Youtao Zhang , Rajiv Gupta, Frequent value compression in data caches, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.258-265, December 2000, Monterey, California, United States [doi>10.1145/360128.360154]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Memory management (garbage collection)

General Terms:
Design, Experimentation, Management, Performance

Keywords:
CFG, Embedded systems, code access pattern, code compression, memory optimization