CPB-ARM -- A New Code Compression Method for Embedded Systems

2012 13th Symposium on Computing Systems

CPB-ARM - A New Code Compression Method for Embedded Systems

Wanderson Roger Azevedo Dias

Edward David Moreno

Departamento de Ciência da Computação - DCC Universidade Federal do Amazonas - UFAM Manaus, Amazonas, Brasil [email protected]

Departamento de Ciência da Computação - DComp Universidade Federal de Sergipe - UFS Aracaju, Sergipe, Brasil [email protected] gerenciamento do consumo de energia, não se mostra viável para o desenvolvimento de sistemas embarcados, devido os mesmos possuírem inúmeras limitações de recursos computacionais e físicos. As atuais estratégias concebidas para o controle e o gerenciamento no consumo de energia, foram desenvolvidas para sistemas de propósitos gerais, em que os custos adicionais de processadores ou memórias são geralmente insignificantes [5]. O tamanho de código aumenta significativamente na medida em que os sistemas tornam-se mais heterogêneos e complexos. Neste sentido, surgiu uma técnica de alto nível que procura comprimir o código em tempo de compilação e a respectiva descompressão, por sua vez, é feita em tempo de execução [4]. A técnica de compressão foi desenvolvida com o intuito de reduzir o tamanho de um código [5]. Mas no decorrer do tempo, grupos de pesquisadores verificaram que essa técnica poderia trazer grandes benefícios para o desempenho e o consumo de energia nos sistemas de propósitos gerais e nos sistemas embarcados. A partir do momento que o código em memória está comprimido é possível em cada requisição do processador buscar uma quantidade bem maior de instruções contidas na memória. Assim, haverá uma diminuição nas atividades de transição nos pinos de acesso à memória, levando a um possível aumento no desempenho do sistema e a uma possível redução no consumo de energia do circuito [7]. Este artigo propõe um novo método de compressão de código para sistemas embarcados intitulado de CPB-ARM (ComPatternBlocks-ARM). Este método aplica quatro tipos de técnicas distintas para compressão dos códigos das instruções, sendo que cada uma das técnicas aborda uma forma diferente para a formação dos Padrões de Blocos das instruções. O conjunto de instruções do processador embarcado ARM modelo StrongARM foi usado como base para o método CPB-ARM, pois a escolha deste processador se deu devido a sua grande aceitação no mercado de eletroeletrônicos; Outro ponto que também justifica a escolha deste processador é o fato do mesmo estar implementado na ferramenta de simulação arquitetural SimpleScalar [15] na qual utilizamos para validar este método usando os programas do benchmark MiBench [6]. Nossa proposta teve uma taxa de compressão satisfatória apesar de usarmos o processador ARM, uma vez que é bem conhecido que seu formato de instruções é irregular e possui muitos campos pequenos, com muitas condições. O restante do artigo está organizado da seguinte forma: a Seção 2 apresenta os trabalhos correlatos; a Seção 3 detalha a descrição do método CPB-ARM; a Seção 4 apresenta as simulações e análises, e a Seção 5 finaliza com as conclusões e ideias para trabalhos futuros.

Abstract—In the design of embedded systems, memory is one of the most restricted resources. The code compression has been proposed as a solution to reduce the code size of applications that run on embedded systems. However, one major challenge is to develop an efficient compression technique that generates a substantial reduction in code size without affecting the overall system performance. We have observed that most previous work compresses only instruction individually. Therefore, this paper proposes a new code compression method (CPB-ARM) which comprises four different types of compression techniques, and each of these techniques form different patterns of blocks taking into account the class and the format of each instruction. The simulation results showed that our method, which uses only 18 instructions, the most frequently used by the application, obtained a compression ratio of approximately 24% for twenty MiBench applications. Keywords-embedded systems; code compression; patterns blocks; embedded processor; ARM

I.

INTRODUÇÃO

Sistemas embarcados são quaisquer sistemas digitais que estejam inseridos a outros sistemas com a finalidade de acrescentar ou otimizar funcionalidades [5]. Os sistemas embarcados têm por função monitorar e/ou controlar o ambiente no qual esteja inserido. Esses ambientes podem estar presentes em dispositivos eletrônicos, eletrodomésticos, veículos, máquinas, motores e muitas outras aplicações. A crescente demanda pelo uso de sistemas embarcados tem se tornado cada vez mais comum, motivando a implementação de complexos sistemas em um único chip, os chamados SoC (System-on-Chip). Neste caso, o processador embarcado é um dos principais componentes dos sistemas computacionais embarcados [2]. Atualmente, muitos processadores embarcados encontrados no mercado são baseados em arquiteturas de alto-desempenho (por exemplo, as arquiteturas RISC de 32 bits) que garantem um melhor desempenho computacional para as tarefas a serem executadas. Consequentemente, o projeto de sistemas embarcados para processadores de alto desempenho não é uma tarefa simples. Sabe-se que muitos dos sistemas embarcados são alimentados por baterias. Por essa razão, é de suma importância que estes sistemas sejam capazes de controlar e gerenciar sua potência, possibilitando assim a redução no consumo de energia e no controle do aquecimento. Portanto, projetistas e pesquisadores concentraram-se no desenvolvimento de técnicas que diminuam o consumo de energia mantendo os requisitos de desempenho. Uma dessas técnicas é a compressão do código das instruções em memória. A grande maioria das técnicas, metodologias e padrões de desenvolvimento de software, para o controle e o 978-0-7695-4847-0/12 $26.00 © 2012 IEEE DOI

II. TRABALHOS CORRELATOS Existem muitos métodos para compressão de código, mas

25

