Using Operand Factorization to Compress DSP Programs
Resumo
We propose a method for compressing programs running on embedded DSPs. Program expression trees are decomposed into opcode and operand sequences called patterns. We show that DSP program patterns have exponential frequency distribution. Based on that, we encode patterns using a mix of a variable-length and fixed-length codewords. A decompression engine is proposed, which converts patterns into uncompressed instruction sequences. The experimental results reveal an average compression ratio of 67% for typical DSP programs running on TMS320C25 processor. This ratio includes an estimate of the size of the decompression engine.
Palavras-chave:
Code Compression, DSP architecture
Referências
Guido Araujo, Paulo Centoducatte, mario Cortes and Ricardo Pannain. Code compression based on operand factorization. In Proceedings of MICRO-31: The 31th Annual International Symposium on Microarchitecture, December 1998.
Timothy C. Bell, Jhon G. Cleary and lan H. Witten. Text Compression. Advanced Reference Series. Prentice Hall, new Jersey, 1990.
C. W. Fraser, Hanson, D. R. and T. A. Proebsting. Engineering a simple, efficient code generator. Journal of the ACM, 22(12):248-262, March 1993.
Barry G. Haskell, Atul Puri and Arun N. Netravali. Digital Vídeo: an Introduction to MPEG-2. Chapman & Hall, 1991.
Charles Lefurgy, Peter Bird, I-Cheng Chen and Trevor Mudge. Improving code density using compression techniques. In Proceedings of MICRO-30: The 30th Annual International Symposium on Microarchitecture, pages 194-203, December 1997.
S. Liao, S. Devadas and K. Keutzer. A text-compression-based method for code size minimization in embedded systems. To appear in ACM Transactions on Design Automation of Electronic Systems, 4(1), 1998.
R. Leupers. Retargetable Code Generation for Digital Signal Processors. Kluwer Academic Publishers, June 1997.
D. Lanneer, J. Van Praet, A. Kifli, K. Schoofs, W. Geurts. F. Thoen and G. Goossens. CHESS: Retargetable Code Generation for Embedded DSP Processors. In P. Marwedel and G. Groossens, editors, Code Generation for Embedded Processors, chapter 5, pages 85-102. Kluwer Academic Publishers, Boston, Massachusetts, 1995.
H. Lekatsas and W. Wolf. Code compression for embedded systems. In Proc. of 35th ACM Design Automation Conference, 1998.
P. G. Paulin, C. Liem, T. C. May and S. Sutarwala. CodeSyn : A Retargetable Code Synthesis System. In Proceedings of the 7th International High-level Synthesis Workshop, Spring 1994.
Todd A. Proebsting. Optimizing an ANSI C intepreter with superoperators. In ACM Conference on Principies of Programming Languages, pages 322-332, January 1995.
A. Sudarsanam. Code Optimization Libraries for Retargetable Compilation for Embedded Digital Signal Processors. PhD thesis, Princeton University, May 1998.
Texas Instruments. TMS320C2x Use's Cuide, 1990.
Andrew Wolfe and Alex Channin. Executing compressed on an embedded RISC architecture. In Proceedings of MICRO-25: The 25th Annual International Symposium on Microarchitecture, pages 81-91. December 1992.
Timothy C. Bell, Jhon G. Cleary and lan H. Witten. Text Compression. Advanced Reference Series. Prentice Hall, new Jersey, 1990.
C. W. Fraser, Hanson, D. R. and T. A. Proebsting. Engineering a simple, efficient code generator. Journal of the ACM, 22(12):248-262, March 1993.
Barry G. Haskell, Atul Puri and Arun N. Netravali. Digital Vídeo: an Introduction to MPEG-2. Chapman & Hall, 1991.
Charles Lefurgy, Peter Bird, I-Cheng Chen and Trevor Mudge. Improving code density using compression techniques. In Proceedings of MICRO-30: The 30th Annual International Symposium on Microarchitecture, pages 194-203, December 1997.
S. Liao, S. Devadas and K. Keutzer. A text-compression-based method for code size minimization in embedded systems. To appear in ACM Transactions on Design Automation of Electronic Systems, 4(1), 1998.
R. Leupers. Retargetable Code Generation for Digital Signal Processors. Kluwer Academic Publishers, June 1997.
D. Lanneer, J. Van Praet, A. Kifli, K. Schoofs, W. Geurts. F. Thoen and G. Goossens. CHESS: Retargetable Code Generation for Embedded DSP Processors. In P. Marwedel and G. Groossens, editors, Code Generation for Embedded Processors, chapter 5, pages 85-102. Kluwer Academic Publishers, Boston, Massachusetts, 1995.
H. Lekatsas and W. Wolf. Code compression for embedded systems. In Proc. of 35th ACM Design Automation Conference, 1998.
P. G. Paulin, C. Liem, T. C. May and S. Sutarwala. CodeSyn : A Retargetable Code Synthesis System. In Proceedings of the 7th International High-level Synthesis Workshop, Spring 1994.
Todd A. Proebsting. Optimizing an ANSI C intepreter with superoperators. In ACM Conference on Principies of Programming Languages, pages 322-332, January 1995.
A. Sudarsanam. Code Optimization Libraries for Retargetable Compilation for Embedded Digital Signal Processors. PhD thesis, Princeton University, May 1998.
Texas Instruments. TMS320C2x Use's Cuide, 1990.
Andrew Wolfe and Alex Channin. Executing compressed on an embedded RISC architecture. In Proceedings of MICRO-25: The 25th Annual International Symposium on Microarchitecture, pages 81-91. December 1992.
Publicado
29/09/1999
Como Citar
PANNAIN, Ricardo; CENTODUCATTE, Paulo; ARAUJO, Guido.
Using Operand Factorization to Compress DSP Programs. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 11. , 1999, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1999
.
p. 223-229.
DOI: https://doi.org/10.5753/sbac-pad.1999.19793.
