Code compression for embedded systems

ABSTRACT

Memory is one of the most restricted resources in many modern embedded systems. Code compression can provide substantial savings in terms of size. In a compressed code CPU, a cache miss triggers the decompression of a main memory block, before it gets transferred to the cache. Because the code must be decompressible starting from any point (or at least at cache block boundaries), most file-oriented compression techniques cannot be used. We propose two algorithms to compress code in a space-efficient and simple to decompress way, one which is independent of the instruction set and another which depends on the instruction set. We perform experiments on two instruction sets, a typical RISC (MIPS) and a typical CISC (x86) and compare our results to existing file-oriented compression algorithms.

REFERENCES

• 1: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 2: 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]
• 3: G. V. Ormack , R. N. S. Horspool, Data compression using dynamic Markov modelling, The Computer Journal, v.30 n.6, p.541-550, Dec. 1987
• 4: D.Huffman. A method for the construction of minimum redundancy codes. In Proceedings of the IRE,volume Vol. 4D,pages pp 1098-1101, September 1952.
• 5: 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
• 6: 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
• 7: A .Mayne and E. James. Information compression by factoring common strings. Computer Journal Vol.18(No2)-pp 157-160,1975
• 8: A. Moffat. Word based text compression. Technical report, Department of Computer Science, University of Mcl bourne,Parkville,Victoria,Australia,1987.
• 9: J. Rissanen and G.Landon Universal modeling and coding. ZEEE ,Transactions on Information Theory, Vol.27pp 12- 23, 1981.
• 10: J. Storer. NP-completeness results concerning data compression. Technical Report No 234, Department of Electrical Engineering and Computer Science, Princeton University, Princeton, 1977.
• 11: T. Welch. A technique for high performance data compression. IEEE Computer, pages pp 8-19, June 1984.
• 12: 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]
• 13: 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
• 14: J.Zie and A. Lempel. A universal algorithm for sequential data compression. IEEE on Information Theory, Vol.23(No3)pp. 337-343, May 1977.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Instruction set design (e.g., RISC, CISC, VLIW)

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

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory

Keywords:
MPEG4, codec, design automatian, flip-flops, level converters, low power, placement, synthesis, voltage scaling