até 32 bits. Depois disso, os novos códigos são comprimidos usando a codificação de Huffman [3, 5]. No método de compressão de Bonny & Henkel [9], as entradas da tabela de decodificação dos códigos de comprimento são variáveis e os índices (ou seja, as instruções codificadas) para essas entradas também possuem comprimento variável. Isto tornou difícil a decodificação quando foi implementado em hardware. Além disso, o tamanho necessário para armazenar a tabela de decodificação da memória é grande. Para resolver estes problemas, os autores usaram a Codificação Canônica de Huffman [10], como feito em [8]. Usando esta nova decodificação, os autores constataram que a decodificação tornou-se mais eficiente em espaço e tempo, porque requer que menos informações sejam armazenadas para a decodificação. A arquitetura do hardware descompressor proposta pelos autores [9] é composta por 2 registradores de deslocamento (Shift Register), 1 demultiplexador e 2 grupos de comparadores. O primeiro registrador recebe a palavra de instrução de 32 bits comprimida da memória. Esta palavra de instrução pode conter uma ou mais palavras de instruções comprimidas ou a instrução original completa ou partes dela. A tarefa principal deste registrador é manter o segundo registrador de deslocamento cheio e cada vez que o seu conteúdo é reduzido, desloca-se a palavra de instrução comprimida em série para ele. O segundo registrador tem um comprimento igual à maior instrução codificada (L), ou seja, o maior índice. O segundo registrador transfere o índice da tabela de L bits para o primeiro grupo dos comparadores. A tarefa dos comparadores é decodificar o comprimento das instruções codificadas a partir dos bits de entrada L. Todo o descompressor foi descrito em VHDL e sintetizado utilizando a ferramenta ISE-8.1 da Xilinx para o Virtex-II e implementado em uma plataforma de FPGA escalável Platinum da Pro-Design. O tempo médio de acesso foi de 4ns e usou por volta de 1200 CLBs (Configurable Logic Blocks). Portanto, o método desenvolvido em [9] é independente de qualquer arquitetura e de seu conjunto de instruções sendo assim, uma abordagem mais geral para o problema. As razões de compressão alcançadas para os processadores ARM [11] e MIPS [16] foram de 53% e 51% respectivamente, usando 7 programas do benchmark MiBench. Haider & Nazhandali [13] desenvolveram um novo método de codificação híbrido, combinando a tradicional codificação baseada em bitmask e a codificação baseada em prefixo de Huffman, gerando assim um novo dicionário e uma nova técnica de seleção baseada no algoritmo nongreedy. A compressão baseada em bitmask gera a compressão baseada nas freqüências e aproveita a curta distância de hamming entre algumas instruções. No método desenvolvido em [13] existem dois tipos distintos de instruções comprimidas, sendo: (i) as instruções de entrada no dicionário (DE) e (ii) as instruções de children no dicionário (DC). Em uma instrução DE o código de instrução original é armazenado no dicionário. Quando comprimidas, essas instruções só precisam de referências como índice de entrada correspondente no dicionário. Já uma instrução DC depende de uma instrução diferente, nomeadamente uma instrução DE, a ser codificada. Quando comprimida, ela contém uma referência para o índice da instrução DE, juntamente com alguns bits que especificam a máscara de bits necessários para recuperar a instrução de seus DE associados. Já a bitmask contém informações mais detalhadas sobre as máscaras incluindo a sua localização e a alternância

apesar disso, nós apresentamos apenas aqueles que se dedicam ao processador ARM e na maioria das vezes focado em estudos com programas do benchmark MiBench, que é especifico como referência para sistemas embarcados. Lefurgy et al [12], propuseram uma técnica de compressão de código baseado na codificação do programa usando um dicionário de códigos. Assim, a compressão é realizada após a compilação do código fonte, porém, o código objeto é analisado e as sequências comuns de instruções são substituídas por uma palavra codificada (codeword), como na compressão de texto. Apenas as instruções mais freqüentes são comprimidas. Um bit (escape bit) é utilizado para distinguir uma palavra comprimida (codificada) de uma instrução não comprimida. As instruções correspondentes às instruções comprimidas são armazenadas em um dicionário no hardware de descompressão. As instruções comprimidas são usadas para indexar as entradas do dicionário. O código final consiste de codewords misturadas com instruções não comprimidas. Observa-se que um dos problemas mais comuns encontrados na compressão de código se refere à determinação dos endereços alvo das instruções de salto. Normalmente este tipo de instrução (desvio direto) não é codificado para evitar a necessidade de reescrever as palavras de códigos que representam estas instruções [12]. Já os desvios indiretos podem ser codificados normalmente, pois, como seus endereços alvos estão armazenados em registradores, apenas as palavras de códigos necessitam ser rescritas. Neste caso, é necessária apenas uma tabela para mapear os endereços originais armazenados no registrador para os novos endereços comprimidos. Este método diverge dos demais métodos vistos na literatura no sentido que, os endereços alvos estejam sempre alinhados a 4 bits (tamanho de um codeword) e não ao tamanho da palavra do processador (32 bits). Como vantagem destaca-se uma melhor compressão; mas como desvantagem verifica-se a necessidade de alterações no core do processador (um hardware extra) para tratar desvios para endereços alinhados a 4 bits. Entretanto, detalhes sobre a interação do hardware descompressor com os processadores experimentados (PowerPC, ARM e i386) não são detalhados. O funcionamento do hardware descompressor é realizado basicamente da seguinte maneira: a instrução é buscada da memória, caso seja um codeword, a lógica de decodificação dos codewords obtém o deslocamento e o tamanho do codeword que servirá como índice para acessar a instrução não comprimida no dicionário e repassar ao processador. No caso de instruções não comprimidas, elas são repassadas diretamente ao processador. Com o método proposto em [12], foram obtidas taxas de compressões de 61% para o processador PowerPC, 66% para o processador ARM e 75% para o processador i386 usando 6 programas do benchmarck SPECint95. As métricas de desempenho e consumo de energia não foram ditas. Bonny & Henkel [9] desenvolveram um método de compressão de código onde as instruções originais são divididas em padrões de comprimento variável e depois é aplicada a codificação de Huffman [3] para os padrões obtidos. As novas instruções obtidas após a sua divisão podem ser classificadas em dois tipos: (i) instruções que não se repetem dentro do aplicativo (frequência = 1), chamadas de “instruções únicas”; (ii) instruções que se repetem dentro do aplicativo (frequência > 1), também chamadas de “instruções repetidas”. O algoritmo de divisão encontra a maioria dos padrões repetitivos de instruções entre todas as outras instruções. Os padrões podem ter comprimentos diferentes, sendo entre 2

26

