Code compression for VLIW processors using variable-to-fixed coding

ABSTRACT

Memory has been one of the most restricted resources in the embedded computing system domain. Code compression has been proposed as a solution to this problem. Previous work used fixed-to variable coding algorithms that translate fixed-length bit sequences into variable-length bit sequences. In this paper, we propose code compression schemes that use variable-to-fixed (V2F) length coding. We also propose an instruction bus encoding scheme, which can effectively reduce the bus power consumption. Though the code compression algorithm can be applied to any embedded processor, it favors VLIW architectures because VLIW architectures require a high-bandwidth instruction pre-fetch mechanism to supply multiple operations per cycle. Experiments show that the compression ratios using memoryless V2F coding for IA-64 and TMS320C6x are around 72.7% and 82.5% respectively. Markov V2F coding can achieve better compression ratio up to 56% and 70% for IA-64 and TMS320C6x respectively. A greedy algorithm for codeword assignment can reduce the bus power consumption and the reduction depends on the probability model used.

REFERENCES

• 1: Tony Givargis , Frank Vahid, Interface exploration for reduced power in core-based systems, Proceedings of the 11th international symposium on System synthesis, p.117-122, December 02-04, 1998, Hsinchu, Taiwan, China
• 2: N. Ishiura et al. Instruction Code Compression for Application Specific VLIW Processors Based on Automatic Field Partitioning. Proceedings of the Workshop on Synthesis and System Integration of Mixed Technologies,, pages 105--109, 1998.
• 3: 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
• 4: H. Lekatsas and W. Wolf. SAMC: A Code Compression Algorithm for Embedded Processors. IEEE Transactions on Computer Aided Design, Vol. 18:1689--1701, December 1999.
• 5: 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
• 6: S. Nam. Improving dictionary-based code compression in vliw architectures. IEICE trans. Fundamentals, November 1999.
• 7: B. Tunstall. Synthesis of Noiseless Compression Codes. PhD thesis, Georgia Institute of Technology, Atlanta, Georgia, September 1967.
• 8: 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
• 9: 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
• 10: Y.Xie, W.Wolf, and H.Lekatsas. Compression Ratio and Decompression Overhead Tradeoffs in Code Compression for VLIW Architectures. Proceedings of the 4th International Conference on ASIC,pages 337--341,2001.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

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

General Terms:
Algorithms, Design, Experimentation