skip to main content
10.1145/1023833.1023853acmconferencesArticle/Chapter ViewAbstractPublication PagesesweekConference Proceedingsconference-collections
Article

A hamming distance based VLIW/EPIC code compression technique

Published: 22 September 2004 Publication History

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]
P. Centoducatte, G. Araujo, and R. Pannain, "Compressed code execution on DSP architectures," in Proceedings 12th International Symposium on System Synthesis. 1999: IEEE Comput. Soc, Los Alamitos, CA, USA, 1999, pp. 56--61.
[5]
K. D. Cooper and N. McIntosh, "Enhanced code compression for embedded RISC processors," in SIGPLAN Notices. May 1999; 34(5): ACM, 1999, pp. 139--49.
[6]
J. Ernst, W. Evans, C. W. Fraser, S. Lucco, and T. A. Proebsting, "Code compression," in SIGPLAN Notices. May 1997; 32(5): ACM, 1997, pp. 358--65.
[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]
S. Y. Larin and T. M. Conte, "Compiler-driven cached code compression schemes for embedded ILP processors," in MICRO 32. Proceedings of the 32nd Annual ACM/IEEE International Symposium on Microarchitecture. 1999: IEEE Comput. Soc, Los Alamitos, CA, USA, 1999, pp. 82--92.
[12]
C. Lefurgy, P. Bird, I. C. Chen, and T. Mudge, "Improving code density using compression techniques," in Proceedings. Thirtieth Annual IEEE/ACM International Symposium on Microarchitecture Cat. No.97TB100184. 1997: IEEE Comput. Soc, Los Alamitos, CA, USA, 1997, pp. 194--203.
[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]
S. Liao, S. Devadas, and K. Keutzer, "A text-compression-based method for code size minimization in embedded systems," ACM Transactions on Design Automation of Electronic Systems, vol. 4, pp. 12--38, 1999.
[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]
M. Ros and P. Sutton, "Compiler optimization and ordering effects on VLIW code compression," in Proceedings of the international conference on Compilers, Architectures and Synthesis for embedded systems. San Jose: ACM Press, 2003, pp. 95--103.
[21]
Texas-Instruments, TMS320C6000 CPU and Instruction Set Reference Guide, 2000, accessed 2004, http://focus.ti.com/lit/ug/spru189f/spru189f.pdf
[22]
A. Wolfe and A. Chanin, "Executing compressed programs on an embedded RISC architecture," in SIGMICRO Newsletter. Dec. 1992; 23(1 2), 1992, pp. 81--91.
[23]
Y. Xie, H. Lekatsas, and W. Wolf, "Code compression for VLIW processors," in Proceedings DCC 2001. Data Compression Conference. 2001, J. A. Storer and M. Cohn, Eds.: IEEE Comput. Soc, Los Alamitos, CA, USA, 2001, pp. 525.
[24]
Y. Xie, W. Wolf, and H. Lekatsas, "Code compression for VLIW processors using variable-to-fixed coding," in 15th International Symposium on System Synthesis IEEE Cat. No.02EX631. 2002: ACM, New York, NY, USA, 2002, pp. 138--43.
[25]
Y. Xie, W. Wolf, and H. Lekatsas, "A code decompression architecture for VLIW processors," in Proceedings 34th ACM/IEEE International Symposium on Microarchitecture. 2001: IEEE Comput. Soc, Los Alamitos, CA, USA, 2001, pp. 66--75.

Cited By

View all
  • (2024)NOVLI-ISA: A Novel Optimized Variable-Length Inclusive Instruction Set Architecture for RV32I/E Architecture2024 IEEE East-West Design & Test Symposium (EWDTS)10.1109/EWDTS63723.2024.10873786(01-06)Online publication date: 13-Nov-2024
  • (2019)Code Compression for Embedded SystemsEmbedded, Cyber-Physical, and IoT Systems10.1007/978-3-030-16949-7_6(115-147)Online publication date: 29-Jun-2019
  • (2016)Code Compression for Embedded Systems Using Separated DictionariesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2015.239436424:1(266-275)Online publication date: Jan-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
CASES '04: Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems
September 2004
324 pages
ISBN:1581138903
DOI:10.1145/1023833
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 September 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. VLIW
  2. code compression
  3. hamming distance

Qualifiers

  • Article

Conference

CASES04

Acceptance Rates

Overall Acceptance Rate 52 of 230 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)NOVLI-ISA: A Novel Optimized Variable-Length Inclusive Instruction Set Architecture for RV32I/E Architecture2024 IEEE East-West Design & Test Symposium (EWDTS)10.1109/EWDTS63723.2024.10873786(01-06)Online publication date: 13-Nov-2024
  • (2019)Code Compression for Embedded SystemsEmbedded, Cyber-Physical, and IoT Systems10.1007/978-3-030-16949-7_6(115-147)Online publication date: 29-Jun-2019
  • (2016)Code Compression for Embedded Systems Using Separated DictionariesIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2015.239436424:1(266-275)Online publication date: Jan-2016
  • (2015)A novel clustered multi-dictionary code compression method2015 IEEE 5th International Conference on Electronics Information and Emergency Communication10.1109/ICEIEC.2015.7284474(1-5)Online publication date: May-2015
  • (2015)A novel classified multi-dictionary code compression for embedded systemsThe 27th Chinese Control and Decision Conference (2015 CCDC)10.1109/CCDC.2015.7162350(2546-2550)Online publication date: May-2015
  • (2014)A Low-Power Enhanced Bitmask-Dictionary Scheme for Test Data CompressionProceedings of the 2014 IEEE Computer Society Annual Symposium on VLSI10.1109/ISVLSI.2014.103(220-225)Online publication date: 9-Jul-2014
  • (2014)Studying the code compression design space - A synthesis approachJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2013.11.00160:2(179-193)Online publication date: 1-Feb-2014
  • (2013)Bitmask aware compression of NISC control wordsIntegration, the VLSI Journal10.1016/j.vlsi.2012.02.00446:2(131-141)Online publication date: 1-Mar-2013
  • (2012)Bitmask-based code compression methods for balancing power consumption and code size for hard real-time embedded systemsMicroprocessors & Microsystems10.1016/j.micpro.2011.12.00836:3(267-279)Online publication date: 1-May-2012
  • (2011)An Improved BitMask Based Code Compression Algorithm for Embedded SystemsProceedings of the 2011 International Symposium on Electronic System Design10.1109/ISED.2011.15(152-157)Online publication date: 19-Dec-2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media