Uma nova codificação usando codeword foi proposta para substituir as instruções que formam os padrões de blocos no código comprimido. As codewords são codificadas de forma que elas sejam escritas no código comprimido em uma única palavra de memória, e, por conseguinte elimina acessos múltiplos à cache para a descompressão de várias instruções. Usamos o conjunto de instruções do processador embarcado ARM (Advanced RISC Machine), modelo StrongARM [1, 11], versão SA-1110 como sendo o processador alvo de estudo. Portanto, nesta seção mostramos o desenvolvimento do método CPB-ARM com ênfase no algoritmo de compressão implantado na ferramenta de simulação arquitetural SimpleScalar. O método CPB-ARM é um algoritmo de compressão de código que tenta localizar padrões de blocos de instruções no código das aplicações. No entanto, quatro técnicas diferentes são aplicadas por este método com o objetivo de alcançar uma melhor razão de compressão das aplicações. São as técnicas: (i) Padrões de Instruções Repetidas; (ii) Padrões da Classe Data Processing; (iii) Padrões da Classe Single Data Transfer e (iv) Exclusão dos Sufixos Always nas quais estão descritas a seguir.

necessária entre os bits reais, conforme se explica em [13]. Os experimentos realizados em [13], obtiveram uma razão de compressão de 91% para os dicionários com 4096 e 8092 entradas (instruções) e 80% para os dicionários com 512 e 1024 entradas (instruções) aplicando o novo método de compressão de código híbrido. A plataforma de teste foi um ARM usando 9 programas do benchmark MiBench. Xu et al [14] definiram uma nova arquitetura que é independente do algoritmo de compressão e descompressão de código. Os autores não tiveram a intenção de se aprofundar em desenvolvimento ou melhoria de um novo algoritmo de compressão de código, mais sim de analisar os algoritmos já conceituados na área da pesquisa e usá-los na nova arquitetura, chamada de Code Compressed THUMB Processor (CCTP). Os componentes da arquitetura CCTP são: caches de dados e instruções, CPU, memória RAM, barramento, buffer de bloco descomprimido (DBB) que armazena temporariamente os blocos das instruções descomprimidas, memória de instruções comprimidas, tabela de endereço dos blocos comprimidos (CBAT) que é usada para converter o espaço de endereço comprimido a uma tabela de descompressão e uma máquina de descompressão (DE) que realiza todo o processo de descompressão, e gerencia os hits na DBB. Os algoritmos de compressão de código podem aparecer na forma de software ou hardware. Porém, os autores preferiram usar um descompressor em hardware por ser mais rápido do que o correspondente descompressor em software. Os autores [14] escolheram o ISA (Instruction Set Architecture) do processador ARM como base, porque desenvolveram uma arquitetura que comprimiu com eficiência o código ARM/THUMB. No entanto, a arquitetura CCTP também é capaz de trabalhar com outros ISAs. Para os experimentos usaram a SimpleScalar definida como plataforma de simulação para a arquitetura CCTP em software. A compressão de código trabalhou com o núcleo do microprocessador ARM9. Como pacote de entrada para os experimentos, usaram-se 8 programas do MiBench. Segundo XU et al [14] na arquitetura CCTP a memória de compressão proposta mostrou uma redução de 15 a 20% no tamanho do código das instruções do processador ARM/THUMB e um aumento de 5% no desempenho final do sistema. A Tabela I mostra uma sumarização dos resultados obtidos pelos autores dos trabalhos correlatos através das simulações e análises realizadas. Nesta tabela aparece também a razão de compressão média obtida com o método proposto neste artigo, que será mais bem detalhado nas próximas seções. TABELA I.

Cond 31

benchmark

Nº de Programas

SPECint95

6

MiBench

7

ARM

MiBench

9

ARM9 ARM

MiBench MiBench

8 20

Plataforma PowerPC ARM i386 ARM MIPS

Lefurgy et al [12] Bonny & Henkel [9] Haider & Nazhandali [13] Xu et al [14] CPB-ARM

IdT 28

27

26

Size 25

Index 18

17

0

Figura 1. Codeword#1 – Técnica PIR.

onde, x x x

RESUMO DOS TRABALHOS CORRELATOS E CPB-ARM

Autor

III.

A. Padrões de Instruções Repetidas (PIR) Está técnica faz uma análise no código da aplicação em busca de blocos de instruções idênticas e que tenha uma frequência de repetição consecutiva superior a duas instruções. Quando o padrão é encontrado no código que está sendo submetido à compressão o mesmo é substituído por uma codeword e uma representação desta instrução é inserida no dicionário. Ainda, ressaltamos que esta técnica não apresenta nenhuma outra restrição quanto: às classes do ISA do processador, os sufixos das instruções ou ainda a quantidade de bits dos operandos da instrução. 1) Codeword – Técnica PIR: No código comprimido por está técnica é usada uma codeword no lugar das instruções que compõem os blocos de instruções. A Figura 1 mostra a codeword#1 usada nesta técnica. Com o uso desta codeword é possível identificarmos a técnica de compressão aplicada, o tamanho do bloco e a sua localização dentro do dicionário.

Razão de Compressão 61% 66% 75% 53% 51% 80% DicSmall 91% DicLarge 80% a 85% 76,8%

x

Cond: é o sufixo da instrução, sendo que Cond= 1111b identifica uma instrução comprimida; IdT: é o identificador da técnica de compressão, sendo que para PIR IdT= 00b; Size: é o tamanho do bloco de instruções, podendo conter PIR com até 256 instruções idênticas; Index: é o índice da posição do bloco das instruções comprimidas no dicionário.

Sendo o campo Index da codeword#1 composto por 18 bits, é possível indexar um dicionário com até 262.143 posições; No entanto, dicionários deste tamanho não são usados em projetos de compressão de código para sistemas embarcados. Então, usamos apenas alguns bits do campo Index sendo o restante preenchido com zeros. A Figura 2 mostra um exemplo de trecho de código do SHA-1 (usado no MiBench). É possível verificar que as linhas 46744 até 46750 (instrução andeq r13,r2,#200704 (196 >>> 11)) apresentam um bloco de instruções idênticas. Então, no código original podemos substituir essas linhas pela codeword#1, e uma dessas linhas é inserida no dicionário.

DESCRIÇÃO DO MÉTODO CPB-ARM

Nesta seção apresentamos a contribuição deste artigo, ou seja, o método ComPatternBlocks-ARM (CPB-ARM) que foi desenvolvido com o objetivo principal de reduzir a quantidade de acessos à cache de instrução e por conseguinte a memória principal.

