Três Novos Métodos de Compressão Código usando Padrões de Blocos e Dicionário Multi-Nível
Resumo
Este trabalho propõe e implementa três novos métodos de compressão de código que são simples e eficientes. No artigo também se discute aspectos da implementação do respectivo hardware descompressor. Além disso, um novo tipo de dicionário, que é dividido em níveis, é introduzido neste artigo. O paradigma aplicado para este novo dicionário consiste em armazenar, ao mesmo tempo, instruções unitárias e padrões de blocos encontrados no código do programa, por esta razão, é chamado de Dicionário Multi-Nível. Nas simulações dos algoritmos desenvolvidos, usou-se alguns programas do benchmark MiBench, além de dois processadores embarcados de 32 bits (ARM e MIPS). A taxa média de compressão obtida em nossos métodos chegou a 34,5%. Assim, os algoritmos propostos oferecem uma melhor exploração da tríade compressão-desempenho-consumo.
Palavras-chave:
sistema embarcado, compressão de código, instrução unitária, padrão de bloco, dicionário multi-nível
Referências
Altera® Corporation. Disponível em: http://www.altera.com. Acessado em 01 de março de 2013.
A. S. Oliveira, and F. S. Andrade, "Embedded Systems - Hardware and Firmware in Practice". São Paulo: Publisher Érica, 2006, 316p.
A. Wolfe, and A. Chanin, "Executing Compressed Programs on an Embedded RISC Architecture". In Proc. of 25th Annual Intl. Symp. on Microarchitecture (MICRO 25), USA, p. 81-91, Dec. 1992.
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes". In Proceedings of the Institute of Radio Engineers (IRE), 40(9):1098-1101, September 1952.
D. Seal, "ARM Architecture Reference Manual". Addison-Wesley Professional, 2nd edition, 2001, 816p.
D. Sweetman, "See MIPS Run". – San Francisco, California, USA: Morgan Kaufmann Publishers, 2nd edition, 2006, 512p.
E. B. W. Netto, R. Azevedo, P. Centoducatte, and G. Araújo, "Multi-Profile Based Code Compression". In Proc. of the 41th Annual Design Automation Conference (DAC'04), USA, pages 244-249, June 2004.
G. de Micheli, "Computer-Aided Hardware-Software Codesign". IEEE Micro, 14(4):10-16, August 1994.
H. Lekatsas, J. Henkel, and W. Wolf, "Code Compression for Low Power Embedded System Design". In Proc. of the 37th Annual Design Automation Conference (DAC'00), USA, pages 294-299, June 2000.
M. Collin, and M. Brorsson, "Two-Level Dictionary Code Compression: a New Scheme to Improve Instruction Code Density of Embedded Applications". In Proc. of 17th Intl. Symposium on Code Generation and Optimization (CGO'09), USA, p. 231-242, March 2009.
P. Marwedel, "Embedded System Design". New York, USA: Springer-Verlag, 2nd edition, 2006, 241p.
S. I. Haider, and L. Nazhandali, "A Hybrid Code Compression Technique using Bitmask and Prefix Encoding with Enhanced Dictionary Selection". In Proc. of the Intl. Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES'07), Salzburg, Austria, pages 58-62, September 2007.
S. Klein, "Space and Time-Efficient Decoding with Canonical Huffman Trees". In Proc. of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM 1997), Aarhus, Denmark, pages 65-75, June 1997.
S. K. Menon, "An Efficient Tool-Chain for Analyzing Tradeoffs of Code Compression Schemes in Embedded Processors". In Proc. of 18th IEEE-Intl. Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2012), Korea, p. 192-201, Aug. 2012.
T. Bonny, and J. Henkel, "Instruction Splitting for Efficient Code Compression". In Proc. of the 44th Annual Design Automation Conference (DAC'07), USA, pages 646-651, June 2007.
W. R. A. Dias, and E. D. Moreno, "Code Compression in ARM Embedded Systems using Multiple Dictionaries". In Proc. of 15th IEEE Intl. Conference on Computational Science and Engineering (CSE 2012), Paphos, Cyprus, pages 209-214, December 2012.
A. S. Oliveira, and F. S. Andrade, "Embedded Systems - Hardware and Firmware in Practice". São Paulo: Publisher Érica, 2006, 316p.
A. Wolfe, and A. Chanin, "Executing Compressed Programs on an Embedded RISC Architecture". In Proc. of 25th Annual Intl. Symp. on Microarchitecture (MICRO 25), USA, p. 81-91, Dec. 1992.
D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes". In Proceedings of the Institute of Radio Engineers (IRE), 40(9):1098-1101, September 1952.
D. Seal, "ARM Architecture Reference Manual". Addison-Wesley Professional, 2nd edition, 2001, 816p.
D. Sweetman, "See MIPS Run". – San Francisco, California, USA: Morgan Kaufmann Publishers, 2nd edition, 2006, 512p.
E. B. W. Netto, R. Azevedo, P. Centoducatte, and G. Araújo, "Multi-Profile Based Code Compression". In Proc. of the 41th Annual Design Automation Conference (DAC'04), USA, pages 244-249, June 2004.
G. de Micheli, "Computer-Aided Hardware-Software Codesign". IEEE Micro, 14(4):10-16, August 1994.
H. Lekatsas, J. Henkel, and W. Wolf, "Code Compression for Low Power Embedded System Design". In Proc. of the 37th Annual Design Automation Conference (DAC'00), USA, pages 294-299, June 2000.
M. Collin, and M. Brorsson, "Two-Level Dictionary Code Compression: a New Scheme to Improve Instruction Code Density of Embedded Applications". In Proc. of 17th Intl. Symposium on Code Generation and Optimization (CGO'09), USA, p. 231-242, March 2009.
P. Marwedel, "Embedded System Design". New York, USA: Springer-Verlag, 2nd edition, 2006, 241p.
S. I. Haider, and L. Nazhandali, "A Hybrid Code Compression Technique using Bitmask and Prefix Encoding with Enhanced Dictionary Selection". In Proc. of the Intl. Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES'07), Salzburg, Austria, pages 58-62, September 2007.
S. Klein, "Space and Time-Efficient Decoding with Canonical Huffman Trees". In Proc. of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM 1997), Aarhus, Denmark, pages 65-75, June 1997.
S. K. Menon, "An Efficient Tool-Chain for Analyzing Tradeoffs of Code Compression Schemes in Embedded Processors". In Proc. of 18th IEEE-Intl. Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2012), Korea, p. 192-201, Aug. 2012.
T. Bonny, and J. Henkel, "Instruction Splitting for Efficient Code Compression". In Proc. of the 44th Annual Design Automation Conference (DAC'07), USA, pages 646-651, June 2007.
W. R. A. Dias, and E. D. Moreno, "Code Compression in ARM Embedded Systems using Multiple Dictionaries". In Proc. of 15th IEEE Intl. Conference on Computational Science and Engineering (CSE 2012), Paphos, Cyprus, pages 209-214, December 2012.
Publicado
23/10/2013
Como Citar
DIAS, Wanderson Roger Azevedo; MORENO, Edward David.
Três Novos Métodos de Compressão Código usando Padrões de Blocos e Dicionário Multi-Nível. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 14. , 2013, Porto de Galinhas.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2013
.
p. 36-43.
DOI: https://doi.org/10.5753/wscad.2013.16771.
