Compressão de código para sistemas
embarcados
Daniel Stefani Marcon, Thiago Nunes Kehl
1 de junho de 2008
Haris Lekatsas e Wayne Wolf da Universidade de Engenharia Elétrica da
Universisdade de Princeton estão desenvolvendo 2 algoritmos para redução
de código para sistemas embarcados, um que é independente do conjunto
de instruções e outro que depende das instruções. Sistemas embarcados são
sensı́veis em questão de custo e espaço, a redução do tamanho do executável
resulta em significante ganho em termos de tamanho, custo, peso e consumo
de energia. Compressão de código ajuda a utilizarmos menos memória. Como
o código deve ser descompactado partindo de qualquer ponto, muitos dos
algoritmos já existentes não podem ser utilizados. O código é descomprimido
logo antes de ser inserido na memória cache, e é assumido que o processador
executa normalmente o código descompactado e uma descompressão só ocorre
novamente quando o processador requer uma instrução não alocada ao cache.
É necessário a utilização de um processador rápido o suficiente para não
reduzir a performance com a utilização dessas técnicas, sempre visando minimizar o tamanho do mesmo. Há vários algoritmos para compressão de dados, mas considerando os problemas citados acima, a maioria dos algoritmos
existentes não podem ser utilizados diretamente. Em termos de taxa de compressão os algoritmos que utilizam modelagem finita do contexto como PPM,
DMC e WORD parecem ter a melhor performance. Porém tais algoritmos
necessitam de muita memória para compactação e descompactação, não podendo ser utilizados para compactação de código para sistemas embarcados.
A famı́lia dos algoritmos LZ utilizam ponteiros para ocorrência anterior de
strings, fazendo com que esses algoritmos sejam inviáveis para decompressão
de um único bloco. Somente a parte executável que contém instruções é
comprimida, não qualquer dado ou tabelas, pois tal abordagem complicaria
o projeto uma vez que teriamos que prover um compressor ainda mais rápido
quando escrevendo na memória principal. O primeiro método, Semiadaptative Markov Compression (SAMC), utiliza um codificador aritmético binário
1
com um modelo de Markov.
O método de Markov é utilizado da seguinte maneira. As instruções são
divididas em k streams contendo Ki bits, com i variando de 0 até k − 1.
Para cada stream é gerada uma árvore binária de Markov com 2(ki +1) − 1
estados. O primeiro estado é o estados inicial correspondente a nenhuma
entrada. Esquerda corresponde o bit 0 e a direita o bit 1. Cada transição
tem uma probabilidade que é gerada pelo processamento de todo o programa.
É preciso armazenar as probabilidades dos ramos esquerdos uma vez que as
probabilidades do outro ramo é complementar as dos ramos esquerdos. No
final o que deve ser armazenado é a mensagem codificada e a árvore de
Markov para todas as streams.
O outro método, chamado SADC(Semiadaptative Dictionary Compression), utiliza um dicionário semiadaptativo para comprimir opcodes, combinação de registradores de opcodes e combinação opcodes imediatos. Certamente com a utilização de um dicionário semiadaptativo se adquirirá uma
melhor compressão uma vez que que o dicionário será criado especificamente
para este programa. É construı́do para cada programa em questão um dicionário semiadaptativo que mapeia os ı́ndices de opcodes ou conjuntos de
opcodes.
Encontrar o melhor dicionário para um programa é tido com um problema NP-completo, então não se tentou encontrar o melhor dicionário. Para
substituir ocorrência de combinações de opcodes por ı́ndices do dicionário
utiliza-se o greedy parsing. A aboragem utiliza geração do dicionário e parsing simultaneamente.
A geração do dicionário funciona da seguinte maneira:
• o gerador varre o programa e cria uma árvore com todos os opcodes
e suas frequências, todos os grupos de 2 códigos consecutivos e suas
frequências, e depois o mesmo com grupos de 3 consecutivos, não é
feito com grupos maiores porque isso resultaria em grande tempo de
execução e iria requerer muita memória.
• todos os opcodes são inseridos no dicionário. E uma das duas ações
é tomada, codifica-se o grupo de opcodes adjacentes que tem maior
ganho de codificação, ou codifica-se o opcode com um registrador ou
imediato especifico que irá gerar a maior redução no tamanho da stream
de registradores ou de imediatos.
• usando o dicionário criado, o gerador codifica o arquivo guardando o
indice do dicionário para cada opcode ou grupo.
• todas entradas do dicionário e a árvore são apagadas. O gerador repete
os passos até que o dicionário gerado tenha entradas igual ao máximo
2
permitido, ou o novo arquivo codificado não é menor que o gerado no
ciclo anterior. O compressor calcula os ganhos para todos os opcodes e
pega o grupo de instruções com maior ganho e inclui no dicionário. O
último passo do compressor é codificar todas as streams comprimidas
resultantes usando Huffman.
Foram feitas experiências em duas arquiteturas, MIPS e x86(Pentium
Pro). O SADC ficou aproximadamente 4-6% melhor que o SAMC em ambas
arquiteturas, pois o SAMC foi desenvolvido para conjuntos de instruções
RISC com tamanho fixo de instruções, mas pode ser usado por qualquer tipo
de arquitetura; já o SADC funciona especificamente com um programa e
conjunto de instruções, adquirindo assim melhor compressão nos testes.
Algumas pesquisas podem ser feitas em como gerar o melhor modelo
de Markov para um determinado programa a ser compactado. Finalmente,
pesquisas podem ser feitas para diferentes e mais rápidas implementações de
descompressores.
3