27

x x

Neste pequeno exemplo já eliminaríamos cinco instruções repetitivas no código comprimido, ou seja, uma compressão de ≈38,5% para este exemplo.

00: são bits defaults da classe Data Processing; I: é o bit que identifica se na instrução o Operand2 possui ou não um valor de imediato; Opcode: é o opcode da instrução; S: é um bit de controle; Rn: é o registrador do operando da instrução; Rd: é o registrador de destino da instrução; Operand2: é um registrador da instrução.

x x x x x

46741 @ 0x0202daec: [e5963000] ldr r3,[r6,#0] 46742 @ 0x0202daf0: [e50b301c] str r3,[r11,-#28] 46743 @ 0x0202daf4: [e4d32001] ldrb r2,[r3],#1 46744 @ 0x0202db40: [0202dbc4] andeq r13,r2,#200704 (196 >>> 11) 46745 @ 0x0202db44: [0202dbc4] andeq r13,r2,#200704 (196 >>> 11) 46746 @ 0x0202db48: [0202dbc4] andeq r13,r2,#200704 (196 >>> 11) 46747 @ 0x0202db4c: [0202dbc4] andeq r13,r2,#200704 (196 >>> 11) 46748 @ 0x0202db50: [0202dbc4] andeq r13,r2,#200704 (196 >>> 11) 46749 @ 0x0202db54: [0202dbc4] andeq r13,r2,#200704 (196 >>> 11) 46750 @ 0x0202db58: [0202dbc4] andeq r13,r2,#200704 (196 >>> 11) 46751 @ 0x0202db88: [e24b001c] sub r0,r11,#28 (28 >>> 0) 46752 @ 0x0202db8c: [e1a02005] mov r2,r5 46753 @ 0x0202db90: [ebffff49] bl 0x202d8bc

1) Formato das Instruções: Para comprimir as instruções da classe Data Processing com o sufixo always usando o método CPB-ARM, primeiramente foi necessário identificarmos os formatos das instruções, conforme mostrado na Tabela III.

Figura 2. Exemplo de trecho do código do sha-1 obtido pela ferramenta SimpleScalar.

TABELA III.

B. Padrões da Classe Data Processing (PCDP) Está técnica localiza padrões analisando os opcodes de cada instrução que pertence a esta classe. Esses opcodes podem ser iguais (divergindo apenas o formato das instruções ou os seus registradores) ou ainda diferentes (no formato das instruções e seus registradores). Na técnica PCDP o método CPB-ARM foi otimizado para a classe das instruções Data Processing com o sufixo always1. Importante lembrar que esta classe realiza operações de processamento dos dados, tais como: operações lógicas, adições, subtrações, movimentações de dados, comparações dos registradores (Rn, Rd e Operand2) entre outras. Em medições realizadas com a ferramenta de simulação arquitetural SimpleScalar usando aplicações do benchmark MiBench, a classe Data Processing apresentou o maior números de instruções presentes nas aplicações, entre 45% a 55% no total geral das instruções, obtidas de forma Estática e Dinâmica. Portanto, assim justificamos o uso desta classe no desenvolvimento de uma técnica específica para o método CPB-ARM. A Tabela II mostra as instruções pertencentes à classe Data Processing do processador StrongARM, bem como suas operações e na Figura 3 o formato básico destas instruções. TABELA II.

Cond 31

28

Binário dos Formatos 000 001 010 011 100 101 110 111

Opcode 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

0

0

I

27

26

25

TABELA IV. Binário dos Formatos

Operação Rd := Rn and Op2 Rd := (Rn and not Op2) or (Op2 and not Rn) Rd := Rn - Op2 Rd := Op2 - Rn Rd := Rn + Op2 Rd := Rn + Op2 + Carry Rd := Rn - Op2 - 1 + Carry Rd := Op2 - Rn - 1 + Carry CPSR flags := Rn and Op2 CPSR flags := Rn eor Op2 CPSR flags := Rn - Op2 CPSR flags := Rn + Op2 Rd := Rn or Op2 Rd : = Op2 Rd := Rn and not Op2 Rd := 0xFFFFFFFF eor Op2

Opcode 24

21

S 20

Rn 19

Rd 16

15

11

Formato das Instruções

000

opcode reg1, reg2

010

opcode reg1, #v1 (v2 >>> v3)

100

opcode reg1, reg2, ShiftType reg3

110

opcode reg1, reg2, ShiftType #v1

TABELA V. Binário dos Formatos 001 0

Figura 3. Formato básico das instruções da classe Data Processing [1].

onde, x

FORMATO DAS INSTRUÇÕES COM OPCODE: MOV, MVN, CMP, CMN, TEQ E TST Sintaxe cond opcode , Operand2 cond opcode , #Operand2 (Operand2 [7:0] >>> Operand2 [11:8]) cond opcode , Operand2 [3:0], Operand2 [6:5] Operand2 [11:8] cond opcode , Operand2 [3:0], Operand2 [6:5] #Operand2 [11:7]

Tamanho dos Registradores 8 bits 16 bits

16 bits

16 bits

Já na Tabela V, mostramos os demais formatos das instruções da classe Data Processing, ou seja, as instruções com opcodes and, eor, sub, rsb, add, adc, sbc, rsc, orr e bic.

Operand2 12

Formatos das Instruções opcode reg1, reg2 opcode reg1, reg2, reg3 opcode reg1, #v1 (v2 >>> v3) opcode reg1, reg2, #v1 (v2 >>> v3) opcode reg1, reg2, ShiftType reg3 opcode reg1, reg2, reg3, ShiftType reg4 opcode reg1, reg2, ShiftType #v1 opcode reg1, reg2, reg3, ShiftType #v1

Na Tabela IV apresentamos os formatos das instruções que possuem opcodes mov, mvn, cmp, cmn, teq e tst, sendo que o valor de reg1 é diferente para instruções que fazem a movimentação de dados (mov e mvn - instruções de operando único) em relação as instruções que fazem apenas comparações e testes nos valores dos registradores (cmp, cmn, teq e tst - instruções que não produzem um resultado). Se o opcode da instrução for mov ou mvn, então, o valor de reg1 será o valor do registrador Rd, senão, Rn.

INSTRUÇÕES DA CLASSE DATA PROCESSING [1]

