A hamming distance based VLIW/EPIC code compression technique

ABSTRACT

This paper presents and reports on a VLIW code compression technique based on vector Hamming distances. It investigates the appropriate selection of dictionary vectors such that all program vectors are at most a specified maximum Hamming distance from a dictionary vector. Bit toggling information is used to restore the original vector.A dictionary vector selection method which considered both vector frequency as well as maximum coverage achieved better results than just considering vector frequency or vector coverage independently. This method was found to outperform standard dictionary compression on TI TMS320C6x program code by an average of 8%, giving compression ratios of 72.1% to 80.3% when applied to the smallest compiler builds. The most favorable results were achieved with a Hamming distance upper limit of 3.An investigation into parallel compression showed that dividing the program into 32-bit parallel streams returned an average compression ratio of 79.4% for files larger than 200kb. This approach enables parallel decompression of instruction streams within a VLIW instruction word. Suggestions for further work include compiler/compression integration, more sophisticated dictionary selection methods and better codeword allocation.

REFERENCES

• 1: Mediabench Benchmarks, 1997, accessed 2003, http://cares.icsl.ucla.edu/MediaBench/
• 2: SPEC CPU2000 Benchmarks, 2000, accessed 2003, http://www.specbench.org/cpu2000/
• 3: Atmel-Corporation, AT572D740 Summary (Datasheet), 2004, accessed 2004, http://www.atmel.com/dyn/resources/prod_documents/7001s.pdf
• 4: Paulo Centoducatte , Guido Araujo , Ricardo Pannain, Compressed Code Execution on DSP Architectures, Proceedings of the 12th international symposium on System synthesis, p.56, November 01-04, 1999
• 5: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, ACM SIGPLAN Notices, v.34 n.5, p.139-149, May 1999
• 6: Jens Ernst , William Evans , Christopher W. Fraser , Todd A. Proebsting , Steven Lucco, Code compression, ACM SIGPLAN Notices, v.32 n.5, p.358-365, May 1997
• 7: M. B. Game, A, "CodePack: Code Compression for PowerPC processors (version 1.0)," PowerPC Embedded Processor Solutions, IBM, North Carolina 2000.
• 8: D. A. Huffman, "A method for the constuction of minimum redundancy codes," Proceedings of the IRE, vol. 4D, pp. 1098--1101, 1952.
• 9: Intel, Intel Itanium Architecture Software Developer's Manual, Revision 2.1, 2002, accessed 2004, http://www.intel.com/design/itanium/manuals/iiasdmanual.htm
• 10: N. Ishiura and M. Yamaguchi, "Instruction Code Compression for Application Specific VLIW Processors BAsed on utomatic Field Partitioning," 1997.
• 11: 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
• 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: C. Lefurgy and T. Mudge, "Code Compression for DSP," presented at Compiler and Architecture Support for Embedded Computing Systems, George Washington University, Washington DC, 1998.
• 14: C. Lefurgy, E. Piccininni, and T. Mudge, "Reducing code size with run-time decompression," in Proceedings Sixth International Symposium on High Performance Computer Architecture. HPCA 6 Cat. No.PR00550. 1999: IEEE Comput. Soc, Los Alamitos, CA, USA, 1999, pp. 218--28.
• 15: H. A. Lekatsas, "Code compression for embedded systems," Princeton University, 2000, pp. 171.
• 16: 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]
• 17: S. J. Nam, In Cheol Park, and Chong Min Kyung, "Improving dictionary-based code compression in VLIW architectures," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E82-A, pp. 2318--24, 1999.
• 18: P. S. Paolucci, "Apparatus and Method for Dynamic Program Decompression." United States, Filed: 2002.
• 19: J. S. Prakash, C., "A Simple and Fast Scheme for Code Compression for Embedded VLIW processors," Indian Institute of Science, 2003, pp. 43.
• 20: Montserrat Ros , Peter Sutton, Compiler optimization and ordering effects on VLIW code compression, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, October 30-November 01, 2003, San Jose, California, USA [doi>10.1145/951710.951725]
• 21: Texas-Instruments, TMS320C6000 CPU and Instruction Set Reference Guide, 2000, accessed 2004, http://focus.ti.com/lit/ug/spru189f/spru189f.pdf
• 22: Andrew Wolfe , Alex Chanin, Executing compressed programs on an embedded RISC architecture, ACM SIGMICRO Newsletter, v.23 n.1-2, p.81-91, Dec. 1992
• 23: Y. Xie , H. Lekatsas , W. Wolf, Code Compression for VLIW Processors, Proceedings of the Data Compression Conference (DCC '01), p.525, March 27-29, 2001
• 24: Yuan Xie , Wayne Wolf , Haris Lekatsas, Code compression for VLIW processors using variable-to-fixed coding, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581231]
• 25: Yuan Xie , Wayne Wolf , Haris Lekatsas, A code decompression architecture for VLIW processors, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Algorithms, Performance

Keywords:
VLIW, code compression, hamming distance