Using Lin-Kernighan algorithm for look-up table compression to improve code density

ABSTRACT

The presented work uses code compression to improve the design efficiency of an embedded system. In particular, we present a method and architecture for compressing the so-called Look-up Tables that are necessary for the de-compression process. No other work has yet focused on minimizing the Look-up Tables that, as we show, have a significant impact on the total overhead of a hardware-based decompression scheme. We introduce a novel and very efficient hardware-supported approach based on Canonical Huffman Coding. Using the Lin-Kernighan algorithm we reduce the Look-up Table size by up to 45%. As a result, we achieve all-over compression ratios as low as 45% (already including the overhead of the Look-up Tables). Thereby, our scheme is entirely orthogonal to approaches that take particularities of a certain instruction set architecture into account, meaning that compression could be further improved. Factoring in the orthogonality, our scheme is the basis for not-yet-achieved efficiency in hardware-supported compression schemes. We have conducted evaluations using a representative set (in terms of size and application domain) of applications and have applied it to three major embedded processor architectures, namely ARM, MIPS and PowerPC. The hardware evaluation shows no performance penalty.

REFERENCES

• 1: http://www.prodesigncad.com.
• 2: T. O. at el. Instruction encoding techniques for area minimization of instruction rom. ISSS, 1998.
• 3: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 4: Luca Benini , Alberto Macii , Alberto Nannarelli, Cached-code compression for energy minimization in embedded processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.322-327, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383177]
• 5: L. Benini , D. Bruni , A. Macii , E. Macii, Hardware-Assisted Data Compression for Energy Minimization in Systems with Embedded Processors, Proceedings of the conference on Design, automation and test in Europe, p.449, March 04-08, 2002
• 6: Marc L. Corliss , E. Christopher Lewis , Amir Roth, DISE: a programmable macro engine for customizing applications, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 7: D. Das, R. Kumar, and P. Chakrabarti. Code compression using unused encoding space for variable length instruction encodings. 8th VLSI Design & Test Workshop, Aug. 2004.
• 8: Dipankar Das , Rajeev Kumar , P. P. Chakrabarti, Dictionary Based Code Compression for Variable Length Instruction Encodings, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.545-550, January 03-07, 2005 [doi>10.1109/ICVD.2005.81]
• 9: M. B. Game. Codepack: Code compression for powerpc processors. PowerPC Embedded Processor Solutions, 2000.
• 10: K. Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research, 2000.
• 11: Shmuel T. Klein, Space- and Time-Efficient Decoding with Canonical Huffman Trees, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.65-75, June 30-July 02, 1997
• 12: 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
• 13: Haris Lekatsas , Jorg Henkel , Venkata Jakkula , Srimat Chakradhar, A Unified Architecture for Adaptive Compression of Data and Code on Embedded Systems, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.117-123, January 03-07, 2005 [doi>10.1109/ICVD.2005.36]
• 14: H. Lekatsas and W. Wolf. Samc: A code compression algorithm for embedded processors. IEEE Transactions on CAD, 1999.
• 15: Chang Hong Lin , Yuan Xie , Wayne Wolf, LZW-Based Code Compression for VLIW Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.30076, February 16-20, 2004
• 16: Yakov Nekritch, Decoding of Canonical Huffman Codes with Look-Up Tables, Proceedings of the Conference on Data Compression, p.566, March 28-30, 2000
• 17: M. K. Rudberg and L. Wainhamar. High speed pipeline parallel huffman decoding. IEEE International Symposium on Circuits and Systems, 1997.
• 18: 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
• 19: I. Tuduce and T. Gross. Adaptive main memory compression. Proc. USENIX Conf., Apr. 2005.
• 20: 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
• 21: X. H. Xu , C. T. Clarke , S. R. Jones, High performance code compression architecture for the embedded ARM/THUMB processor, Proceedings of the 1st conference on Computing frontiers, April 14-16, 2004, Ischia, Italy [doi>10.1145/977091.977154]
• 22: Lei Yang , Robert P. Dick , Haris Lekatsas , Srimat Chakradhar, CRAMES: compressed RAM for embedded systems, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, p.93-98, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084861]
• 23: 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]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

General Terms:
Design, Performance

Keywords:
code compression, embedded systems, huffman coding