Mnemônico and eor sub rsb add adc sbc rsc tst teq cmp cmn orr mov bic mvn

FORMATOS DAS INSTRUÇÕES DA CLASSE DP

Cond: são os bits de verificação condicionais, se a condição for verdadeira a instrução é executada;

1 As instruções que possuem o sufixo always significam que a instrução sempre será executada independentemente dos valores de codificação do registrador CPSR do processador StrongARM.

FORMATO DAS INSTRUÇÕES COM OPCODE: AND, EOR, SUB, RSB, ADD, ADC, SBC, RSC, ORR E BIC

Formato das Instruções opcode reg1, reg2, reg3

011

opcode reg1, reg2, #v1 (v2 >>> v3)

101

opcode reg1, reg2, reg3 ShiftType reg4

111

opcode reg1, reg2, reg3 ShiftType #v1

Sintaxe

Tamanho dos Registradores

cond opcode Rd, Rn, Operand2

12 bits

cond opcode Rd, Rn, #Operand2 (Operand2 [7:0] >>> Operand2 [11:8]) cond opcode Rd, Rn, Operand2 [3:0], Operand2 [6:5] Operand2 [11:8] cond opcode Rd, Rn, Operand2 [3:0], Operand2 [6:5] #Operand2 [11:7]

20 bits

20 bits

20 bits

Devido ao processador embarcado StrongARM ser uma arquitetura RISC de 32 bits, onde as instruções são compostas

28

por bits de: verificação condicionais, opcode, registradores e flags de informações conforme mostrado na Figura 3, não há nenhuma maneira de carregar os valores grandes (em quantidade de bits) de imediatos no registrador em uma instrução. Este problema pode ser resolvido com o uso do ShiftType. Então, quando o registrador Operand2 da instrução é especificado para ser deslocado de um determinado registrador a outro, a operação de deslocamento é controlada pelo ShiftType (para os Formatos das Instruções da Tabela III que possuem os valores binários iguais a 100, 101, 110 e 111), ou seja, este campo da instrução indica o tipo de deslocamento ou rotacionamento a ser realizado, conforme mostrado na Tabela VI. TABELA VI. Binário 00 01 10 11

32 bits causando o desalinhamento das instruções no código da aplicação. A Tabela VII mostra as possíveis combinações nos tamanhos (em bits) dos Formatos das Instruções para a formação dos Padrões de Blocos da técnica PCDP. TABELA VII. PADRÕES DE BLOCOS DA TÉCNICA PCDP Binário do IdPB 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

TIPO DE DESLOCAMENTO OU ROTACIONAMENTO [1]

Tipos de ShiftType lsl (logical shift left) deslocamento lógico para à esquerda lsr (logical shift right) deslocamento lógico para à direita asr (arithmetic shift right) deslocamento aritmético para à direita ror (rotate right) rotacionamento para à direita

2) Blocos Misto ou Igual: No método CPB-ARM a técnica PCDP pode formar blocos contendo instruções mistas ou iguais, no qual será usado para a criação dos Padrões de Blocos utilizados na compressão do código, sendo: x Bloco Misto (valor binário da flag mi das codewords igual a 0): os blocos mistos podem conter instruções com opcodes e/ou Formatos das Instruções diferentes; x Bloco Igual (valor binário da flag mi das codewords igual a 1): esses blocos possuem apenas instruções com o mesmo opcode, sendo que os Formatos das Instruções podem ser diferentes.

Binário dos Formatos das Instruções 000 + 000 + 000 000 + 000 + 001 000 + 001 + 000 001 + 000 + 000 000 + 000 + 010 000 + 000 + 100 000 + 000 + 110 000 + 010 + 000 000 + 100 + 000 000 + 110 + 000 010 + 000 + 000 100 + 000 + 000 110 + 000 + 000 000 + 001 + 001 001 + 000 + 001 001 + 001 + 000

Tamanho dos Padrões de Blocos 8 + 8 + 8 = 24 bits 8 + 8 + 12 = 28 bits 8 + 12 + 8 = 28 bits 12 + 8 + 8 = 28 bits 8 + 8 + 16 = 32 bits 8 + 8 + 16 = 32 bits 8 + 8 + 16 = 32 bits 8 + 16 + 8 = 32 bits 8 + 16 + 8 = 32 bits 8 + 16 + 8 = 32 bits 16 + 8 + 8 = 32 bits 16 + 8 + 8 = 32 bits 16 + 8 + 8 = 32 bits 8 + 12 + 12 = 32 bits 12 + 8 + 12 = 32 bits 12 + 12 + 8 = 32 bits

Podemos observar na Tabela VII que não foram usados os Formatos das Instruções que possuem o tamanho de 20 bits, conforme apresentado na Tabela V. Está é uma restrição desta técnica (PCDP), devido às permutações dos formatos com esse tamanho juntamente com os demais formatos de tamanhos diferentes nunca obter um Padrão de Bloco que seja formado com pelo menos três instruções e que a soma de seu tamanho seja de no máximo 32 bits. Assim, desconsideramos o uso dos Formatos das Instruções que possuem o valor binário igual a 011, 101 e 111 da Tabela V na formação dos Padrões de Blocos nesta técnica. 4) Codeword – Técnica PCDP: No código comprimido é usada uma codeword no lugar das instruções que compõem os Padrões de Blocos, no qual é possível identificar a técnica de compressão aplicada, o tamanho do bloco, os formatos das instruções, os opcodes e a localização dos padrões de blocos das instruções no dicionário. Portanto, desenvolvemos nesta técnica os seguintes formatos de codewords: x Codeword#2: se o valor da flag S (bit 25 da codeword) for igual a 0, então a codeword representa um Padrão de Bloco formado por três instruções. Não entanto, faz-se necessário o uso da flag IdPB (bits 8 a 11 da codeword) para identificar os possíveis Padrões de Blocos (ver Tabela VII) os quais serão usados pelo processo de descompressão. A Figura 4 mostra a codeword#2.

