Survey of code-size reduction methods

ABSTRACT

Program code compression is an emerging research activity that is having an impact in several production areas such as networking and embedded systems. This is because the reduced-sized code can have a positive impact on network traffic and embedded system costs such as memory requirements and power consumption. Although code-size reduction is a relatively new research area, numerous publications already exist on it. The methods published usually have different motivations and a variety of application contexts. They may use different principles and their publications often use diverse notations. To our knowledge, there are no publications that present a good overview of this broad range of methods and give a useful assessment. This article surveys twelve methods and several related works appearing in some 50 papers published up to now. We provide extensive assessment criteria for evaluating the methods and offer a basis for comparison. We conclude that it is fairly hard to make any fair comparisons of the methods or draw conclusions about their applicability.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Araújo, G., Centoducatte, P., Azevedo, R., and Pannain, R. 2000a. Expression tree based algorithms for code compression on embedded RISC architectures. Tech. Rep. IC-00-01, Instituto de Computação---UNICAMP. Jan.
• 3: Guido Araujo , Paolo Centoducatte , Rodolfo Azevedo , Ricardo Pannain, Expression-tree-based algorithms for code compresion on embedded RISC architectures, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.5, p.530-533, Oct., 2000 [doi>10.1109/92.894158]
• 4: 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
• 5: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 6: 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
• 7: 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
• 8: 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]
• 9: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 10: Bird, P. L. and Mudge, T. N. 1996. An instruction stream compression technique. Tech. Rep. CSE-TR-319-96, EECS Department, University of Michigan. Nov.
• 11: 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
• 12: Paulo Centoducatte , Guido Araujo , Ricardo Pannain, Compressed Code Execution on DSP Architectures, Proceedings of the 12th international symposium on System synthesis, p.56, November 01-04, 1999
• 13: Chen, I.-C. K., Bird, P. L., and Mudge, T. N. 1997. The impact of instruction compression on I-cache performance. Tech. Rep. CSE-TR-330-97, EECS Department, University of Michigan.
• 14: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, ACM SIGPLAN Notices, v.34 n.5, p.139-149, May 1999
• 15: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 16: 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
• 17: Franz, M. 1994. Code-generation on-the-fly: A key to portable software. Ph.D. dissertation, ETH Zürich.
• 18: 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
• 19: Michael Franz , Thomas Kistler, Slim binaries, Communications of the ACM, v.40 n.12, p.87-94, Dec. 1997 [doi>10.1145/265563.265576]
• 20: Christopher W. Fraser, Automatic inference of models for statistical code compression, ACM SIGPLAN Notices, v.34 n.5, p.242-246, May 1999
• 21: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.117-121, June 17-22, 1984, Montreal, Canada
• 22: Fraser, C. W. and Proebsting, T. A. 1995. Custom instruction sets for code compression. Unpublished manuscript. http://research. microsoft.com/˜toddpro/papers/pldi2.ps.
• 23: Darrel Hankerson , Peter D. Johnson , Greg A. Harris, Introduction to Information Theory and Data Compression, CRC Press, Inc., Boca Raton, FL, 1998
• 24: Barry G. Haskell , Atul Puri , Arun N. Netravali, Digital Video: An introduction to MPEG-2, Chapman & Hall, Ltd., London, UK, 1996
• 25: 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]
• 26: Howard, P. G. and Vitter, J. S. 1992. Practical implementations of arithmetic coding. Image Text Compres., 85--112.
• 27: Huffman, D. A. 1952. A method for the construction of minimum redundancy codes. Proc. IERE 40, 1098--1101.
• 28: IBM. 1998. CodePack: PowerPC Code Compression Utility User's Manual Version 3.0. International Business Machines (IBM) Corporation.
• 29: 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
• 30: 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
• 31: 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
• 32: Charles Robert Lefurgy , Trevor Mudge, Efficient execution of compressed programs, 2000
• 33: 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
• 34: Lefurgy, C. R. and Mudge, T. N. 1998. Code compression for DSP. Technical Report CSE-TR-380-98, EECS Department, University of Michigan. Nov.
• 35: 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
• 36: Lefurgy, C. R., Piccininni, E., and Mudge, T. N. 2000. Reducing code size with run-time decompression. In Proceedings of the 6th International Symposium on High-Performance Computer Architecture (HPCA).
• 37: Haris Lekatsas , Wayne Wolf , Joerg Henkel, Arithmetic Coding for Low Power Embedded System Design, Proceedings of the Conference on Data Compression, p.430, March 28-30, 2000
• 38: 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]
• 39: 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]
• 40: 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]
• 41: Haris Lekatsas , Wayne Wolf, Random Access Decompression using Binary Arithmetic Coding, Proceedings of the Conference on Data Compression, p.306, March 29-31, 1999
• 42: Lekatsas, H. and Wolf, W. 1999b. SAMC: A code compression algorithm for embedded processors. IEEE Trans. CAD 18, 12 (Dec.), 1689--1701.
• 43: Lempel, A. and Ziv, J. 1976. On the complexity of finite sequences. IEEE Trans. Inf. Theory 22, 1 (Jan.), 75--81.
• 44: Stan Liao , Srinivas Devadas , Kurt Keutzer, A text-compression-based method for code size minimization in embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.1, p.12-38, Jan. 1999 [doi>10.1145/298865.298867]
• 45: 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
• 46: Robert Michael Muth , Saumya K. Debray, Alto: a platform for object code modification, 1999
• 47: Muth, R., Debray, S. K., Watterson, S., and Bosschere, K. D. 1998. alto: A link-time optimizer for the DEC Alpha. Tech. Rep. 98-14, Dept. of Computer Science, The University of Arizona. Dec.
• 48: Mark Nelson , Jean-Loup Gailly, The data compression book (2nd ed.), MIS:Press, New York, NY, 1995
• 49: van de Wiel, R. 2001. The code compaction bibliography. http://www.extra.research.philips.com/ccb/
• 50: van de Wiel, R., Augusteijn, L., Bink, A., and Hoogendijk, P. 2001. Code compaction: Reducing memory cost of embedded software. Philips white paper. See http://www.extra. research.philips.com/
• 51: van de Wiel, R. and Hoogendijk, P. 2001. Belt-tightening in software. Philips Res. Passw. Mag., 16--19.
• 52: Welch, T. A. 1984. A technique for high-performance data compression. Comput. Mag. Comput. Group News IEEE Comput. Group Soc. 17, 6 (June), 8--19.
• 53: Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]
• 54: 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
• 55: 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]
• 56: Ziv, J. and Lempel, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23, 3 (May), 337--343.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.1 INTRODUCTORY AND SURVEY

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

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

General Terms:
Algorithms, Measurement

Keywords:
code compaction, code compression, method assessment, method evaluation