A software-only compression system for trading-offs between performance and code size

ABSTRACT

The design of an embedded system is often heavily constrained by its performance objective and budget envelope. Software code compression may reduce the instruction memory space and then the overall cost of the system. However, it may also induce performance degradation. Previous studies proposed selective code compression using profile information in order to reduce the performance penalty. In this paper, we go one step further. We propose a software-only compression system, called SCS, that automatically finds trade-offs between code size and performance. Through an iterative approach, SCS automatically determines which functions to be compressed given a performance constraint and/or a code size constraint in order to guarantee a minimal performance and a maximal code size for an application. Experimentations illustrate that even with a non-optimal software decompression approach, SCS achieves a high compression rate with a minimal performance degradation.

REFERENCES

• 1: Bjorn De Sutter , Hans Vandierendonck , Bruno De Bus , Koen De Bosschere, On the side-effects of code abstraction, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 2: Á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]
• 3: Saumya Debray , William Evans, Profile-guided code compression, ACM SIGPLAN Notices, v.37 n.5, May 2002
• 4: 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
• 5: Liam Goudge , Simon Segars, Thumb: Reducing the Cost of 32-bit RISC Performance in Portable and Consumer Applications, Proceedings of the 41st IEEE International Computer Conference, p.176, February 25-28, 1996
• 6: The PowerPC Processor Reference Guide. http://www.xilinx.com/bvdocs/userguides/ppc_ref_guide.pdf.
• 7: H263.http://www.ee.ubc.ca/image/h263plus/.
• 8: K. Heydemann. Schéma global de compilation sous contrainte pour la recherche de compromis entre la taille d'un code et sa performance. PhD thesis, University of Rennes 1, France, 2004.
• 9: 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]
• 10: D. A. Huffman. A method for a construction of minimum redundancy codes. IERE, 40(9):1098--1101, 1952.
• 11: K. Kissell. Mips16: High-density MIPS for the embedded market. Silicon Graphics MIPS Group, 1997.
• 12: T. Kisuki , P. M. W. Knijnenburg , M. F. P. O'Boyle, Combined Selection of Tile Sizes and Unroll Factors Using Iterative Compilation, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.237, October 15-19, 2000
• 13: 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
• 14: 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
• 15: C. Lefurgy, E. Piccininni, and T. N. Mudge. Reducing code size with run-time decompression. In Proc. of HPCA, pages 218--227, 2000.
• 16: Haris Lekatsas , Jörg Henkel , Wayne Wolf, Design and simulation of a pipelined decompression architecture for embedded systems, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada [doi>10.1145/500001.500015]
• 17: Haris Lekatsas , Jörg Henkel , Venkata Jakkula, Design of an one-cycle decompression hardware for performance increase in embedded systems, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513929]
• 18: 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]
• 19: The SPARC Architecture Manual. SPARC International Inc. http://www.sparc.org/standards/V8.pdf.
• 20: 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
• 21: Shukang Zhou , Bruce R. Childers , Naveen Kumar, Profile Guided Management of Code Partitions for Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.21396, February 16-20, 2004
• 22: MIPS32 Architecture For Programmers Vol. II: The MIPS32(tm) Instruction Set. 2001 MIPS Technologies, Inc. http://lsdpl.net/references.html.
• 23: 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
• 24: J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5):530--536, 1978.