3) Padrões de Blocos: Os Padrões de Blocos de instruções da técnica PCDP são as possíveis combinações dos Formatos das Instruções, que somando os tamanhos dos registradores não ultrapasse a 32 bits. Portanto, os Padrões de Blocos formados para a compressão sempre terão tamanhos de 24, 28 ou 32 bits. No entanto, os Padrões de Blocos de instruções formados sempre serão inseridos no dicionário, porém estes padrões conterão os valores dos registradores (Rn, Rd e Operand2) das instruções comprimidas. Já no código comprimido será usada uma codeword no lugar das instruções do bloco, onde será possível identificarmos o tamanho do bloco, os formatos das instruções, os opcodes, a técnica de compressão aplicada e a localização do Padrão de Bloco das instruções no dicionário. Para que a compressão das instruções usando a técnica PCDP apresente ganhos na métrica de espaço, é necessário que os Padrões de Blocos formados sempre sejam compostos por três ou quatro instruções. Sendo que para os padrões formados por três instruções o ganho é de ≈33%, já para os padrões com quatro instruções este valor aumente para 50%. Estes ganhos justificam-se pelas trocas de três ou quatro instruções de 32 bits cada por duas novas instruções de 32 bits, sendo que uma delas é inserida no código comprimido (como uma codeword) e a outra no dicionário (Padrão de Bloco). Portanto, assim concluímos que para a formação de Padrões de Blocos eficientes, não é vantajoso o uso de apenas duas instruções, pois a métrica de espaço não apresentará nenhum ganho usando esta técnica e sim uma redução de desempenho do sistema devido às operações de descompressão dos blocos. E para os Padrões de Blocos formados com cinco ou mais instruções será necessário mais de uma linha de posicionamento no dicionário (mais de uma busca no dicionário), e ainda assim a codeword terá mais de

Cond 31

28

IdT 27

26

S

Mi

25

24

Opc1 23

20

Opc2 19

16

Opc3 15

12

IdPB 11

Index 8

7

0

Figura 4. Codeword#2 – Técnica PCDP.

x

Codeword#3: se o valor da flag S (bit 25 da codeword) for igual a 1, então a codeword representa um Padrão de Bloco formado por quatro instruções. Para esse tipo de Padrão não é necessário o uso da flag IdPB, pois todos os Formatos das Instruções são compostos por 8 bits. A Figura 5 mostra a codeword#3.

Cond 31

28

IdT 27

26

S

Mi

25

24

Opc1 23

20

Opc2 19

16

Opc3 15

12

Opc4 11

Figura 5. Codeword#3 – Técnica PCDP.

onde,

29

Index 8

7

0

x

Cond: é o sufixo da instrução, sendo que Cond= 1111b identifica uma instrução comprimida; IdT: é o identificador da técnica de compressão, sendo que para PCDP IdT= 01b; S: é o tamanho do bloco de instruções, pode conter grupos formados com três instruções (S igual a 0); e quatro instruções (S igual a 1); Mi: é o identificador de bloco misto (Mi igual a 0) ou bloco igual (Mi igual a 1); Opc1, Opc2, Opc3 e Opc4: são os opcodes das instruções do bloco; IdPB (Index Block Pattern): é o identificador do Padrão de Bloco, usado apenas na codeword#2; Index: é o índice da posição do padrão de bloco das instruções comprimidas no dicionário. Podendo indexar um dicionário com até 256 posições.

x x x x x x

campo da instrução indica o tipo de deslocamento ou rotacionamento a ser realizado, conforme visto na Tabela VI. Nas simulações realizadas com a ferramenta SimpleScalar usando os MiBench, o primeiro tipo de formato da instrução mostrado na Tabela VIII é o que mais aparece entre as instruções desta classe, cerca de 95%. Portanto, restringimos esta técnica para realizar a compressão nas instruções da classe Single Data Transfer que possuem apenas este formato.

2) Codeword – Técnica PCSDT: A codeword desenvolvida para esta técnica possui as mesmas características das demais codewords apresentadas anteriormente neste artigo. Se o valor da flag S (bit 25 da codeword) for igual a 0, então a codeword representa um Padrão de Bloco formado por três instruções, sendo assim, é atribuída o valor 0 para a flag Opc4 (bit 21) e 000 para os bits 9 até 11 da flag IdP e os mesmos não serão levados em consideração no momento do processo de descompressão. A Figura 7 mostra a codeword#4.

C. Padrões da Classe Single Data Transfer (PCSDT) Assim como as outras duas técnicas (PIR e PCDP) do método CPB-ARM apresentadas anteriormente, esta técnica também tenta localizar padrões de instruções para realizar a compressão. No entanto, esta técnica foi otimizada para a classe Single Data Transfer (SDT) do ISA do processador StrongARM (com o sufixo always). Fizemos simulações (utilizando SimpleScalar) e medimos a quantidade de instruções que pertencem a esta classe. Para os programas do MiBench, esta classe representa entre 30 a 35% de todas as instruções. Esses dados foram obtidos de forma estática e dinâmica. A classe SDT é composta por apenas dois tipos de instruções, sendo elas: LDR e STR. A instrução LDR realiza operações de carregar bytes ou palavras de dados da memória para os registradores; Já a instrução STR realiza operações inversas, ou seja, armazena bytes ou palavras de dados na memória. A Figura 6 o formato básico destas instruções. Cond 31

28

0

1

27

26

info 25

L 21

20

Rn 19

Rd 16

15

Cond 31

11

onde, x x x x x x

0

Figura 6. Formato básico das instruções da classe SDT [1].

onde, x x x x x x x

