Code compression as a variable in hardware/software co-design

ABSTRACT

We present a new way to practice and view handware/software co-design: rather than raising the level of abstraction in order to exploit the highest possible degree of optimization, we use code compression i.e. we practice co-design at the bit-level. Through our novel architecture combined with our compression methodology this results in optimization of all major design goals/constraints. In particular, we present a compression methodology that deploys what we call a “post-cache architecture” (i.e. the detached decompression unit is located between the CPU and the instruction cache). We present a design methodology that allows the designer to control parameters like speed, power, and area through the choice of compression parameters. In addition we show that our compression methodology (using a Markov Model) is more efficient than the widely used Huffman compression scheme.

REFERENCES

• 1: 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
• 2: P.G. Howard and J.S. Vitter, Practical Implementations of Arithmetic Coding, Image and Text Compression, Kluwer Academic Publishers, Norwell, MA, pp. 85-112, Kluwer Academic Publishers, Norwell, MA, 1992.
• 3: 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]
• 4: T. Okuma , H. Tomiyama , A. Inoue , E. Fajar , H. Yasuura, Instruction encoding techniques for area minimization of instruction ROM, Proceedings of the 11th international symposium on System synthesis, p.125-130, December 02-04, 1998, Hsinchu, Taiwan, China
• 5: 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
• 6: 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
• 7: Haris Lekatsas , Wayne Wolf, Random Access Decompression using Binary Arithmetic Coding, Proceedings of the Conference on Data Compression, p.306, March 29-31, 1999
• 8: 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]
• 9: 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
• 10: J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Transactions on Information Theory, Vol. 23(3), pp. 337-343, May, 1977.
• 11: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 12: 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
• 13: D.A. Huffman, A Method for the Construction of Minimum- Redundancy Codes, Proceedings of the IRE, vol 4D, pp. 1098- 1101, September, 1952.
• 14: 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]
• 15: Yanbing Li , Jörg Henkel, A framework for estimation and minimizing energy dissipation of embedded HW/SW systems, Proceedings of the 35th annual conference on Design automation, p.188-193, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277097]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

Additional Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING

General Terms:
Design, Theory