A text-compression-based method for code size minimization in embedded systems

ABSTRACT

We address the problem of code-size minimization in VLSI systems with embedded DSP processors. Reducing code size reduces the production cost of embedded systemswe use data-compression methods to develop code-size minimization strategies. In our framework, the compressed program consists of a skeleton and a dictionary. We show that the dictionary can be computed by solving a set-covering problem derived from the original program. To execute the compressed code, we describe two methods that have different performance characteristics and different degrees of freedom in compressing the code. We also address performance considerations, and show that they can be incorporated easily into the set-covering formulation, and present experimental results obtained with Texas Instruments' optimizing TMS3220C25 compiler.

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: BRAYTON, R. K. AND SOMENZI, F. 1989. Boolean relations and the incomplete specification of logic networks. In Proceedings of the International Conference on Computer-Aided Design (ICCAD). 316-319.
• 3: Olivier Coudert , Jean Chritophe Madre, New ideas for solving covering problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.641-646, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217603]
• 4: COUDERT, O. 1995. On solving binate covering problems. In Proceedings of the 32nd ACM/IEEE Conference on Design Automation. 197-202.
• 5: 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
• 6: Jack G. Ganssle, The Art of Programming Embedded Systems, Academic Press, Inc., Orlando, FL, 1991
• 7: GIMPEL, J. 1967. The minimization of TANT networks. IEEE Trans. Electron. Comput. EC-16, 1 (Feb.), 18-38.
• 8: GRASSELLI, A. AND LUCCIO, F. 1965. A method for minimizing the number of internal states in incompletely specified machines. IEEE Trans. Electron. Comput. EC-14, 3 (June), 350-359.
• 9: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 10: 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
• 11: MAYNE, A. AND JAMES, E. B. 1975. Information compression by factoring common strings. Comput. J. 18, 2, 157-160.
• 12: QUINE, W. V. O. 1959. On cores and prime implicants of truth functions. Am. Math. Monthly 66, 627-631.
• 13: RUDELL, R. 1989. Logic Synthesis for VLSI Design: ERL Memo 89/49. Computer Science Department, University of California at Berkeley, Berkeley, CA.
• 14: James A. Storer , Thomas G. Szymanski, Data compression via textual substitution, Journal of the ACM (JACM), v.29 n.4, p.928-951, Oct. 1982 [doi>10.1145/322344.322346]
• 15: TEXAS INSTRUMENTS, 1993. TMS320C2x User's Guide. Revision C. Texas Instruments, Austin, TX.
• 16: Robert A. Wagner, Common phrases and minimum-space text storage, Communications of the ACM, v.16 n.3, p.148-152, March 1973 [doi>10.1145/361972.361982]
• 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: ZIV, g. AND LEMPEL, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theor. IT-23, 3 (May), 337-343.

INDEX TERMS

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

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

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

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
code size optimization, compression