1) Formato das Instruções: Para a técnica PCSDT comprimir as instruções da classe Single Data Transfer também foi necessário identificarmos os formatos das instruções desta classe, conforme é mostrado na Tabela VIII. TABELA VIII. FORMATO DAS INSTRUÇÕES DA CLASSE SDT Formatos das Instruções opcode reg1, [reg2, #v1] opcode reg1, [reg2, #v1]! opcode reg1, [reg2, reg3] opcode reg1, [reg2, reg3, ShiftType #v1] opcode reg1, [reg2], #v1

26

S

Opc1

Opc2

Opc3

Opc4

25

24

23

22

21

IdP 20

Index 9

8

0

Cond: é o sufixo da instrução, sendo que Cond= 1111b identifica uma instrução comprimida; IdT: é o identificador da técnica de compressão, sendo que para PCSDT IdT= 10b; S: é o tamanho do bloco de instruções, pode conter grupos formados com três instruções (S igual a 0); e quatro instruções (S igual a 1); Opc1, Opc2, Opc3 e Opc4: são os opcodes das instruções do bloco; IdP (IdPattern): é o identificador do Padrão de Bloco, usado pela codeword#4; Index: é o índice da posição do padrão de bloco das instruções comprimidas no dicionário. Podendo indexar um dicionário com até 512 posições.

D. Exclusão dos Sufixos Always Conforme as simulações realizadas nos programas do MiBench usando a ferramenta arquitetural SimpleScalar, podemos constatar que cerca de 85 a 90% de todas as instruções das aplicações possuem o sufixo de condição always. Assim, o método CPB-ARM possui uma técnica específica que faz a exclusão (no processo de compressão) destes bits nas instruções que possuem este tipo de sufixo e assim é possível atingirmos uma taxa de compressão mais expressiva. Uma tabela com um bit flag (para cada instrução da aplicação) de sinalização é criada no instante que esta técnica de compressão está sendo executada, porém, esta tabela é inserida em um buffer no módulo do descompressor. Sendo assim, no instante que o processo de descompressão é solicitado, esta tabela é consultada para verificar se é preciso ou não acrescentar os bits de condição always à instrução. Caso o bit flag da instrução consultado seja igual a 1, então é necessário acrescentar na instrução o sufixo always e logo em seguida realizar todo o processo de descompressão. Já se o bit flag for igual a 0 então a instrução apenas será descomprimida de acordo com a técnica do método CPBARM utilizada. Para finalizar a seção, a Figura 8 mostra um pseudocódigo do algoritmo de compressão do método CPB-ARM.

Cond: são os bits de verificação condicionais, se a condição for verdadeira a instrução é executada; 01: são bits defaults da classe Single Data Transfer; Info: são bits de informações da instrução; L: é o opcode da instrução (L=0 a instrução é STR e L=1 a instrução é LDR); Rn: é o registrador do operando da instrução; Rd: é o registrador de destino da instrução; Offset: é o índice de deslocamento da instrução.

Binário 000 001 010 011 100

IdT 27

Figura 7. Codeword#4 – Técnica PCSDT.

Offset 12

28

Tamanho 12 bits 13 bits 12 bits 18 bits 12 bits

Assim como mostrado na técnica PCDP o campo ShiftType no formato das instruções (com valor binário igual a 011) apresenta a mesma funcionalidade, ou seja, este

30

compressão, em média 23,2%. Comprovando esta afirmação observamos na Figura 10 que a aplicação gsm (toast, untoast) apresentou a melhor taxa de compressão, ou seja, 23,8% quando comparado com o seu tamanho original. Este fato é explicado em virtude desta aplicação fazer muitas operações lógicas que usam instruções que manipulam dados inteiros na ULA para codificar e decodificar streams de dados. Já a aplicação sphinx mostrou-se não tão eficaz na compressão de suas instruções, ou seja, uma compressão de apenas 22,5% em relação ao seu tamanho original, ficando abaixo da taxa média das demais aplicações.

CódigoComprimido COMPRESS (CódigoOriginal) { 1 Dicionário ← {Conjunto Vázio} 2 Enquanto não for o fim do CódigoOriginal ou Dicionário não estiver completo 3 Lê uma instrução do CódigoOriginal - Insere a instrução no buffer 3.1 Se a instrução lida for da classe Data Processing com sufixo always - Tenta aplicar a codeword#3 - Tenta aplicar a codeword#2 3.2 Senão, se a instrução lida for da classe Single Data Transfer - Tenta aplicar a codeword#4 3.3 Senão, se a instrução lida for igual à 1ª instrução do buffer - Incrementa o contador do buffer 4 Se uma das codewords for aplicada, então - Insere a codeword no CódigoComprimido - Insere o Padrão de Bloco no Dicionário - Salta a leitura no CódigoOriginal o tamanho da quantidade de bits do Padrão de Bloco formado e aplicado - Volta ao passo 2 5 Senão, se o contador do buffer for > 2, e a instrução lida for diferente da 1ª instrução do buffer, então - Insere a codeword#1 no CódigoComprimido - Insere a 1ª instrução do buffer no dicionário - Salta a leitura no CódigoOriginal o tamanho do contador do buffer - Zera o contador do buffer - Limpa o buffer - Volta ao passo 2 6 Se a instrução não foi comprimida e o sufixo é always, então - Insere o bit flag da instrução na Tabela de Bit Flag - Exclui o sufixo da instrução 7 Fim do Enquanto 8 Retorna o CódigoComprimido }

24

% da Taxa de Compressão

23,5

23

22,5

22

21,5

Figura 8. Pseudo-Algoritmo do método CPB-ARM.

IV.

benchmark MiBench

SIMULAÇÕES E ANÁLISES

Figura 10. Taxa de compressão dos MiBench.

Para análise e validação do método CPB-ARM realizamos simulações com vinte programas do benchmark MiBench, sendo eles: basicmath, quicksort (small, large), rijndael (encriptar, decriptar), sha-1, dijkstra (small, large), patrícia, jpeg (comprime, descomprime), mad, crc32 (small, large), fft, gsm (toast, untoast), stringsearch (small, large) e sphinx. Escolhemos estas aplicações de forma que cobríssemos todas as categorias de programas do MiBench. Primeiramente, observamos na Figura 9, o tamanho das aplicações (em bytes) antes e depois da compressão, detalhando mais a análise observamos na Figura 10 a taxa de compressão de cada aplicação simulada e por fim, na Figura 11 a representatividade (em %) na compressão das aplicações para cada uma das quatro técnicas do método CPB-ARM. Instrução Original

Assim como já esperado, podemos constatar na Figura 11 que a técnica Exclusão dos Sufixos Always apresentou uma média de 39% na representatividade das instruções comprimidas, vale lembrar que cerca 85 a 90% de todas as instruções das aplicações do MiBench possuem este tipo de sufixo. Já a técnica Padrões da Classe Data Processing (PCDP) apresentou em média 29,2% na representatividade da compressão das aplicações quando aplicado às técnicas do método CPB-ARM. Isto ocorre devido ao fato de que aproximadamente 55% de todas as instruções das aplicações pertencerem a esta classe. Em seguida destacamos que a técnica Padrões da Classe Single Data Transfer (PCSDT) representou 23,3% na taxa de compressão, chegando esta classe a possuir cerca de 35% de todas as instruções das aplicações. E por fim, a técnica Padrões de Instruções Repetidas (PIR) representou 8,5% na taxa de compressão das aplicações.

Instrução Comprimida

500.000 450.000 400.000

PIR

300.000

Representatividade (%) na taxa de compressão de cada técnica do método CPB-ARM

Tamanho em Bytes

350.000 250.000 200.000 150.000 100.000 50.000 0

benchmark MiBench

Figura 9. Tamanho das aplicações dos MiBench em bytes.

Como podemos observar na Figura 9, constatamos que em todas as aplicações simuladas houve uma redução (em bytes) significativa em seu tamanho quando aplicada a

PCDP

PCSDT

Exclusão de Sufixo

100 90 80 70 60 50 40 30 20 10 0

benchmark MiBench

Figura 11. Representatividade de cada técnica do método CPB-ARM na taxa de compressão.

31

V. CONCLUSÕES E TRABALHOS FUTUROS Neste artigo descremos um novo método de compressão de código (CPB-ARM – CPB = ComPatternBlocks), o qual foi implementado em linguagem C e validado pelo simulador arquitetural SimpleScalar. Usamos como base o ISA do processador embarcado ARM modelo StrongARM. A utilização do método CPB-ARM mostrou-se viável para as aplicações do MiBench, pois o uso de técnicas de compressão de código - com intuito de melhorar as métricas de espaço, desempenho e consumo de energia - vem se tornando cada vez mais necessário em projetos de sistemas embarcados. Mediante as simulações realizadas podemos constatar que o método CPB-ARM apresentou uma taxa de compressão de aproximadamente 24%. Desta forma, quando armazenamos mais instruções comprimidas na memória, aumentamos o número de instruções armazenadas na cache e assim aumentamos a taxa de acertos (hit rate) e diminuímos as buscas na memória principal, aumentando o desempenho do sistema e, por seguinte, diminuindo o consumo de energia. No entanto, levando-se em consideração que o método CPB-ARM aplica a compressão de blocos em apenas 18 tipos de instruções e ainda condicionadas ao sufixo always, destacamos que o mesmo apresentou uma taxa de compressão compatível com as taxas dos métodos encontrados na literatura e apresentados na Seção 2 deste artigo. Assim, concluímos que o método apresentado neste artigo mostrou-se eficiente para o uso em sistemas embarcados. Como trabalhos futuros sugere-se realizar medições do consumo de energia das aplicações no método CPB-ARM; prototipar o módulo descompressor do método CPB-ARM em uma FPGA; analisar o comportamento da compressão do código de outros benchmarks; projetar novas técnicas de compressão para as outras classes de processador embarcado.

[5]

[6]

[7]

[8]

[9]

[10]

[11] [12]

[13]

REFERÊNCIAS [1] [2]

[3]

[4]

ARM. ARM-7TDMI Data Sheet. Advanced RISC Machines Ltd., August 1995. A. S. de Oliveira, and F. S. de Andrade, "Embedded Systems Hardware and Firmware in Practice". São Paulo: Publisher Érica, 2006, 316p. D. A. Huffman, "A Method for the Construction of MinimumRedundancy Codes". In Proceedings of the Institute of Radio Engineers (IRE), 40(9):1098-1101, September 1952. E. B. W. Netto, R. Azevedo, P. Centoducatte, and G. Araújo, "Multi-Profile Based Code Compression". In Proceedings of the

[14]

[15]

[16]

32

41th Annual Design Automation Conference (DAC'04), San Diego, California, USA, pages 244-249, June 2004. L. Benini, A. Macii, and A. Nannarelli, "Cached-Code Compression for Energy Minimization in Embedded Processor". In Proceedings of the International Symposium on Low-Power, Electronics and Design (ISPLED '01), Huntington Beach, California, USA, pages 322-327, August 2001. M. Guthaus, J. Ringenberg, D. Ernst, T. Austin, T. Mudge, and R. Brown, "MiBench: A Free, Commercially Representative Embedded Benchmark Suite". In Proceedings of the IEEE 4th Annual Workshop on Workload Characterization (WWC-4), Austin, Texas, USA, pages 3-14, December 2001. W. R. A. Dias, E. D. Moreno, and R. S. Barreto, "An Approach for Code Compression in Run Time for Embedded Systems – A Preliminary Results". In Proceedings of 11th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP 2011), Melbourne, Australia: SpringerVerlag, v. 7016. p. 349-359, October 2011. T. Bonny, and J. Henkel, "Efficient Code Density Through Lookup Table Compression". In Proceedings Design Automation and Test in Europe Conference (DATE'07), France, pages 809-814, April 2007. T. Bonny, and J. Henkel, "Instruction Splitting for Efficient Code Compression". In Proceedings of the 44th Annual Design Automation Conference (DAC'07), San Diego, California, USA, pages 646-651, June 2007. S. Klein, "Space and Time-Efficient Decoding with Canonical Huffman Trees". In Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM 1997), Aarhus, Denmark, pages 65-75, 1997. D. Seal, "ARM Architecture Reference Manual". Addison-Wesley Professional, 2nd edition, 2001, 816p. C. Lefurgy, E. Piccininni, and T. Mudge, "Evaluation of a High Performance Code Compression Method". In Proceedings of 32nd Annual International Symposium on Microarchitecture (MICRO 32), Haifa, Israel, pages 93-102, November 1999. S. I. Haider, and L. Nazhandali, "A Hybrid Code Compression Technique using Bitmask and Prefix Encoding with Enhanced Dictionary Selection". In Proceedings of the International Conference on Compilers, Architecture and Synthesis for Embedded Systems (CASES'07), Salzburg, Austria, pages 58-62, September 2007. X. H. Xu, C. T. Clarke, and S. R. Jones, "High Performance Code Compression Architecture for the Embedded ARM/THUMB Processor". In Proceedings of the First Conference on Computing Frontiers (CF'04), Ischia, Italy, pages 451-456, April 2004. D. Burger, and T. M. Austin, "The SimpleScalar Tool Set, version 2.0". ACM SIGARCH Computer Architecture News, 25(3):13-25, June 1997. MIPS® Technologies. Disponível em: http://www.mips.com. Acessado em 05 de abril de 2012.