UNIVERSIDADE FEDERAL DE SANTA CATARINA
PROGRAMA DE PÓS-GRADUAÇÃO EM
CIÊNCIA DA COMPUTAÇÃO
Leonardo Taglietti
GERAÇÃO AUTOMÁTICA DE FERRAMENTAS
DE SUPORTE AO DESENVOLVIMENTO DE
SOFTWARE EMBARCADO PARA ASIPs
Dissertação submetida à Universidade Federal de Santa Catarina,
como parte dos requisitos para obtenção do grau de
Mestre em Ciência da Computação.
Prof. Olinto José Varela Furtado, Dr.
Orientador
Prof. Luiz Cláudio Villar dos Santos, Dr.
Co-orientador
Florianópolis, fevereiro de 2005.
GERAÇÃO AUTOMÁTICA DE FERRAMENTAS
DE SUPORTE AO DESENVOLVIMENTO DE
SOFTWARE EMBARCADO PARA ASIPs
Leonardo Taglietti
Esta Dissertação foi julgada adequada para a obtenção do tı́tulo de Mestre em Ciência da
Computação (Sistemas de Computação) e aprovada em sua forma final pelo Programa de
Pós-Graduação em Ciência da Computação.
Prof. Raul Sidnei Wazlawick, Dr. (coordenador)
Banca Examinadora
Prof. Olinto José Varela Furtado, Dr. (orientador)
Prof. Luiz Cláudio Villar dos Santos, Dr. (co-orientador)
Prof. Guido Costa Souza de Araújo, Dr.
Prof. Luiz Fernando Friedrich, Dr.
“Se em horas de encontros pode haver tantos
desencontros, que a hora da separação seja, tão
somente, a hora de um verdadeiro, profundo e coletivo
encontro. De tudo ficarão três coisas: a certeza de
estar sempre começando, a certeza de que é preciso
continuar e a certeza de ser interrompido antes de
terminar. Fazer da queda um passo de dança, do medo
uma escada, do sonho uma ponte, da procura um
encontro.” Fernando Sabino
Recebi este manuscrito da Ionara, minutos antes
de partir rumo ao mestrado. Valeu, mana!
Aos meus pais, Celso e Lidia...
Agradecimentos
Neste momento, desejo compartilhar minha alegria em concluir este curso de mestrado,
exteriorizando minha gratidão:
Aos meus pais, Celso e Lidia, ao Eliseu, Jans, Ionara e Sabrina, pelo incentivo que
nunca termina e sempre me fortalece. À minha namorada Jeane, pelo amor e presença,
principalmente nos últimos meses.
Aos professores Olinto e Luiz Claúdio, pelo exemplo profissional e pela oportunidade
de trabalho. A partir das suas valiosas orientações, pude concretizar mais esta etapa da
minha vida.
Aos colegas de laboratório, pelas longas jornadas de trabalho vencidas. Em especial,
ao José Otávio, Daniel e Gabriel, pela direta participação neste trabalho.
Aos membros do Laboratório de Sistemas de Computação da UNICAMP, pela atenção
concedida.
À Vera Lúcia (Verinha), secretária da pós-graduação, pela amizade e companhia.
Ao amigo e professor Luiz Carlos Zancanella, pela amizade e incentivo constante.
Aos amigos Gilmar e Magália Benini, Geomar Martins, Roberto Leão e Alexandre
Zanatta, que de alguma forma contribuı́ram antes ou durante estes anos.
Aos professores Nelson Zang e Eduardo Appel da URI/FW, que motivaram meu ingresso no curso de mestrado.
À Universidade Federal de Santa Catarina, pela estrutura fı́sica disponibilizada. Ao
Conselho Nacional de Desenvolvimento Cientı́fico e Tecnológico do Brasil (CNPq), no
âmbito do Programa Nacional de Microeletrônica, pelo auxı́lio financeiro concedido (Bolsa
132930/2003-0).
E a Deus, fundamento da minha fé, pela constante presença.
Leonardo Taglietti
Sumário
Lista de figuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Lista de tabelas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
Lista de siglas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Resumo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1 Introdução
16
1.1
Alternativas de implementação . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2
Requisitos de um sistema embarcado . . . . . . . . . . . . . . . . . . . . . 18
1.3
Fluxo de projeto e nı́veis de descrição . . . . . . . . . . . . . . . . . . . . . 19
1.4
Contexto desta dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5
Foco e contribuições da dissertação . . . . . . . . . . . . . . . . . . . . . . 21
1.6
Organização da dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 Trabalhos correlatos
2.1
2.2
23
Um panorama das ADLs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.1
nML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.1.2
LISA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.3
EXPRESSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.4
ISDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.1.5
ArchC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Abordagens para a geração de ferramentas . . . . . . . . . . . . . . . . . . 27
2.2.1
Ferramentas de suporte . . . . . . . . . . . . . . . . . . . . . . . . . 27
6
2.2.2
2.3
Geração de montadores . . . . . . . . . . . . . . . . . . . . . . . . . 28
O trabalho proposto frente aos trabalhos correlatos . . . . . . . . . . . . . 31
3 A modelagem do microcontrolador PIC 16F84
33
3.1
Arquitetura do conjunto de instruções . . . . . . . . . . . . . . . . . . . . . 33
3.2
Caracterı́sticas gerais e peculiaridades do PIC 16F84 . . . . . . . . . . . . 35
3.2.1
Organização de memória . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.2
Banco de registradores . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3
Descrição funcional em ArchC . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4
Validação experimental do modelo . . . . . . . . . . . . . . . . . . . . . . . 39
4 A metodologia baseada em ADL
43
4.1
Visão geral da metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2
Uma visão geral do montador parametrizável . . . . . . . . . . . . . . . . . 45
5 O uso de gramáticas na geração automática de ferramentas
5.1
46
Fundamentação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.1.1
Alfabeto (ou Vocabulário) . . . . . . . . . . . . . . . . . . . . . . . 46
5.1.2
Sentença (ou Palavra) . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.1.3
Fechamento (closure) de um alfabeto . . . . . . . . . . . . . . . . . 47
5.1.4
Linguagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.5
Gramática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
5.1.6
Gramática Livre de Contexto (GLC) . . . . . . . . . . . . . . . . . 48
5.1.7
Gramática livre de contexto LL(1) . . . . . . . . . . . . . . . . . . 49
5.1.8
Geradores de analisadores léxico e sintático . . . . . . . . . . . . . . 49
5.2
Vantagens do uso de GLCs . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3
O uso de GLC para a geração de montadores . . . . . . . . . . . . . . . . . 51
5.3.1
Gramáticas envolvidas . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.3.2
Geração automática da gramática do montador . . . . . . . . . . . 52
6 Geração automática de ferramentas
6.1
55
A geração automática de montadores . . . . . . . . . . . . . . . . . . . . . 55
6.1.1
O fluxo de geração . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
6.1.2
Exemplo de geração de uma GLC . . . . . . . . . . . . . . . . . . . 57
6.2
6.3
6.1.3
Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.1.4
Verificação de inconsistências . . . . . . . . . . . . . . . . . . . . . 61
A geração automática de pré-processadores . . . . . . . . . . . . . . . . . . 62
6.2.1
O papel do pré-processador . . . . . . . . . . . . . . . . . . . . . . 62
6.2.2
O fluxo de geração . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.2.3
Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Resultados experimentais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
7 Conclusões e perspectivas
70
7.1
Produtos de trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.2
Contribuições e discussão . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.3
Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.4
Expectativa de impacto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Referências bibliográficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Lista de Figuras
1.1
Relação desempenho/potência das alternativas de implementação 18
2.1
Regra de instrução em nML . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1
Diagrama da organização do PIC 16F84 . . . . . . . . . . . . . . . . 35
3.2
Organização de memória do PIC 16F84 . . . . . . . . . . . . . . . . . 36
3.3
Registradores especı́ficos do PIC 16F84 . . . . . . . . . . . . . . . . . 37
3.4
Descrição ArchC de uma versão condensada do PIC 16F84 . . . . 38
3.5
Tamanho de código: PIC 16F84 x i8051 . . . . . . . . . . . . . . . . 41
3.6
Tempo de simulação: PIC 16F84 x i8051 . . . . . . . . . . . . . . . . 42
4.1
A metodologia de projeto adotada . . . . . . . . . . . . . . . . . . . . 44
4.2
O montador parametrizável . . . . . . . . . . . . . . . . . . . . . . . . 45
5.1
Definições regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
5.2
Definição de tokens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
6.1
O fluxo da geração de montadores . . . . . . . . . . . . . . . . . . . . 56
6.2
Exemplo de geração de GLC e lista de instruções . . . . . . . . . . 58
6.3
Gramática completa de uma descrição AC ISA em ArchC . . . . . 60
6.4
O gerador de pré-processadores . . . . . . . . . . . . . . . . . . . . . . 63
6.5
Definições reservadas de uma arquitetura fictı́cia . . . . . . . . . . . 64
6.6
Exemplo da classe AddressGenerator.h
9
. . . . . . . . . . . . . . . . 65
Lista de Tabelas
2.1
Principais ADLs e suas ferramentas . . . . . . . . . . . . . . . . . . . . . . 27
2.2
Técnicas de geração de montadores . . . . . . . . . . . . . . . . . . . . . . 32
3.1
Conjunto de instruções do PIC 16F84 . . . . . . . . . . . . . . . . . . . . . 34
3.2
Funcionalidades dos registradores especiais do PIC 16F84 . . . . . . . . . . 37
3.3
Caracterı́sticas dos benchmarks utilizados . . . . . . . . . . . . . . . . . . . 41
6.1
Tempos de geração do pré-processador e montador . . . . . . . . . . . . . . 67
6.2
Seleção de cores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
6.3
Tempos de geração do montador . . . . . . . . . . . . . . . . . . . . . . . . 68
6.4
Caracterı́sticas dos benchmarks . . . . . . . . . . . . . . . . . . . . . . . . 68
6.5
Tempos de pré-processamento e montagem de cada programa . . . . . . . . 69
10
Lista de Siglas
µPs
ADL
ALU
ASIC
ASIP
BNF
CAD
CPU
EDA
EEPROM
FPGA
FSR
GALS
HDL
IP
IR
ISS
MOPS
mW
NoC
PC
RISC
RT
SFR
SiP
SoC
UMTS
VHDL
VLIW
YACC
Microprocessors
Architecture Description Language
Arithmetic-Logic Unit
Application-Specific Integrated Circuit
Application-Specific Instruction-Set Processor
Backus-Naur Form
Computer-Aided Design
Central Processing Unit
Electronic Design Automation
Electrically Erasable Programmable Read-Only Memory
Field Programmable Gate Array
Function Selection Register
Generator of Syntactic and Lexical Analyzers
Hardware Description Language
Intellectual Property
Instruction Register
Instruction-set simulator
Millions of operations per second
Miliwatt
Network-on-chip
Program Counter
Reduced Instruction Set Computer
Register Transfer
Special Function Register
System in a Package
System-on-Chip
Universal Mobile Telecommunication System
Very High Speed Integrated Circuit Hardware Description Language
Very Long Instruction Word
Yet Another Compiler Compiler
11
Resumo
GERAÇÃO AUTOMÁTICA DE FERRAMENTAS DE SUPORTE AO
DESENVOLVIMENTO DE SOFTWARE EMBARCADO PARA ASIPs
Leonardo Taglietti
Fevereiro/2005
Orientador: Olinto José Varela Furtado
Co-orientador: Luiz Cláudio Villar dos Santos
Área de Conhecimento: Sistemas de Computação
Palavras-chave: ADL, ASIP, assembler
Número de Páginas: 76
Como resultado da evolução da Microeletrônica, é hoje possı́vel fabricar-se um sistema
embarcado em um único circuito integrado ou System-on-Chip (SoC). Um SoC compõese de uma ou mais CPUs, memórias, meios de comunicação e blocos de propriedade
intelectual ou Intelectual Property Blocks (IPs). Uma de suas alternativas de projeto é
o uso de CPU dedicada, cujo conjunto de instruções é talhado para uma dada classe de
aplicações, dando origem ao assim-chamado Application-Specific Instruction-Set Processor
(ASIP).
Como um ASIP não é um componente padrão, não há disponibilidade imediata de
ferramentas de suporte ao desenvolvimento de seu software. Tais ferramentas devem ser
geradas automaticamente, pois sua elaboração manual inviabilizaria o uso de ASIPs sob a
pressão do time-to-market. A eficiente geração de ferramentas requer o uso de Linguagens
de Descrição de Arquiteturas ou Architecture Description Languages (ADLs).
A técnica proposta nesta dissertação representa uma das etapas de uma metodologia
mais ampla. A metodologia vislumbra uma descrição ADL do ASIP como ponto de
12
partida tanto para a geração automática de ferramentas de suporte ao desenvolvimento
de software embarcado, quanto para o fluxo de projeto do hardware.
A principal contribuição desta dissertação é a concepção de um montador parametrizável. Dada uma descrição ADL da arquitetura de um ASIP, o efeito de montador
parametrizável é obtido através da geração automática de um pré-processador e de um
montador para a arquitetura descrita. A automação ampara-se em técnicas formais baseadas em Gramática Livre de Contexto (GLC) para a geração de parsers.
A técnica proposta baseia-se em uma especificação unificada dos aspectos léxicos e
sintáticos da linguagem e em um novo algoritmo para a geração de GLC. A eficiência
da técnica é mostrada experimentalmente tanto para as ferramentas geradoras, quanto
para as ferramentas geradas. Robustez e corretude são garantidas formalmente. A manutenibilidade e a extensibilidade do montador parametrizável são viabilizadas por um
mecanismo de co-validação entre linguagem e gramática, bem como por mecanismos de
verificação de expressões regulares.
Vários experimentos foram realizados para assegurar a validação e avaliar a eficiência
da técnica proposta. Nos experimentos, foram utilizados programas extraı́dos do benchmark do bem conhecido Projeto Dalton, os quais foram montados para três CPUs-alvo:
PIC 16F84, PowerPC 405 e MIPS.
A ADL adotada nesta dissertação é ArchC, que possui a caracterı́stica única de gerar
modelos escritos em SystemC. Para a familiarização com a ADL, adotou-se o microcontrolador PIC 16F84, de uso bastante difundido, como estudo de caso. Assim, um dos
produtos de trabalho desta dissertação é um modelo funcional daquele microcontrolador,
devidamente validado.
13
Abstract
AUTOMATIC GENERATION OF SUPORTING TOOLS FOR
ASIP EMBEDDED SOFTWARE DEVELOPMENT
Leonardo Taglietti
February/2005
Adivisor: Olinto José Varela Furtado
Co- Adivisor: Luiz Cláudio Villar dos Santos
Area of Concentration: Design Automation Systems
Keywords: ADL, ASIP, assembler
Number of Pages: 76
As a result of the evolution of Microelectronics, it is possible today to design an embedded system in a single integrated circuit, which is known as System-on-Chip (SoC). A SoC
is composed of one or more CPUs, memories, communication network and Intellectual
Property Blocks (IPs). One of its design alternatives is the use of a dedicated CPU, whose
instruction set is tailored to for one application class, leading to an Application-Specific
Instruction-Set Processor (ASIP).
Since an ASIP is not a standard component, supporting tools to its software development are not immediately available. Such tools must be automatically generated,
otherwise its manual design would make impractical the use of ASIPs under the current time-to-market pressure. Efficient tool generation requires the use of Architecture
Description Languages (ADLs).
The technique proposed in this dissertation represents one of the steps of a broader
methodology. The envisaged methodology adopts an ADL description of the ASIP as a
14
starting point not only for the automatic generation of supporting tools for embedded
software development, but also for the hardware design flow.
The main contribution of this dissertation is the design of a parameterizable assembler
tool. Given an ADL description of the ASIP’s architecture, the effect of parameterizable
assembler results from the automatic generation of pre-processing and assembling tools for
the described architecture. Automation relies on formal techniques based on Context-Free
Grammar (CFG) for parser generation.
The proposed technique is based upon a unified specification of lexical and syntactic
aspects of the language and on a novel algorithm for CFG generation. The technique’s
efficiency was shown experimentally for both the generating and the generated tools.
Robustness and correctness are guaranteed by the formal framework. Maintainability and
extensibility are provided by a co-validation mechanism between language and grammar
and by a regular expression verification mechanism.
Several experiments were performed for validation and efficiency evaluation. Programs
from the well-known Dalton Project benchmark were assembled for three target CPUs:
PIC 16F84, PowerPC 405 e MIPS.
The ADL adopted in this dissertation is ArchC, which has the unique feature of generating SystemC models. For acquaintance with the ADL, the well-known microcontroller
PIC 16F84 was used as a case study. As a result, one of the dissertation’s work products
is a functional model of that microcontroller, properly validated.
15
Capı́tulo 1
Introdução
A tecnologia de Microeletrônica tem evoluı́do significativamente há mais de três décadas. Essa evolução é regida pela Lei de Moore, a qual prevê que, a cada 18 meses,
dobra o número de transistores em um circuito integrado (CI), tornando-o cada vez mais
complexo. Devido a esse crescimento, em progressão geométrica, os projetos de CIs
tornam-se viáveis apenas se utilizadas ferramentas de Computer-Aided Design (CAD) ou
Electronic Design Automation (EDA).
Muitos produtos eletrônicos são sistemas integrados de hardware e software, formando
os denominados embedded systems ou sistemas embutidos/embarcados. Um sistema
embarcado é qualquer dispositivo que contenha um computador programável e que não
seja utilizado ou entendido como um computador de propósito geral [Wol00].
Há uma grande variedade de aplicações que utilizam sistemas embarcados, tais como
eletrodomésticos, automóveis, aviões, equipamentos médicos, automação industrial, sistemas de telecomunicações, etc. Atualmente, 79% dos processadores de alto desempenho
no mercado são usados em sistemas embutidos [Mar03b]. Segundo Marwedel [Mar03b],
os modelos de automóveis mais avançados da marca BMW contêm mais de 100 microprocessadores.
1.1 Alternativas de implementação
Inicialmente, os sistemas embarcados eram construı́dos com seus componentes (chips)
montados em placas de circuito impresso. A evolução tecnológica permitiu que um sistema
embarcado pudesse ser acomodado em poucas pastilhas dentro de um único encapsula-
16
mento. Essa alternativa é denominada System in a Package (SiP).
A continuidade dessa evolução tornou possı́vel o projeto de um sistema embarcado em
um único circuito integrado, originando a noção de System-on-Chip (SoC). Um SoC
pode agregar uma ou mais CPUs, blocos de propriedade intelectual ou Intelectual Property
Blocks (IPs), memórias, unidades de entrada/saı́da, etc. A infraestrutura de comunicação
entre IPs é, em geral, uma estrutura de barramentos ou pode ser uma rede em chip ou
Network-on-a-Chip (NoC)[Dea01]. Além disso, um IP pode necessitar de parâmetros de
operação ou configuração ou de um programa (caso de um processador).
As CPUs padrão foram desenvolvidas originalmente para aplicações de propósitos
gerais nos mercados de desktop e servidores. Como o conjunto de instruções de uma CPU
padrão é projetado para atender os requisitos de uma larga faixa de aplicações, vários
recursos do processador podem ficar ociosos ou sub-utilizados. Embora pouco ou nada
contribuam para uma dada aplicação, tais recursos ociosos contribuem para o consumo
de potência da CPU. Por isso, várias CPUs padrão (tais como PowerPC, MIPS e ARM)
possuem versões projetadas para o mercado de sistemas embarcados, onde o consumo
de potência pode ser reduzido desligando-se o relógio dos recursos ociosos, colocando a
máquina em modos de operação de baixa potência ou permitindo a redução da tensão e
da freqüência dinamicamente para minimizar o consumo de potência [Mar03b].
Para garantir desempenho adequado e baixo consumo de potência, uma das alternativas é o uso de uma CPU dedicada ou Application-Specific Instruction-Set Processor
(ASIP). Um ASIP caracteriza-se por um conjunto de instruções talhado para uma classe
especı́fica de aplicações.
Como um ASIP não é um componente padrão, as ferramentas de suporte ao desenvolvimento de seu software embarcado não estão disponı́veis. Diante da pressão do time-tomarket, essa indisponibilidade de ferramentas torna imperativa sua geração automática,
pois a elaboração manual inviabilizaria o uso de ASIPs.
Para aplicações de alto desempenho e de alto volume de mercado, podem ser utilizados circuitos integrados de aplicação especı́fica ou Application-Specific Integrated Circuits
(ASICs). ASICs são caracterizados por uma única aplicação e por isso não são programáveis, resultando em inflexibilidade e alto custo.
17
1.2
Requisitos de um sistema embarcado
Segundo Marwedel [Mar03b], além dos requisitos funcionais e de qualidade de serviço,
aos sistemas embarcados costumam ser impostas algumas restrições. As principais são:
• Restrição de tamanho de código (devido à escassez de memória);
• Restrição de consumo de potência e energia (devido à operação com bateria);
• Restrições de tempo real (devido ao timing da aplicação);
O consumo de potência e energia tem se mostrado como a restrição dominante. Por
exemplo, a transmissão de dados através de telefones celulares com tecnologia UMTS
resulta na exaustão da bateria em cerca de uma hora [Mar03b].
Figura 1.1: Relação desempenho/potência das alternativas de implementação
A Figura 1.1, adaptada da original em [Mar03b], ilustra o compromisso entre a
eficiência energética e a flexibilidade de diferentes alternativas de implementação: processador de uso geral, lógica reconfigurável e ASIC. O eixo das abscissas representa a
escala de miniaturização das tecnologias de circuitos integrados (tamanho mı́nimo dos
transistores). O eixo das ordenadas representa a eficiência energética, ou seja, o desempenho obtido por miliwatt (mW) de potência consumida. Note que a eficiência energética
dos ASIPs é da mesma ordem de grandeza da alternativa em lógica reconfigurável.
Observa-se que, para uma alternativa de implementação arbitrária, a miniaturização
provoca aumento da eficiência energética. Por outro lado, para uma dada tecnologia, a
18
eficiência energética diminui com a flexibilidade da alternativa de implementação. Por
exemplo, embora um processador de uso geral ofereça mais flexibilidade à alteração de
funcionalidade de uma aplicação, sua eficiência energética é de uma ordem de magnitude
inferior à uma implementada usando lógica reconfigurável. Por sua vez, o ASIC apresenta
a maior eficiência energética, mas possui a menor flexibilidade, pois sua personalização é
realizada em hardware não programável.
É importante lembrar que o custo de desenvolvimento de circuitos integrados aumenta
com a eficiência energética. Diante disso, o projeto de um ASIP justifica-se como um
compromisso entre eficiência energética, flexibilidade e custo.
1.3
Fluxo de projeto e nı́veis de descrição
Um componente de um sistema embarcado pode ser modelado em vários nı́veis de
abstração [Gea02], tais como:
• Nı́vel funcional: a funcionalidade é modelada sem considerar como o sistema será
implementado.
• Nı́vel comportamental: a funcionalidade é modelada independentemente da futura implementação, mas a temporização dos eventos na interface já possui precisão
de ciclos.
• Nı́vel RT (register-transfer): a modelagem reflete a estrutura do hardware em
termos de registradores, unidades funcionais, barramentos e unidade de controle. A
temporização dos eventos é precisa tanto na interface quanto na estrutura interna.
• Nı́vel lógico: reflete a estrutura interna do componente em termos de portas lógicas
e elementos de armazenamento. A temporização é ainda mais precisa que aquela
descrita no nı́vel RT.
O projeto de cada componente envolve refinamentos sucessivos de uma descrição mais
abstrata para uma menos abstrata. Geralmente inicia-se com uma descrição puramente
funcional, sem considerar como o sistema será implementado. Posteriormente, pode-se
adicionar ao modelo outras caracterı́sticas, como por exemplo, precisão de ciclos. Sucessivos nı́veis vão sendo construı́dos e refinados, visando chegar a um modelo em nı́vel
19
RT, que costuma ser descrito em uma Linguagem de Descrição de Hardware ou
Hardware Description Language (HDL). A indústria de EDA produz uma infinidade de
ferramentas de projeto com entrada HDL, cuja utilização foi disseminada para a indústria
de sistemas. VHDL e Verilog são HDLs fortemente estabelecidas na indústria de EDA e
na indústria de sistemas.
Algumas linguagens e extensões foram propostas visando aumentar o nı́vel de abstração do projeto de sistemas (System-Level Design). Este nı́vel de descrição de sistemas
é suportado por SystemC [Sys04], uma extensão das bibliotecas padrão da linguagem
C++, através da qual é também possı́vel descrever caracterı́sticas de sistemas embarcados, tais como paralelismo do hardware, tempo, separação entre funcionalidade e comunicação, etc. SystemC é considerada a linguagem mais promissora para a modelagem
de sistemas embarcados, especialmente nos mais altos nı́veis de abstração [Mar03a]. Em
princı́pio, qualquer componente digital de um sistema embarcado pode ser descrito em
SystemC no nı́vel funcional. Entretanto, um modelo descrito em SystemC admite tantos
estilos de descrição que inviabiliza a geração automática eficiente de ferramentas de suporte. Essa dificuldade é contornada com a introdução de Linguagens de Descrição
de Arquiteturas ou Architecture Description Languages (ADLs).
Uma ADL é uma linguagem cujas primitivas permitem a descrição do conjunto de
instruções de uma CPU e, possivelmente, de algumas caracterı́sticas e parâmetros de
sua organização (comprimento da palavra de instrução, códigos de operações, bancos de
registradores, memórias, etc).
Observa-se que o uso de ADLs torna mais pragmática e eficiente a geração automática
de ferramentas de suporte ao desenvolvimento de software embarcado, além de facilitar o
projeto do hardware do ASIP.
1.4 Contexto desta dissertação
O projeto de um sistema embarcado envolve o projeto do hardware e o desenvolvimento do software. Como o software não pode ser depurado sem uma plataforma de
hardware, as metodologias de projeto antigas consistiam no projeto do hardware, seguido
do projeto do software e da chamada integração software-hardware. Nesta abordagem de projeto, a detecção tardia de erros pode resultar em vários ciclos de re-projeto.
Diante das necessidades de redução de custo de engenharia não recorrente [Wol00] e da
20
pressão do time-to-market, uma metodologia de co-projeto de hardware e software
(HW/SW Co-design) tornou-se mandatória.
A técnica de co-projeto requer que o software seja desenvolvido e depurado antes do
hardware estar disponı́vel. Para isso, o software deve ser testado em um modelo executável
do hardware. Assim, o co-projeto de hardware e software pode amparar-se em ADLs para
a geração de modelos executáveis, permitindo vislumbrar uma metodologia de projeto
onde uma descrição ADL é o ponto de partida, em nı́vel funcional, do fluxo de projeto de
um ASIP.
As técnicas abordadas nesta dissertação situam-se no contexto de uma metodologia
de suporte ao uso de ASIPs em SoCs. A metodologia vislumbrada tem os seguintes
pressupostos:
• A descrição ADL do ASIP é o ponto de partida para o fluxo de projeto do hardware
(manual ou automático).
• A descrição ADL do ASIP é o ponto de partida para a geração automática de modelos funcionais e ferramentas de suporte ao desenvolvimento de software embarcado,
tais como montador, compilador cruzado, simulador do conjunto de instruções, etc.
Esta dissertação situa-se no âmbito do segundo pressuposto, conforme descrito na
próxima seção.
1.5
Foco e contribuições da dissertação
A principal contribuição desta dissertação é a concepção e a implementação de um
programa montador parametrizável a partir de uma descrição ADL. O montador parametrizável baseado em ADL é obtido a partir da geração automática de um pré-processador
e de um montador para a arquitetura do conjunto de instruções representada na descrição
ADL. Assim, sempre que uma nova instrução for adicionada ao conjunto de instruções de
um ASIP, um novo programa montador pode ser produzido automaticamente.
Para fins de estudo de caso, foi desenvolvido um modelo funcional do microcontrolador
PIC 16F84 [Inc04b], de uso bastante difundido, para fazer o papel de um core parametrizável. Além desse modelo, foram também utilizados modelos do MIPS [Arc04] e do
PowerPC 405 [Fea04], para fins de validação e avaliação do montador parametrizável.
21
Esta dissertação está situada no âmbito do Projeto DESERT (Desenvolvimento de
Ferramentas para Sistemas Embutidos de Tempo Real), o qual visa contribuir com novas técnicas de EDA para o desenvolvimento de sistemas embarcados. A execução das
atividades de pesquisa é amparada por bolsa de mestrado do Conselho Nacional de Desenvolvimento Cientı́fico e Tecnológico (CNPq), no âmbito do Programa Nacional de
Microeletrônica (PNM).
1.6
Organização da dissertação
A presente dissertação é assim organizada: no Capı́tulo 2 são discutidos alguns trabalhos correlatos, com foco na geração automática de ferramentas a partir de ADLs. Uma
breve descrição do estudo de caso, baseada no microcontrolador PIC 16F84, é discutida no
Capı́tulo 3. Este capı́tulo discute também a modelagem do PIC implementada em ArchC
e mostra os resultados experimentais obtidos a partir deste modelo. O Capı́tulo 4 detalha
a metodologia baseada em ADL que norteia a dissertação, delimitando seu escopo. No
Capı́tulo 5, descreve-se o papel das gramáticas na geração de parsers. O Capı́tulo 6 descreve as técnicas de geração de montadores e pré-processadores. Neste capı́tulo também
são mostrados os resultados experimentais obtidos a partir das ferramentas desenvolvidas.
As conclusões e perspectivas de trabalhos futuros são apresentadas no Capı́tulo 7.
22
Capı́tulo 2
Trabalhos correlatos
As linguagens de descrição de arquiteturas existentes variam muito em sua expressividade, de acordo com os objetivos a que se propõem. As caracterı́sticas estruturais,
comportamentais e de sintaxe influenciam diretamente os métodos de geração de ferramentas a partir destas ADLs, podendo dificultar e até mesmo inviabilizar a completa
geração destas ferramentas.
Segundo Hadjiyiannis [Hea97a], algumas caracterı́sticas desejáveis em uma ADL são:
• Representação de uma grande variedade de arquiteturas.
• Definição de restrições que definem grupos de operações válidas dentro de uma
instrução.
• Fácil modificação do compilador e/ou arquitetura.
• Suporte a geração automática de montador, simulador e gerador de código.
• Informações adequadas para otimizações de código.
Em seguida, as ADLs mais difundidas são analisadas em termos de suas principais
caracterı́sticas.
2.1
2.1.1
Um panorama das ADLs
nML
nML foi desenvolvida na Technical University of Berlin (TUB). Seu desenvolvimento
baseou-se na observação das informações que estão disponı́veis nos manuais de processa23
dores, tais como lista de instruções, operações entre registradores, sintaxe da linguagem
de montagem, modos de endereçamento, etc. Em nML, a estrutura da arquitetura é descrita junto com o comportamento das instruções, misturando informações estruturais e
comportamentais. A falta de flexibilidade na descrição de comportamentos traz inúmeras
dificuldades no uso de nML [Hea97b].
A versão original de nML não oferecia suporte a self-modifying code 1 e instruções
multi-ciclos. O conjunto de instruções é descrito por uma gramática com atributos. Ações
semânticas de qualquer instrução podem ser compostas de vários fragmentos distribuı́dos
na árvore da gramática, permitindo compartilhar comportamentos, codificações e sintaxe
entre várias instruções. Em nML, a execução de um programa tem por objetivo alterar o
conteúdo de registradores.
A partir de descrições nML, projetistas da TUB e de outros grupos de pesquisa desenvolveram ferramentas, tais como geradores de código e simuladores.
2.1.2
LISA
LISA foi desenvolvida para permitir a geração automática de simuladores, utilizando a
técnica de simulação compilada, com precisão de ciclos e de bits. Uma contribuição inicial
desta ADL foi a descrição de pipeline em nı́vel de operação e o modelo de sequenciamento.
A descrição de uma arquitetura em LISA envolve declarações de recursos e de operações,
sendo estas os elementos básicos da linguagem. As operações são divididas em várias
seções de acordo com diferentes propriedades do sistema e representam a visão do programador quanto à estrutura, conjunto de instruções e comportamento da arquitetura.
Memórias, registradores e pipelines fazem parte dos recursos disponı́veis na arquitetura. O pipeline possui execução sı́ncrona e as operações são atribuı́das a estágios de
pipeline.
Uma nova versão de LISA [Pea99] permite a geração automática de simuladores e
montadores para diversas classes de arquitetura. LPDP [Sea02] é uma extensão de LISA
voltada para o projeto de ASIPs, tendo por base uma descrição LISA. LPDP possibilita
a geração de ferramentas de desenvolvimento de software. Entre as extensões disponibilizadas estão a geração automática do back-end de um compilador C e de um modelo
sintetizável em HDL.
1
Código que pode modificar-se dinamicamente.
24
O modelo de memória inclui todas as memórias e registradores do sistema. O modelo de recursos descreve a estrutura do hardware, determinando suas restrições. Tais
informações são utilizadas pelo compilador para realizar o escalonamento das instruções,
possibilitando assim o compartilhamento de recursos.
Extensões de LISA [Bea04] recentemente publicadas possibilitam a geração de compiladores C. As informações necessárias são extraı́das de uma descrição LISA e as outras
são informadas manualmente pelo usuário. O arquivo de saı́da é uma descrição no formato CGD (Code Generator Description) [LIS04], para a qual já existem ferramentas de
geração de compiladores C.
2.1.3
EXPRESSION
A ADL EXPRESSION é voltada para a descrição de arquiteturas para SoCs, através
da qual é possı́vel gerar ferramentas automaticamente. Expression permite a especificação
de sistemas de memória e, seguindo o mesmo paradigma de LISA, mistura informações
estruturais e comportamentais.
As técnicas encontradas em [Gea99] possibilitam a geração automática de compiladores. Mishra [Mea01] introduziu uma metodologia de projeto baseada em abstração
funcional, na qual foram definidas funções parametrizadas para unidades funcionais de
arquiteturas reconfiguráveis (unidade de busca, predição de desvios, etc) oferecendo suporte para a geração de ferramentas.
2.1.4
ISDL
A linguagem ISDL (Instruction Set Description Language for Retargetability) é uma
ADL comportamental e foi apresentada juntamente com um gerador automático de montadores. Mesmo sendo especialmente voltada para arquiteturas do tipo VLIW (Very Long
Instruction Word ), ISDL foi projetada com capacidade de redirecionamento automático
de compiladores, possibilitando descrever várias classes de arquiteturas. As descrições
da parte estrutural, usadas para gerar modelos de hardware, são extraı́das do simulador
do conjunto de instruções e das descrições de operação (geralmente no nı́vel RT). Por
exemplo, as informações de latência e atraso modeladas no simulador são cruciais para a
geração destes modelos.
Algumas ferramentas existentes para ISDL são: gerador de geradores de código, gera25
dor de simuladores e gerador de modelos de hardware. Segundo Hadjiyiannis [Hea97a], não
é possı́vel descrever instruções multi-ciclos de tamanho variável, sendo esta uma grande
restrição da ADL.
2.1.5
ArchC
Tornada pública recentemente e adotada como ponto central para o desenvolvimento
desta dissertação, ArchC [Rig04] destaca-se por ser a primeira ADL que gera simuladores
(modelos executáveis) escritos em SystemC [Sys04]. Os focos iniciais desta ADL são a
simulação e a co-verificação. Entretanto, foi projetada também para oferecer suporte a
outras ferramentas que ainda estão em fase de desenvolvimento, tais como montadores,
ligadores, compiladores e geradores de código.
ArchC permite a declaração de recursos da arquitetura (denominado AC ARCH), tais
como registradores, bancos de registradores e memórias. Além disso, é possı́vel definir o
tamanho da palavra de dados da arquitetura, estágios de pipeline, etc. Os registradores
podem ser associados a formatos de instrução ou ao tamanho da palavra de dados da
arquitetura.
A descrição do conjunto de instruções da arquitetura (denominado AC ISA) fornece
detalhes sobre formatos de instrução (campos, tamanhos, etc.), sintaxe assembly e códigos
operacionais. Um exemplo de descrição ArchC será mostrado na Seção 3.3.
ArchC possui um pré-processador composto por um parser, um gerador de simuladores
e um geradores de decodificadores. A partir das informações extraı́das das descrições AC ISA e AC ARCH, o pré-processador ArchC gera classes C++ e/ou módulos SystemC que
farão parte do código fonte do simulador. Os comportamentos das instruções são implementados manualmente. O decodificador recebe uma seqüência de bits lidos da memória
e utiliza os códigos operacionais para identificar qual instrução deve ser executada.
O simulador do conjunto de instruções, gerado a partir de uma descrição ArchC, pode
ser integrado a outros modelos, sendo esta uma das grandes vantagens de sua utilização.
ArchC é licenciada sob a GNU Lesser General Public License (LGPL) e encontra-se
disponı́vel em [Rig04].
Uma comparação entre ADLs, extraı́da de [Rig04], é apresentada na Tabela 2.1. Nesta
tabela, a letra F denota a não disponibilidade atual de duas ferramentas na versão atual
do pacote ArchC, embora haja pesquisas em andamento para esse fim.
26
Tabela 2.1: Principais ADLs e suas ferramentas
Caracterı́sticas
LISA
EXPRESSION
nML
ISDL
ArchC
Conjunto de instruções
*
*
*
*
*
Precisão de ciclos
*
*
*
Suporte a multi-ciclo
*
*
*
Suporte a pipeline
*
*
*
Hierarquia de memória
*
*
*
Emulação de sistema operacional
*
Hierarquia de comportamentos
*
Co-verificação
*
Geração de simuladores escritos em SystemC
*
Geração de montadores
*
*
Simulação compilada
*
*
Redirecionamento de compiladores
*
*
2.2
2.2.1
*
F
*
*
F
Abordagens para a geração de ferramentas
Ferramentas de suporte
A partir de código-fonte escrito em linguagem de alto nı́vel (geralmente C/C++), é
possı́vel gerar código executável para uma arquitetura alvo com o auxı́lio de compiladores cruzados (cross-compilers). Geralmente, é realizada a alteração/construção do
back-end de algum compilador existente a partir da arquitetura desejada. A crescente
demanda por cross-compilers exige sua completa geração automática ou, de maneira parcial, a geração automática de seu back-end. Esta última alternativa é largamente utilizada,
principalmente quando se trata de compiladores com código-fonte aberto, como o GCC
da GNU [GNU04].
A adoção de determinada metodologia para geração de ferramentas de software está
fortemente relacionada com o tipo de projeto. No projeto de sistemas embarcados, fatores como classes de arquiteturas, linguagens de programação, ADLs e HDLs devem ser
considerados. Por exemplo, apesar de a ADL nML possibilitar a descrição de uma grande
variedade de arquiteturas, suas caracterı́sticas especı́ficas podem subsidiar o crescimento
da complexidade no desenvolvimento de ferramentas. Na descrição em nML mostrada na
27
Figura 2.1 (reproduzida de [Hea97b]), a estrutura da arquitetura é definida juntamente
com informações do nı́vel RT (seção action).
Figura 2.1: Regra de instrução em nML
A complexidade das caracterı́sticas apresentadas motivam a geração de descrições
intermediárias para facilitar o processo de geração das ferramentas. Entretanto, nem
sempre estão completas. Por exemplo, o assembler apresentado por Hartoog [Hea97b]
não apresenta suporte a labels, declarações de variáveis e diretivas.
A adoção de uma determinada ADL que atenda as necessidades dos desenvolvedores
de ferramentas é um fator que deve ser considerado. Na ADL ArchC, por exemplo,
as informações do nı́vel RT e da arquitetura do conjunto de instruções estão definidas
separadamente, facilitando o desenvolvimento de ferramentas.
2.2.2
Geração de montadores
As técnicas de geração de montadores vem sendo pesquisadas desde a década de 70.
Primeiramente, eram adotadas técnicas adhoc baseadas na similaridade entre as linguagens assembly [Wea87]. Posteriormente, técnicas formais baseadas em gramáticas foram introduzidas, possibilitando a geração automática do parser da linguagem assembly [Tra87]. Entretanto, ainda eram necessárias intervenções manuais para a definição da
gramática.
Nas descrições de arquiteturas através de uma HDL, são inseridas informações desnecessárias para a geração de montadores. Tal fato contribuiu para o aparecimento das
representações intermediárias, contendo somente informações relevantes para a geração de
ferramentas, tais como assemblers. Paralelamente, esta evolução colaborou para a geração
automática de gramáticas, e conseqüentemente, dos parsers a partir delas gerados.
Com o surgimento das ADLs, as informações relevantes para a geração automática de
ferramentas são capturadas diretamente pelo parsing da ADL [Hea97a] [Bea04] [Fre93]
28
[Pea99] [Hea99]. Os simuladores (modelo executável) gerados a partir de ADLs precisam ser amparados por montadores para viabilizar o processo de simulação. Daı́ surge a
necessidade de geração automática de montadores.
Baseados em técnicas formais para a realização do parsing e geração de código, a maioria dos geradores de montadores pesquisados [Hea97a] [Kum00] [CF90] produzem as
definições léxicas com a notação usada no gerador de analisadores léxico Lex [GNU04],
e as definições sintáticas com a notação usada no gerador de analisadores sintáticos Bison [GNU04] ou Yacc [YAC04]. O Yacc, utilizado por exemplo nas implementações em
[Hea97a], é um dos mais difundidos geradores de parsers. Entretanto, é limitado à técnica
de análise sintática LALR(1) e não possui um mecanismo de co-validação entre linguagem
e gramática.
Alguns fatores limitam e dificultam o processo de geração de montadores, tais como:
• heterogeneidade das arquiteturas;
• mistura de informações estruturais e comportamentais na descrição ADL;
• sintaxe assembly;
Em [Kum00], é apresentado um gerador de montadores para a linguagem Sim-nML
(uma extensão de nML). Para construir o parser do montador, são gerados arquivos Lex
e Yacc. Opcionalmente, o gerador poderá incluir um arquivo com informações de realocação em tempo de ligação para a máquina especı́fica. Uma descrição em Sim-nML
deve ser convertida para um formato intermediário e posteriormente armazenada em outro
arquivo, o qual será a entrada principal do gerador de montadores. Este gerador possui
tabelas que contêm, entre outras informações, atributos, regras, sintaxes e tipos de dados,
e gera como saı́da um arquivo no formato ELF [ELF04]. Estas informações opcionais são
definidas separadamente em um arquivo de configuração.
Um gerador de montadores desenvolvido para a ADL ISDL [Hea97a] produz arquivos
com padrão Lex e Yacc, a partir dos quais são gerados o analisador léxico e o parser do
montador. O analisador léxico inclui, em sua tabela de sı́mbolos, os seguintes componentes:
• Tipos de dados pré-definidos;
• Nomes de operações;
29
• Tokens da definição global ISDL;
• Labels (endereços simbólicos);
Antes da realização do parsing, um script invoca um pré-processador C para resolução
de macros, pseudo-instruções e inclusões (links), gerando como saı́da um arquivo com
código assembly. O montador processa este arquivo assembly em dois passos. Primeiramente, o gerenciador do parser presente no arquivo de definições Yacc realiza inicializações
no arquivo de entrada e preenche uma tabela de sı́mbolos. No passo seguinte, realiza a
resolução de labels e conclui a montagem baseada nas informações obtidas da descrição
ISDL.
Ferguson [Fer66] apresenta um gerador de montadores chamado de meta-assembler
que, ao invés de partir de uma descrição de máquina, recebe como entrada declarações
de macros, as quais empacotam campos em palavras através de manipulações de bits.
O meta-assembler implementa cada instrução através de uma macro, inserindo algumas
facilidades para incluir e referenciar operandos na palavra de instrução. O tamanho da
palavra de dados e algumas caracterı́sticas da arquitetura são representados por variáveis
globais. A geração de um novo assembler ocorre através da definição e redefinição de
macros para as instruções, caracterizando o meta-assembler como um processador de
macros.
Uma vantagem desta técnica é a padronização do software que realiza a avaliação de
expressões, manipulação de tabelas de sı́mbolos e análise sintática. Apesar disso, Wick
[Wic75] apresenta as seguintes desvantagens do meta-assembler :
• Baixo desempenho no processo de montagem;
• Ineficiência e inflexibilidade;
• Difı́cil sustentação de hipótese sobre as classes de máquinas que podem ser tratadas;
A técnica apresentada por Wick [Wic75] baseia-se em tradução dirigida pela sintaxe, com foco principal no processo de geração de código. Após análise de montadores
existentes, o autor obteve um modelo genérico baseado em caracterı́sticas padrão. As
estruturas de dados são construı́das a partir de informações especı́ficas da máquina, tais
como formatos, opcodes e operandos.
30
Em Abbaspour [Aea02], o reconhecimento de programas escritos em linguagem assembly baseia-se em definições especı́ficas, utilizando caracteres especiais para representação
de operandos, tais como registradores e valores imediatos. Portanto, o reconhecimento
léxico e sintático não é realizado através de software gerado a partir do Lex e Yacc/Bison.
Além disso, não é utilizado o formalismo Backus-Naur Form (BNF) para descrever a sintaxe da linguagem. A técnica apresentada pelo autor possui foco na geração da Aplication
Binary Interface (ABI) para diferentes ADLs, realizando o redirecionamento da saı́da do
GNU assembler gas. Porém, não ficam evidentes as técnicas utilizadas para a geração do
código fonte do montador.
2.3
O trabalho proposto frente aos trabalhos correlatos
A partir da análise de trabalhos correlatos, verificou-se o uso comum de gramáticas
como a técnica formal adotada nas implementações. As gramáticas são usadas para a
geração de parsers que reconheçam descrições em ADLs, arquivos de configurações e programas escritos em linguagem de montagem. Por exemplo, a definição de valores de campos ou registradores no formato hexadecimal pode ser usada para gerar a representação
léxica destes valores, fazendo com que o montador gerado reconheça programas escritos
em linguagem assembly com operandos neste formato de numeração.
A partir de uma descrição em ADL, é possı́vel extrair os tokens e as regras sintáticas
da linguagem, permitindo a geração automática da gramática que representa a linguagem assembly da arquitetura descrita e, posteriormente, a geração automática do
parser a partir da gramática gerada. Os conceitos, caracterı́sticas e vantagens do uso de
gramáticas são apresentadas no Capı́tulo 5.
O gerador de montadores apresentado por Kumari [Kum00] exige a definição de macros
juntamente com a descrição ADL. O autor afirma que se for usado como entrada um
arquivo gerado por um cross-compiler do PowerPC 603, as informações sobre pseudoinstruções e macros deverão ser manualmente substituı́das por instruções nativas.
O processo de montagem pode ser realizado em único passo durante o parsing de um
programa assembly. Entretanto, este processo pode ser amparado por funções especı́ficas,
tais como no montador criado por Hadjiyiannis [Hea97a]. Neste caso, a montagem é
realizada em dois passos e o processamento de labels é realizado por funções especı́ficas.
A Tabela 2.2 compara algumas caracterı́sticas envolvidas no processo de geração de
31
montadores. A coluna denominada ASMGen representa o gerador de montadores desenvolvido nesta dissertação. Caracterı́sticas não suportadas são denotadas pela letra “N”;
caracterı́sticas presentes são indicadas pela letra “S”.
Tabela 2.2: Técnicas de geração de montadores
Caracterı́sticas e suportes
Kumari[Kum00]
ASMGen
Gerador de analisador léxico
Lex [LEX04]
GALS [Ges04]
Gerador de parser
Yacc [YAC04]
GALS [Ges04]
Palavras-chave
Arquivo especı́fico (separado)
Desnecessário
Entrada para o gerador de
Arquivo intermediário, gerado
Descrição ArchC
montadores
a partir de uma descrição Sim-nML
Pré-processador
S
S
Tamanho de instrução
S
S
Formato de instrução
S
S
Representação binária
S
N
Suporte a labels
S
S
O gerador de montadores aqui proposto assume que todas as instruções sejam nativas. Porém, como o uso de pseudo-instruções e macros é usual, um gerador de préprocessadores foi desenvolvido. Tal gerador produz um pré-processador capaz de expandir macros, substituir pseudo-instruções por instruções nativas, calcular endereços-alvo
de desvio, etc. Assim, a adoção de um módulo pré-processador simplifica o processo de
geração do montador.
Para a geração de parsers, foi adotado o GALS [Ges04], um gerador de analisadores léxico e sintático desenvolvido na Universidade Federal de Santa Catarina. Em seu
ambiente de desenvolvimento, é possı́vel especificar os aspectos léxicos e sintáticos de
maneira unificada. Além da técnica de análise sintática LALR(1) presente no Yacc, o
GALS suporta também as técnicas SLR(1), LR(1) e preditiva LL(1) [Aea88]. Uma das
mais importantes caracterı́sticas do GALS é a disponibilidade de um simulador para a
co-validação entre linguagem e gramática, bem como mecanismos de depuração de expressões regulares. Tais caracterı́sticas resultam na manutenibilidade e extensibilidade do
gerador de montadores.
32
Capı́tulo 3
A modelagem do microcontrolador PIC
16F84
Este capı́tulo descreve sucintamente a arquitetura e a organização do microcontrolador
PIC (Seções 3.1 e 3.2), adotado como estudo de caso. Além disso, o capı́tulo apresenta uma
versão condensada da descrição funcional do PIC em ArchC (Seção 3.3). A Tabela 3.1 e as
figuras desta seção são reproduções das originais, retiradas do manual do microcontrolador
[Inc04b]. Ao final, o capı́tulo relata a validação do modelo, descrevendo os resultados
experimentais.
3.1 Arquitetura do conjunto de instruções
O PIC é um microcontrolador da famı́lia RISC que adota a arquitetura Harvard,
sucintamente mostrada na Figura 3.1. Sua arquitetura é baseada em acumulador (8
bits), ou seja, um dos operandos é sempre armazenado no acumulador (denotado pela
letra W). A Tabela 3.1 mostra o conjunto das 35 instruções do PIC, divididas em 3
diferentes formatos, baseados nas seguintes operações:
• Operações orientadas a byte: existem 18 instruções mapeadas para este formato.
As instruções movwf e clrf possuem apenas um operando e as instruções nop e clrw
não possuem operandos. Todas as instruções restantes possuem dois operandos.
• Operações orientadas a bit: apenas 4 instruções são mapeadas para este formato,
a partir das quais é possı́vel testar e manipular, em nı́vel de bit, o conteúdo do banco
33
de registradores do PIC. Por exemplo, através das instruções btfsc e btfss realizam-se
os desvios condicionais.
• Operações de controle/literal: através das instruções mapeadas para este formato, realizam-se operações de controle do hardware do microcontrolador e também
a inserção de valores (imediatos) na memória de dados. As instruções call, goto, retlw, return e retfie são utilizadas em desvios incondicionais.
Tabela 3.1: Conjunto de instruções do PIC 16F84
Mnemonic
Operands
ADDWF f,d
ANDWF f,d
CLRF f
CLRW COMF f,d
DECF f,d
DECFSZ f,d
INCF f,d
INCFSZ f,d
IORWF f,d
MOVF f,d
MOVWF f
NOP RLF f,d
RRF f,d
SUBWF f,d
SWAPF f,d
XORWF f,d
BCF f,b
BSF f,b
BTFSC f,b
BTFSS f,b
ADDWF f,d
ANDWF f,d
CLRF f
CLRW COMF f,d
DECF f,d
DECFSZ f,d
INCF f,d
INCFSZ f,d
IORWF f,d
MOVF f,d
MOVWF f
NOP RLF f,d
RRF f,d
SUBWF f,d
SWAPF f,d
XORWF f,d
Description
Cycles
14-Bit Opcode
MSb
LSb
BYTE-ORIENTED FILE REGISTER OPERATIONS
Add W and f
1
00 0111 dfff ffff
AND W with f
1
00 0101 dfff ffff
Clear f
1
00 0001 1fff ffff
Clear W
1
00 0001 0xxx xxxx
Complement f
1
00 1001 dfff ffff
Decrement f
1
00 0011 dfff ffff
Decrement f, Skip if 0
1(2)
00 1011 dfff ffff
Increment f
1
00 1010 dfff ffff
Increment f, Skip if 0
1(2)
00 1111 dfff ffff
Inclusive OR W with f
1
00 0100 dfff ffff
Move f
1
00 1000 dfff ffff
Move W to f
1
00 0000 1fff ffff
No Operation
1
00 0000 0xx0 0000
Rotate Left f through Carry
1
00 1101 dfff ffff
Rotate Right f through Carry
1
00 1100 dfff ffff
Subtract W from f
1
00 0010 dfff ffff
Swap nibbles in f
1
00 1110 dfff ffff
Exclusive OR W with f
1
00 0110 dfff ffff
BIT-ORIENTED FILE REGISTER OPERATIONS
Bit Clear f
1
01 00bb bfff ffff
Bit Set f
1
01 01bb bfff ffff
Bit Test f, Skip if Clear
1(2)
01 10bb bfff ffff
Bit Test f, Skip if Set
1(2)
01 11bb bfff ffff
LITERAL AND CONTROL OPERATIONS
Add W and f
1
00 0111 dfff ffff
AND W with f
1
00 0101 dfff ffff
Clear f
1
00 0001 1fff ffff
Clear W
1
00 0001 0xxx xxxx
Complement f
1
00 1001 dfff ffff
Decrement f
1
00 0011 dfff ffff
Decrement f, Skip if 0
1(2)
00 1011 dfff ffff
Increment f
1
00 1010 dfff ffff
Increment f, Skip if 0
1(2)
00 1111 dfff ffff
Inclusive OR W with f
1
00 0100 dfff ffff
Move f
1
00 1000 dfff ffff
Move W to f
1
00 0000 1fff ffff
No Operation
1
00 0000 0xx0 0000
Rotate Left f through Carry
1
00 1101 dfff ffff
Rotate Right f through Carry
1
00 1100 dfff ffff
Subtract W from f
1
00 0010 dfff ffff
Swap nibbles in f
1
00 1110 dfff ffff
Exclusive OR W with f
1
00 0110 dfff ffff
Status
Affected
C,DC,Z
Z
Z
Z
Z
Z
Z
Z
Z
C
C
C,DC,Z
Z
C,DC,Z
Z
Z
Z
Z
Z
Z
Z
Z
C
C
C,DC,Z
Z
Todas as instruções do PIC têm um tamanho fixo de 14 bits e a palavra de dados
é composta de 8 bits. Com exceção das instruções de desvio, que gastam dois ciclos de
clock, todas as instruções restantes consomem um único ciclo de clock. A coluna Status
34
Affected, presente na Tabela 3.1, representa os bits do registrador STATUS que são
afetados após a execução de uma instrução. O Capı́tulo 6 detalha a influência de cada
instrução na implementação do gerador de montadores.
3.2 Caracterı́sticas gerais e peculiaridades do PIC 16F84
A Figura 3.1(adaptada da original [Inc04b]) apresenta o diagrama da organização do
PIC 16F84. As organizações de memória e de registradores são detalhadas em subseções.
Figura 3.1: Diagrama da organização do PIC 16F84
3.2.1 Organização de memória
O PIC 16F84 possui memória de programa interna com tamanho de 1024 bytes, e a
memória de dados têm capacidade de armazenar até 68 bytes, possibilitando expansão. A
memória EEPROM, que é mapeada indiretamente na memória de dados, pode armazenar
35
até 64 bytes. A Figura 3.2 mostra esta organização.
Figura 3.2: Organização de memória do PIC 16F84
O Program Counter (PC) é um registrador de 13 bits, manipulado automaticamente
pelo hardware do microcontrolador. Está disponı́vel uma pilha de 8 nı́veis implementada em hardware, a qual é manipulada diretamente pelo hardware após a execução das
instruções de desvio call, return, retfie e retlw. O PIC 16F84 possui quatro fontes de interrupções, que são ativadas por recursos internos ou externos ao chip, como por exemplo,
timers, operações de entrada/saı́da e escrita de dados na memória EEPROM. Os vetores
de interrupção e de reset estão localizados em endereços fixos no espaço de memória do
usuário.
3.2.2 Banco de registradores
O PIC possui 15 registradores de uso especı́fico (SFRs), os quais são mapeados em
memória e possuem endereços fixos. Por exemplo, o registrador PC localiza-se entre os
SFRs. Nas instruções de desvio, o endereçamento direto é realizado a partir do Registrador
de Instruções (IR) e o endereçamento indireto é auxiliado pelo registrador especı́fico FSR.
Maiores detalhes podem ser encontrados no manual do microcontrolador [Inc04b].
36
A Figura 3.3 exibe o banco de registradores do PIC.
Figura 3.3: Registradores especı́ficos do PIC 16F84
A funcionalidade de cada registrador mostrado na Figura 3.3 é resumida na Tabela 3.2.
Tabela 3.2: Funcionalidades dos registradores especiais do PIC 16F84
Registrador especı́fico
Funcionalidade
OPTION e TMR0
controle de timers
PCL
byte menos significativo do PC
STATUS
registro de operações da ALU
FSR
endereçamento indireto
PORTA, PORTB, TRISA, TRISB
destinados à operações de I/O
EEDATA, EEADR, EECON1,
manipulação de dados na
EECON2
memória EEPROM
PCLATH
5 bits mais significativos do PC
INTCON
controle de interrupções
37
3.3
Descrição funcional em ArchC
A Figura 3.4 mostra um exemplo da descrição funcional do modelo do microcontrolador
PIC 16F84, desenvolvido no âmbito desta dissertação. Como a descrição da arquitetura
do conjunto de instruções do PIC é extensa, a figura apresenta uma versão condensada
da descrição original.
Figura 3.4: Descrição ArchC de uma versão condensada do PIC 16F84
38
A descrição mostrada na Figura 3.4 consiste essencialmente em quatro seções, que
descrevem diferentes aspectos da arquitetura do conjunto de instruções. A descrição
possui declarações de quatro diferentes formatos: Format Byte, Format Bit, Format Literal e Format Control, mostrados na Seção 1. Na Seção 2 ocorre a associação de cada
instrução com seu devido formato.
Visando a definição de caracterı́sticas sobre modos de endereçamento das instruções
de desvio, foram especificadas duas palavras reservadas: ac addr mode A (modo de
endereçamento absoluto) e ac addr mode R (modo de endereçamento relativo). Através
da Seção 3, associa-se cada instrução de desvio ao seu respectivo modo de endereçamento.
Além disso, é definido o campo do formato da instrução de desvio que possui os bits
referentes ao endereço, cuja informação é necessária para a geração de ferramentas de
software básico. Nesta dissertação, especificamente, são utilizadas para a geração de
montadores e pré-processadores.
As declarações contidas na Seção 3 não estão definidas na gramática da linguagem ArchC, e portanto, devem ser comentadas com “//” antes da geração do simulador (modelo
executável) a partir desta descrição.
Na Seção 4, denominada ISA CTOR (construtor), é definida a sintaxe assembly de
cada instrução, bem como os códigos operacionais.
3.4 Validação experimental do modelo
a) Configuração experimental
Para a geração do simulador, utilizou-se a ADL ArchC, versão 0.8.2. O compilador
PIC usado denomina-se PCWr (PIC C Compiler [Inc04a]), versão 3.182, com IDE versão
3.41. Os códigos assembly gerados pelo PCW foram submetidos a um montador gerado
automaticamente (Seção 6.3).
b) Procedimentos experimentais
Inicialmente, as instruções descritas no modelo funcional do PIC 16F84 foram testadas e depuradas individualmente, por meio de expressões lógico-aritméticas. Deficiências
encontradas foram imediatamente corrigidas. Testes mais avançados foram realizados
39
utilizando pequenos programas escritos em assembly. Posteriormente, experimentos envolvendo programas mais complexos foram amparados pelo compilador PCW (CCS) e
pelo montador do PIC 16F84 gerado automaticamente (a ser descrito no Capı́tulo 6).
Alguns exemplos são os programas envolvendo chamadas de rotinas e o algoritmo de
ordenação Sort.
Paralelamente, realizou-se um experimento usando o exemplo Belt-controller [Wol00].
Como o modelo do PIC não possui funcionalidades de entrada e saı́da, os estı́mulos necessários para simular o exemplo foram inseridos juntamente com o código do programa.
Em seguida, uma validação mais ampla foi realizada através de experimentos baseados
em benchmarks extraı́dos do Projeto Dalton [Pro04], cujos dados serão apresentados ainda
nesta seção. O conjunto de benchmarks escolhido permitiu exercitar operações freqüentes
em software embarcado, tais como operações básicas sobre inteiros, emulação de ponto
flutuante, conversões de tipo e operações sobre ponteiros. Além disso, foram testadas
e validadas caracterı́sticas peculiares do PIC, tais como registradores de uso especı́fico
e endereçamento indireto de memória. Os resultados esperados foram atingidos para
todos os benchmarks testados e desta forma, o modelo funcional ArchC do PIC 16F84 foi
validado.
Os tempos de simulação dos benchmarks foram obtidos através de estatı́sticas geradas
a partir do conjunto de ferramentas do pacote ArchC, que são expressos em unidades de
tempo de SystemC (default time units).
c) Resultados experimentais
Foi realizada uma comparação do modelo do PIC 16F84 com um modelo do microcontrolador i8051, já certificado e disponı́vel no repositório do BrazilIP [Net04]. Os resultados
experimentais quantitativos a seguir apresentados foram gerados usando o já citado conjunto de benchmarks do Projeto Dalton, utilizado na certificação daquele modelo. Para
cada benchmark, a Tabela 3.3 compara os dois microcontroladores em termos de número
de instruções executadas, tempo de simulação e tamanho de código.
Note que o número de instruções executadas para o PIC é bastante menor. Isto é
um indı́cio de que o compilador usado para o i8051 provavelmente tem deficiências na
otimização do código.
40
Tabela 3.3: Caracterı́sticas dos benchmarks utilizados
Benchmark
Instruções
Tempo de
Tamanho de
executadas
simulação1
código (bytes)
PIC
i8051
PIC
i8051
PIC
i8051
negcnt
150
312
2981
6221
60
33
int2bin
256
2659
5101
53161
72
55
cast
68
995
1341
19881
120
112
divmul
296
404
5901
8061
212
190
fib
358
1218
7141
24341
140
298
sort
2227
4245
44521
84881
220
534
Os dados referentes ao tamanho de código (Tabela 3.3) são colocados em evidência na
Figura 3.5.
Figura 3.5: Tamanho de código: PIC 16F84 x i8051
Note que o tamanho do código gerado para o PIC é maior para a maioria dos benchmarks. Isto se deve ao fato de o PIC utilizar um formato fixo de instrução. Entretanto,
os programas fib e sort apresentam um comportamento distinto, que reflete o fato de
o PIC possuir recursos especı́ficos para a manipulação de vetores (estrutura de dados
predominante nestes dois programas).
1
Expresso em unidade de tempo de SystemC (default time unit).
41
Deve-se fazer a ressalva de que os testes foram realizados utilizando-se compiladores
comerciais de diferentes fabricantes e que, portanto, possı́veis diferenças de técnicas de
otimização e geração de código podem estar embutidas nos valores medidos.
A Figura 3.6 mostra os tempos de simulação2 extraı́dos da Tabela 3.3. Note que os
tempos de simulação para o modelo do PIC 16F84 são menores para todos os programas
testados. Por exemplo, o programa sort executou aproximadamente 2 vezes mais rápido
que no i8051. No caso do programa cast, o modelo do PIC 16F84 executa aproximadamente 15 vezes mais rápido.
Figura 3.6: Tempo de simulação: PIC 16F84 x i8051
Obviamente, os tempos de simulação maiores explicam-se pelo maior número de instruções executadas e, possivelmente, pela maior complexidade do conjunto de instruções
(por exemplo, formato variável) do i8051.
Experimentos utilizando programas mais complexos, principalmente envolvendo buffers de memória não foram realizados devido a limitações do compilador, pois seria necessário integrar ao modelo um módulo de memória externa para realizar tais experimentos. Os dados de saı́da obtidos nos experimentos com os benchmarks coincidem com os
encontrados no Projeto Dalton [Pro04], justificando, desta forma, a validação do modelo
funcional do PIC 16F84.
2
Expressos em unidades de tempo de SystemC (default time units).
42
Capı́tulo 4
A metodologia baseada em ADL
O trabalho de pesquisa descrito nesta dissertação é parte de uma metodologia de
suporte ao uso de ASIPs em SoCs. Este capı́tulo descreve as etapas da metodologia
abordadas nesta dissertação, as que são abordadas em trabalhos correlatos e as que se
pretende suportar em trabalhos futuros.
4.1
Visão geral da metodologia
A Figura 4.1 representa esquematicamente a metodologia adotada, na qual existem 3
fluxos distintos:
• Sı́ntese de HW
• Co-simulação HW/SW
• Sı́ntese de SW
A sı́ntese de hardware inicia-se a partir de uma descrição ADL. Esta descrição é
submetida a uma cadeia de ferramentas de sı́ntese que resulta em uma descrição em HDL
do ASIP. Posteriormente, o hardware descrito pode ser sintetizado em uma plataforma
FPGA. Este fluxo será abordado em futuros trabalhos de pesquisa.
No fluxo da co-simulação hardware-software, é possı́vel gerar simuladores automaticamente a partir da descrição ADL de entrada. Este fluxo é suportado por ferramentas já
disponı́veis no pacote ArchC.
Já no fluxo da sı́ntese de software (foco desta dissertação), códigos-fonte escritos em
C++ são compilados, gerando código assembly como saı́da. Este código é então subme43
tido ao montador para a geração de um arquivo executável, que pode ser executado no
simulador ou no hardware sintetizado (por exemplo, numa plataforma FPGA).
Note que o montador é parametrizável de acordo com a descrição ADL da arquitetura
de um ASIP. Alterações ou extensões na arquitetura são refletidas no código executável
gerado.
Figura 4.1: A metodologia de projeto adotada
Esta dissertação aborda parte do fluxo da sı́ntese de software mostrado na Figura 4.1,
destacado pelas linhas espessas. Detalhes deste fluxo são apresentados na próxima seção.
44
4.2
Uma visão geral do montador parametrizável
A Figura 4.2 expande o bloco denominado montador parametrizável na Figura 4.1,
mostrando somente a parte do fluxo de sı́ntese de software abordado nesta dissertação.
Figura 4.2: O montador parametrizável
A descrição ADL mostrada na Figura 4.2 é o ponto de partida para o gerador de
montadores e para o gerador de pré-processadores. Em particular, o gerador de préprocessadores necessita de informações sobre modos de endereçamento, macros e pseudoinstruções, todas descritas em um arquivo de configuração.
O código assembly utilizado como entrada do pré-processador pode conter macros,
pseudo-instruções e labels. Durante o pré-processamento, as macros são expandidas e as
pseudo-instruções são substituı́das por instruções nativas. Além disso, todos os endereços
simbólicos são resolvidos e substituı́dos por endereços numéricos, gerando como saı́da
código assembly nativo. Este código pré-processado é submetido ao montador, cuja tarefa
principal resume-se em ler cada linha do programa assembly e realizar a montagem. O
código montado (executável no formato hexadecimal) pode ser executado no simulador,
conforme o fluxo da co-simulação hardware-software (Figura 4.1).
A geração automática de ferramentas (pré-processador e montador) ampara-se em
técnicas formais baseadas em Gramática Livre de Contexto (GLC). Estas técnicas serão
abordadas no Capı́tulo 5. A implementação das ferramentas de geração automática é
apresentada no Capı́tulo 6.
45
Capı́tulo 5
O uso de gramáticas na geração
automática de ferramentas
A geração automática de ferramentas ampara-se na construção de parsers, os quais
utilizam Gramáticas Livre de Contexto (GLCs) para a representação formal da sintaxe
da linguagem de entrada. Este capı́tulo apresenta a definição formal de GLCs e define os
principais conceitos da teoria das Linguagens Formais relacionados com gramáticas.
O capı́tulo termina com a proposta de um algoritmo para a geração automática de
GLCs, que é um dos elementos-chave para a geração automática de ferramentas a partir
de ADLs, a ser descrita no Capı́tulo 6.
5.1 Fundamentação
5.1.1
Alfabeto (ou Vocabulário)
Um Alfabeto é um conjunto finito, não vazio, de sı́mbolos (elementos), geralmente
denotado por V.
Exemplos: V = {a, e, i, o, u}, V = {0, 1}, etc.
5.1.2
Sentença (ou Palavra)
Uma sentença sobre um alfabeto V, é uma seqüência (ou cadeia) finita de sı́mbolos do
alfabeto.
Exemplo de sentenças sobre V = { a , b }: a, b, aa, ab, ba, bb, aaa, ...
46
5.1.3 Fechamento (closure) de um alfabeto
Seja V um alfabeto ∀.
O fechamento reflexivo (ou simplesmente fechamento) de V, representado por V∗ ,
é dado pelo conjunto de todas as possı́veis seqüências que podem ser formadas a partir
de V, inclusive a sentença vazia ().
O fechamento transitivo (ou fechamento positivo) de V, representado por V+ , é
dado por V∗ - {}.
Exemplos: Seja V = { 0, 1 }, temos que:
V∗ = {, 0, 1, 00, 01, 10, 11, 000, ...}
V+ = {0, 1, 00 ,01, 10, 11, 000, ...}
5.1.4 Linguagem
Uma linguagem L é um conjunto ou subconjunto das possı́veis sentenças que podem
ser escritas a partir de um alfabeto. Ou seja, L ⊆ V∗ .
5.1.5 Gramática
Informalmente, uma gramática pode ser definida como sendo um sistema gerador de
linguagens, ou ainda, um dispositivo formal usado para especificar, de maneira finita e
precisa, uma linguagem potencialmente infinita. Ou seja, uma gramática define qual
subconjunto de V∗ forma uma linguagem.
Segundo a hierarquia de CHOMSKY [Aea88], as gramáticas são classificadas em:
• Gramática Tipo 0 (ou gramática sem restrições)
• Gramática Tipo 1 (ou Gramática Sensı́vel ao Contexto - GSC)
• Gramática Tipo 2 (ou Gramática Livre de Contexto - GLC)
• Gramática Tipo 3 (ou Gramática Regular - GR)
As linguagens geradas por GSC, GLC e GR são denominadas, respectivamente, Linguagens Sensı́veis ao Contexto (LSC), Linguagens Livres de Contexto (LLC) e Linguagens
Regulares (LR).
47
5.1.6 Gramática Livre de Contexto (GLC)
Dentre os quatro tipos de gramáticas de CHOMSKY, as gramáticas livre de contexto
são as mais adequadas para especificação dos aspectos sintáticos de uma linguagem e
constituem a base formal para a implementação de parsers.
Formalmente, uma GLC é definida por G = (Vn, Vt, P, S), onde:
• Vn: Conjunto finito de sı́mbolos não-terminais, os quais são utilizados na descrição da linguagem.
• Vt: Conjunto finito de sı́mbolos terminais, os quais são usados na formação das
sentenças da linguagem, sendo que Vn ∩ Vt = φ.
• P: Conjunto finito das produções (regras gramaticais ou regras de sintaxe), onde
cada produção é composta por um par (A, β), denotado por A ::= β, onde:
P= {A ::= β | A ∈ Vn ∧ β ∈ (Vn ∪ Vt)∗ }
• S: Pertence a Vn e é o sı́mbolo inicial da gramática, ou seja, o sı́mbolo a partir
do qual as sentenças de uma linguagem são geradas.
A linguagem gerada por uma GLC G = (Vn, Vt, P, S), denotada por L(G), é definida
pelo conjunto de sentenças (seqüências pertencentes a Vt∗ ) que podem ser produzidas a
partir do sı́mbolo inicial (S), de acordo com as regras sintáticas contidas em P. Formalmente, L(G) = {x | x ∈ Vt∗ ∧ S =⇒+ x }.
Os sı́mbolos terminais (Vt) de uma gramática constituem a especificação léxica da
linguagem gerada a partir dela. Esta especificação léxica pode ser representada formalmente através de diversos mecanismos, tais como autômatos finitos, gramáticas regulares
e expressões regulares.
A validação dos sı́mbolos terminais (tokens) é realizada por um algoritmo (programa),
denominado analisador léxico, o qual pode ser gerado automaticamente a partir da
especificação formal dos aspectos léxicos de uma linguagem.
A validação das sentenças de uma linguagem é realizada por um algoritmo (programa),
denominado analisador sintático (parser ), o qual pode ser gerado automaticamente
a partir da especificação formal dos aspectos sintáticos de uma linguagem (geralmente
através de GLCs).
48
5.1.7 Gramática livre de contexto LL(1)
Uma gramática livre de contexto é dita LL(1) [Aea88] se, e somente se:
• Não possui recursões à esquerda.
• Está fatorada.
• Para todo não-terminal que deriva a sentença vazia, a intersecção dos conjuntos
first [Aea88] e follow [Aea88] desse não-terminal é vazia.
5.1.8
Geradores de analisadores léxico e sintático
Os geradores de analisadores léxico e sintático são ferramentas que, a partir de uma
especificação formal dos aspectos léxicos e sintáticos de uma linguagem, geram automaticamente os programas (reconhecedores) que efetuam a análise léxica e sintática dos programas escritos nesta linguagem. O código produzido a partir destes geradores é baseado
em algoritmos (técnicas) já consolidados na literatura [Aea88].
Dentre os geradores mais conhecidos e utilizados, encontram-se o Lex (gerador de
analisadores léxico) [LEX04] e o Yacc (gerador de analisadores sintático) [YAC04]. Ferramentas similares foram desenvolvidas utilizando diferentes técnicas de análise léxica
e sintática e/ou visando diferentes objetivos. Entre estas estão o BISON [Com04], o
GAS [GNU04] e o GALS [Ges04].
Nesta dissertação, foi adotado o GALS, um gerador de analisadores léxico e sintático
desenvolvido na Universidade Federal de Santa Catarina, o qual permite a especificação
unificada dos aspectos léxicos e sintáticos de uma linguagem. O GALS gera analisadores
sintáticos segundo as principais técnicas de análise sintática existentes [Aea88], incluindo
LALR(1) (utilizada pelo Yacc), SLR(1), LR(1) e preditiva LL(1).
Uma das mais importantes caracterı́sticas do GALS é a disponibilidade de um simulador para a co-validação entre linguagem e gramática, bem como mecanismos de depuração
para expressões regulares. Tais caracterı́sticas facilitam e flexibilizam a especificação léxica
e sintática de uma linguagem, e conseqüentemente, a geração de seus analisadores.
No GALS, a especificação léxica é baseada no formalismo de expressões regulares,
conforme exemplo a seguir. A Figura 5.1 apresenta as definições regulares utilizadas na
especificação dos tokens (sı́mbolos básicos da linguagem).
49
Figura 5.1: Definições regulares
Na Figura 5.1, L corresponde à definição de qualquer letra maiúscula ou minúscula
no intervalo de A (a) até Z (z). D define qualquer dı́gito de 0 até 9. A definição S
representa o sinal positivo ou negativo que pode ser usado antes de um dı́gito (D). Em
WS (white space) são definidos os sı́mbolos a ignorar, como por exemplo, espaço em
branco, tabulação, final de linha e retorno. COMMENT define a formação léxica de um
comentário.
A Figura 5.2 exemplifica a definição de alguns tokens de acordo com a especificação da
Figura 5.1. O token LABEL é formado por qualquer combinação de caracteres (exceto
aqueles definidos em WS) cujo último caractere seja “:”. Um ID (identificador) deve ser
formado, no mı́nimo, por uma letra (L), que pode ser seguida de outros caracteres, com
as mesmas exceções descritas em LABEL. O token VALUE representa valores decimais
(com ou sem sinal) ou valores no formato hexadecimal.
Figura 5.2: Definição de tokens
A definição :{WS}* especifica que toda a ocorrência caracteres contidos em WS (Figura 5.1) será ignorada. Já a definição :!{COMMENT} possui a funcionalidade reconhecer um comentário. Note que as duas últimas definições não possuem nome associado,
o que indica que as mesmas não possuem valor sintático.
Nesta seção foi exemplificado o uso do GALS para a especificação léxica de uma
linguagem. No Capı́tulo 6, será exemplificada uma especificação sintática (Seção 6.1.3).
50
5.2
Vantagens do uso de GLCs
A geração automática de ferramentas baseada em gramática livre de contexto traz
vários benefı́cios, tais como:
• Expressividade: uma GLC possui expressividade suficiente para especificação formal dos aspectos sintáticos de uma linguagem, constituindo-se, portanto, em uma
base formal para a realização do processo de análise sintática.
• Generalização: através de uma gramática, é possı́vel generalizar o processo de
reconhecimento de programas. Por exemplo, a geração de montadores pode ser
viabilizada para diferentes arquiteturas.
• Robustez e corretude: nesta dissertação, em particular, a principal vantagem
do uso de gramáticas é a garantia de corretude do parser gerado, possibilitando a
validação de todos os programas de entrada corretamente definidos e a invalidação
de todos os programas incorretos.
• Flexibilidade e extensibilidade: a utilização de técnicas formais na especificação
de linguagens facilita a extensão e alteração da linguagem e do parser gerado,
constituindo-se um método mais rápido e seguro em relação aos métodos de extensão desprovidos de formalização.
5.3
O uso de GLC para a geração de montadores
5.3.1 Gramáticas envolvidas
Na técnica de geração automática de montadores adotada nesta dissertação, duas
GLCs são necessárias:
• Gramática da ADL: é manualmente definida para uma dada versão da ADL. Esta
GLC é submetida ao GALS para a geração automática do parser da descrição ADL.
• Gramática do montador: é produzida automaticamente pelo gerador de montadores, sendo a entrada do GALS para a geração automática do parser do montador.
O parser gerado está baseado nas definições léxicas e sintáticas da linguagem assembly da arquitetura descrita na ADL.
51
Na geração dos parsers é utilizada a técnica de análise sintática LL(1), a qual possibilita a análise formal, descendente e determinı́stica dos programas escritos na linguagem
representada pelas gramáticas.
5.3.2 Geração automática da gramática do montador
Nesta seção, apresenta-se um algoritmo para geração de uma GLC LL(1) G = (Vn,
Vt, P, S), que representa a linguagem assembly da arquitetura especificada na ADL.
A GLC gerada é garantidamente uma GLC LL(1), uma vez que apresenta as seguintes
caracterı́sticas:
• O primeiro sı́mbolo do lado direito de cada produção da gramática é sempre um
sı́mbolo terminal (Vt), mais especificamente, o mnemônico da instrução. Isto implica que G não possui recursões à esquerda.
• Todos os sı́mbolos terminais que iniciam as produções de G são distintos entre si, e
portanto, G está fatorada.
• O único sı́mbolo não-terminal da gramática gerada que deriva é o seu sı́mbolo
inicial (<lista instr>), para o qual a intersecção dos conjuntos first e follow é vazia.
O Algoritmo 5.1 utiliza como entrada um conjunto de estruturas de dados contendo
as informações da arquitetura do conjunto de instruções da CPU descrita. Tais estruturas
são construı́das por 17 ações semânticas embutidas na gramática da ADL. Um exemplo
de gramática será apresentado no próximo capı́tulo (Figura 6.3).
Dentre as informações presentes na estrutura de dados da entrada, o algoritmo utiliza
o nome, o mnemônico e a lista de operandos (com seus separadores) de cada instrução.
O algoritmo define o sı́mbolo inicial (S), os sı́mbolos não-terminais (Vn), os sı́mbolos
terminais (Vt) e as regras de sintaxe (P) da gramática. Novas palavras reservadas da
linguagem constituem novos sı́mbolos terminais da gramática e são definidos como um
caso especial do token ID (veja a Figura 5.2).
No passo 1, é realizada a inicialização dos elementos padrão da GLC, tais como
sı́mbolos não-terminais, sı́mbolos terminais (tokens) e sı́mbolo inicial (com suas respectivas produções). A ação semântica #1 é utilizada no controle de labels.
52
Algoritmo 5.1 - Algoritmo de geração de GLC
Objetivo: Gerar uma GLC G = {Vn, Vt, P, S} que represente a linguagem assembly
da arquitetura especificada na ADL.
Entrada: Estrutura de dados Lista Instruções, contendo o nome de cada instrução,
seu mnemônico e uma lista operandos (com operandos e seus separadores).
Saı́da: GLC G = {Vn, Vt, P, S} representando a linguagem assembly da arquitetura
especificada na ADL.
Método:
Passo 1. Inicialização padrão dos elementos de G.
Vn = {<lista instr>, <instr>}
Vt = {LABEL, ID, VALUE}
P = {<lista instr>::=LABEL #1 <instr> <lista instr> | <instr> <lista instr> | }
S = <lista instr>
Passo 2. Definição dos elementos de G dependentes da Lista Instruções.
Para cada elemento da Lista Instruções faça
Inı́cio
Vn = Vn ∪ {<Lista Instruções.nome>}
Vt = Vt ∪ {Lista Instruções.mnemônico}
α = Concatena (Lista Instruções.mnemônico, “#3”)
Se (Lista Instruções.lista operandos == φ)
então α = Concatena (α, “#4”)
Senão
Para cada operando da Lista Instruções.lista operandos faça
Inı́cio
α = Concatena (α , Concatena (VALUE, “#2”))
Se operando for o último da Lista Instruções.lista operandos
então α = Concatena (α, “#4”)
Senão
Inı́cio
α = Concatena (α, Lista Instruções.lista operandos.separador)
Vt = Vt ∪ {Lista Instruções.lista operandos.separador}
Fim
Fim
P = P ∪ {<instr>::=<Lista Instruções.nome>, <Lista Instruções.nome>::=α}
Fim
53
No passo 2, são definidos os elementos de G dependentes diretamente da descrição
da arquitetura na ADL, representados pelo componente Lista Instruções. Neste passo,
ocorre a geração de um sı́mbolo não-terminal para cada instrução definida na ADL, o qual
passa a fazer parte do conjunto Vn. Em seguida, o mnemônico da instrução passa a ser
um elemento do conjunto Vt, tornando-se uma palavra reservada da linguagem.
O sı́mbolo α denota uma cadeia que estabelece a sintaxe de uma instrução. Esta cadeia
é composta pelo mnemônico da instrução e, opcionalmente, por um ou mais operandos.
Cada operando é representado pelo token VALUE, seguido da ação semântica #3. Nas
instruções com dois ou mais operandos, os separadores destes operandos são inseridos no
conjunto Vt, tornando-se sı́mbolos reservados da linguagem.
Finalmente, são introduzidas novas produções em P, representando as instruções definidas na ADL. A ação semântica #2 realiza verificações nos operandos de cada instrução
e a ação #3 realiza verificações sobre os mnemônicos. A ação semântica #4 finaliza o reconhecimento de uma instrução, acionando a geração de código. O epsilon () representa
uma sentença vazia. Um exemplo de uma GLC gerada a partir do Algoritmo 5.1 será
mostrado no próximo capı́tulo (Figura 6.2).
54
Capı́tulo 6
Geração automática de ferramentas
Este capı́tulo descreve as técnicas utilizadas para implementar o montador parametrizável cuja estrutura foi apresentada no Capı́tulo 4. A Seção 6.1 aborda a geração
automática de montadores, enquanto a Seção 6.2 aborda a geração automática de préprocessadores. Ao final, são apresentados os resultados dos experimentos realizados para
validar e avaliar a eficiência, tanto das ferramentas geradoras quanto das geradas.
6.1 A geração automática de montadores
6.1.1
O fluxo de geração
O fluxo de geração automática de um montador, mostrado na Figura 6.1, consiste das
seguintes etapas:
• Geração do parser da ADL
• Parsing da ADL
• Geração da lista de instruções
• Geração da GLC para a linguagem assembly
• Geração do parser do código assembly
• Compilação do montador
55
Figura 6.1: O fluxo da geração de montadores
O GALS [Ges04] é a chave para a geração automática do analisador léxico e sintático
para a descrição ADL do conjunto de instruções, bem como para a linguagem assembly.
Portanto, o GALS é utilizado na primeira e na quinta etapas.
A primeira etapa é realizada pelo GALS a partir da definição da gramática da ADL,
gerando automaticamente o analisador léxico e o parser da descrição ADL. Na segunda
etapa é realizado o parsing da descrição ADL, o qual extrai as informações da arquitetura
do conjunto de instruções e armazena-as em estruturas de dados. Na etapa seguinte,
funções especializadas extraem os dados destas estruturas e geram uma lista de instruções.
56
O Algoritmo 5.1 (detalhado na Seção 5.3.2) realiza a quarta etapa, extraindo informações
das estruturas de dados. Na quinta etapa, a GLC gerada pelo algoritmo é submetida ao
GALS, o qual constrói automaticamente o parser da linguagem assembly representada
pela gramática. Na última etapa, a lista de instruções, o analisador léxico, o parser do
código assembly, algumas classes auxiliares e o analisador semântico são todos compilados,
resultando na geração do montador da arquitetura especificada na descrição ADL.
6.1.2
Exemplo de geração de uma GLC
As informações usadas na geração de montadores mostradas na Figura 6.1 são exibidas
em nı́vel de código na Figura 6.2, a qual é estruturada da seguinte maneira:
• Descrição de uma CPU (descrição ArchC)
• Lista de instruções (código em C++)
• GLC (notação Backus-Naur Form (BNF))
O exemplo mostrado na Figura 6.2 reflete a lista de instruções e a GLC geradas
a partir da mesma descrição ArchC. Neste exemplo, a descrição é composta de único
formato (Format Byte) e única instrução (ADDWF) do microcontrolador PIC 16F84.
A lista de instruções é gerada a partir de funções que extraem dados das estruturas.
Observe que esta lista armazena informações obtidas da ADL, tais como nome do formato
(Format Byte), campos do formato (dummy, op byte, d, f), nome da instrução (ADDWF)
e sintaxe assembly (ADDWF %f, %d).
A gramática é gerada pela aplicação do Algoritmo 5.1 a partir dos dados obtidos
da descrição ADL. A primeira linha da descrição da gramática é padrão para qualquer
descrição ADL. Na segunda linha, o sı́mbolo não-terminal <ADDWF>, corresponde à instrução ADDWF definida na ADL. Na linha seguinte, observe que a produção da gramática
possui um mnemônico (ADDWF), operandos (VALUE) e ações semânticas (formadas pelo
par (#, número)).
Note que o trecho de código mostrado na lista de instruções é código pronto para
ser compilado. Já a GLC deve ser submetida ao GALS para a geração do código C++
correspondentes ao parser do montador.
57
Figura 6.2: Exemplo de geração de GLC e lista de instruções
58
6.1.3 Implementação
Para o desenvolvimento do software, foi utilizada a seguinte plataforma:
• Microcomputador PC
• Sistema operacional Microsoft Windows
• Ambiente de desenvolvimento Borland Builder
• Linguagem de programação C++
O código fonte das ferramentas geradoras e geradas foi escrito em C++ padrão. Desta
forma, o código é totalmente portável para o sistema operacional Linux e pode ser facilmente compilado pelo g++ da GNU [GNU04] sem necessidade de alterações.
As classes geradas automaticamente são:
• Lista de instruções: esta lista é gerada automaticamente pelo gerador de montadores e está armazenada no arquivo ListaInstrucoes.cpp. Na lista de instruções
encontram-se todas as informações da arquitetura especificada em ArchC necessárias
para geração de um montador.
• Tabela de sı́mbolos: esta estrutura é gerada automaticamente pelo GALS a partir
da GLC da linguagem assembly. Nesta tabela estão inseridas as informações léxicas
e sintáticas extraı́das da GLC. O conteúdo da tabela de sı́mbolos é armazenado nos
arquivos Constants.h e Constants.cpp.
As classes construı́das manualmente são:
• Classes auxiliares: estas classes possuem funções de manipulação dos dados extraı́dos da ADL e as rotinas responsáveis pela geração de arquivos contendo o códigofonte que farão parte do montador.
• Analisador semântico: nestas classes estão codificadas as ações semânticas do
montador. Devido a generalização das ações semânticas, um montador gerado a partir de qualquer descrição ArchC incorpora sempre um mesmo analisador semântico.
Estas classes estão armazenadas nos arquivos Semantico.h e Semantico.cpp.
59
Os arquivos que contêm as rotinas e classes descritas formam o código-fonte completo
do novo montador. Após a compilação destes arquivos, é gerado um montador automaticamente. Este processo é auxiliado por um script.
Alguns detalhes de implementação do fluxo de geração de montadores são apresentados
a seguir:
a) Geração do parser da ADL: como base para a geração do parser da ADL, foi
definida uma GLC com padrão BNF, a qual é apresentada na Figura 6.3.
Figura 6.3: Gramática completa de uma descrição AC ISA em ArchC
Nesta gramática, alguns componentes representam palavras reservadas da ADL ArchC, tais como: AC ISA, ac format, ac instr, ISA CTOR, set asm e set decoder, como
exemplificado na Seção 3.3. As palavras ac addr mode A e ac addr mode R são utilizadas
apenas para a geração de montadores e pré-processadores e, portanto, não fazem parte da
ADL. Os sı́mbolos ID e ı̂ foram definidos no Capı́tulo 5 e os elementos ASPA, NUM,
HEXA e ASSEMBLY são casos especiais de ID. Os elementos que aparecem entre os
caracteres < e > representam os sı́mbolos não-terminais da gramática. Para finalizar,
cada número precedido do caractere “#” representa uma ação semântica do gerador de
montadores. Estas ações semânticas são utilizadas pelo GALS para a geração parcial do
analisador semântico do gerador de montadores (basicamente esqueletos de classes e de
funções). As ações semânticas foram implementadas manualmente.
60
b) GALS: o GALS foi usado para gerar os analisadores léxico e sintático das descrições
do conjunto de instruções das arquiteturas definidas em ArchC, bem como da linguagem
assembly. Um simulador disponı́vel na interface gráfica do GALS foi utilizado para testes
e verificações da GLC gerada. Este ambiente permitiu simular diferentes descrições ArchC
e programas assembly, subsidiando diretamente a construção dos parsers envolvidos.
Com objetivo de simplificar e acelerar o processo de geração de montadores, o código
fonte do GALS foi modificado. Desta forma, é possı́vel invocar o GALS através de scripts
(disponı́veis para Windows/Linux) sem necessidade de utilização da sua interface gráfica,
mantendo todas as verificações de inconsistências da gramática especificada.
c) Estruturas de dados: as estruturas de dados disponı́veis são manipuladas pelo
analisador semântico do gerador de montadores e contêm os dados definidos na ADL, tais
como:
• Formatos e seus respectivos campos
• Instruções e sua sintaxe assembly (mnemônicos, operandos e separadores de operandos)
• Definição de modos de endereçamento das instruções de desvio
6.1.4
Verificação de inconsistências
Para tornar robusta a geração e o uso do montador, algumas verificações de inconsistências foram implementadas:
• Verificação de sinais: esta função é realizada nos campos dos formatos declarados
em ArchC pelo analisador semântico do montador, garantindo os limites mı́nimos e
máximos de valores dos operandos de cada instrução de um programa assembly;
• Verificação de erros léxicos, sintáticos e semânticos: qualquer erro léxico,
sintático ou semântico provoca o lançamento de suas respectivas exceções, interrompendo imediatamente o processo de montagem. A não interrupção deste processo
denota a correta geração de código.
61
6.2
A geração automática de pré-processadores
6.2.1 O papel do pré-processador
O pré-processamento resume-se em 3 tarefas:
• Substituição de palavras reservadas: os comentários são ignorados e os sı́mbolos
definidos no arquivo de configuração são substituı́dos por valores numéricos.
• Substituição de pseudo-instruções e macros: estes elementos são substituı́dos
por instruções nativas.
• Cálculo de endereços: nesta tarefa é realizada a resolução de labels, calculando
seus endereços numéricos.
O arquivo de saı́da do pré-processador contém somente código assembly nativo e endereços numéricos. Portanto, a função do montador resume-se apenas na montagem do
código previamente processado.
6.2.2 O fluxo de geração
O fluxo de geração automática de um pré-processador, mostrado na Figura 6.4 consiste
das seguintes etapas:
• Parsing do arquivo de configuração
• Geração da classe de tratamento de labels
• Compilação do pré-processador
A primeira etapa a ser realizada é o parsing do arquivo de configuração, que contêm informações sobre palavras reservadas, macros, pseudo-instruções e modos de endereçamento.
A estrutura do arquivo de configuração será detalhada na Seção 6.2.3.
Na segunda etapa, são geradas as rotinas de resolução de labels baseadas nos modos de endereçamento descritos no arquivo de configuração. Estas rotinas são inseridas
seqüencialmente em uma classe C++ que fará parte do código do pré-processador. A estrutura desta classe contendo um exemplo de rotina de resolução de labels será mostrada
na Seção 6.2.3.
62
Figura 6.4: O gerador de pré-processadores
O parser do pré-processador e as rotinas de manipulação de dados (por exemplo, da
lista de instruções) fazem parte de um conjunto de classes denominado Classes Padrão.
Além disso, o pré-processador utiliza a lista de instruções produzida pelo gerador de
montadores. Portanto, a geração do pré-processador ocorrer após a geração do montador
devido à dependência de dados.
Na última etapa, as classes padrão, a classe de tratamento de labels e a lista de
instruções são compiladas, resultando na geração de um novo pré-processador.
6.2.3 Implementação
Para o desenvolvimento do gerador de pré-processadores, foi utilizada a mesma plataforma especificada na Seção 6.1.3. Esta seção fornece detalhes sobre o arquivo de
configuração e a classe de resolução de labels do pré-processador.
a) Arquivo de configuração: um exemplo de um arquivo de configuração do préprocessador é mostrado na Figura 6.5.
63
Figura 6.5: Definições reservadas de uma arquitetura fictı́cia
A Seção AC RESERVED WORDS possui uma lista de definições padrão da arquitetura, como por exemplo, o nome de registradores e recursos da arquitetura. Nesta seção,
é possı́vel declarar um sı́mbolo de comentário e sı́mbolos que devem ser ignorados pelo
parser. Posteriormente, as pseudo-instruções podem ser definidas, associando-as com instruções nativas equivalentes. As macros são formadas por uma lista de instruções nativas.
Peculiaridades das instruções de desvio são descritas na Seção AC ADDRESS GENERATOR, onde o endereço-alvo do desvio é representado por uma expressão aritmética. Tal
expressão representa a distância (em bytes) entre a instrução de desvio e a instrução atual.
A notação j: “x/4” indica que, na montagem da instrução j, o valor a ser representado
em binário no campo de endereço da palavra de instrução é x/4 (ou seja, o endereço
expresso em número de palavras). A informação sobre o caráter absoluto ou relativo do
endereçamento não é capturada no arquivo de configuração, mas indicada na descrição
ArchC através da sentença “ac addr mode A”, que denota endereçamento absoluto.
b) Classe de resolução de labels: nesta classe, denominada AddressGenerator.h,
é inserida uma rotina para cada expressão declarada na Seção AC ADDRESS GENERATOR (Figura 6.5). Através destas rotinas, o pré-processador calcula e substitui labels
pelo seu endereço numérico efetivo. A flexibilidade da declaração destas expressões através
64
de qualquer expressão válida em C++ permite descrever facilmente os modos de desvio
absoluto ou relativo existentes na arquitetura que está sendo descrita. Um exemplo da
classe AddressGenerator.h, contendo a rotina correspondente à definição na Figura 6.5 é
mostrada na Figura 6.6.
Figura 6.6: Exemplo da classe AddressGenerator.h
6.3
Resultados experimentais
Para validar e avaliar a eficiência tanto da ferramentas geradoras quanto das geradas,
foram realizados experimentos conforme descrito a seguir.
a) Configuração dos experimentos
r Pentium
Os experimentos foram realizados em um computador PC com CPU Intel
4, operando à freqüência de 1.8 GHz, com 256 MB de memória principal, sob o sistema
operacional Linux Debian, com kernel versão 2.4.25-1-686.
Embora as ferramentas de geração automática desenvolvidas destinem-se ao suporte
de ASIPs, para fins de validação e sem perda de generalidade, foram utilizadas CPUs de
propósitos gerais bem conhecidas: o MIPS e PowerPC 405. Além destes, foi utilizado o
microcontrolador PIC 16F84.
65
O código produzido pelo montador gerado foi executado no modelo funcional de cada
CPU-alvo, sendo que cada modelo foi gerado a partir de sua descrição ArchC. O modelo do MIPS foi obtido em [Arc04] e os modelos do PIC 16F84 e PowerPC 405 foram
desenvolvidos localmente [Tea05b] [Fea04].
Os programas adotados para validar os geradores foram extraı́dos do conjunto de
benchmarks do Projeto Dalton [Pro04]. Os tempos de execução, expressos em segundos, foram obtidos através do comando time do Linux, somando-se os tempos de CPU
denominados user e system.
A fim de gerar códigos assembly para validar os montadores gerados automaticamente, utilizaram-se os compiladores cruzados gcc [GNU04] (para o MIPS e o PowerPC)
e PCW/CCS [Inc04a] (para o PIC).
b) Procedimentos experimentais
Para cada CPU-alvo Ci , representada através de um modelo Mi descrito em ArchC,
as seguintes ferramentas foram geradas:
• Um simulador do conjunto de instruções Si (gerado pelo pacote ArchC);
• Um montador Ai ;
• Um pré-processador Pi ;
Posteriormente, cada programa benchmark foi compilado para cada CPU-alvo Ci ,
gerando os respectivos códigos assembly. Por sua vez, os códigos assembly de cada benchmark foram submetidos ao pré-processador Pi e ao montador Ai , resultando no código
executável para a CPU-alvo Ci .
c) Resultados experimentais
Os resultados experimentais relativos às ferramentas geradoras são mostrados nas
Tabelas 6.1 e 6.3. Os resultados experimentais referentes às ferramentas geradas são
mostrados nas Tabelas 6.4 e 6.5.
A Tabela 6.1 mostra os tempos1 necessários para gerar os pré-processadores e os montadores. Note que o tempo de geração do montador é dominante sobre o tempo de geração
66
do pré-processador, que pode ser desconsiderado. Como esperado, os tempos de geração
são proporcionais ao tamanho do conjunto de instruções.
Tabela 6.1: Tempos de geração do pré-processador e montador
CPU
Instruções descritas
Pré-processador
Montador
MIPS
58
0,04
1,13
PowerPC
120
0,05
3,44
PIC
35
0,03
1,06
Para investigar a taxa de crescimento do conjunto de instruções, diferentes cores foram
construı́dos, adicionando novas instruções a um subconjunto já existente, de acordo com
o seguinte critério: dado um core Ci , o core Ci+1 contêm todas as instruções do core Ci
adicionando-se 10 novas instruções, conforme mostra a Tabela 6.2.
Tabela 6.2: Seleção de cores
Core
C1
ISA
PowerPC 405
MIPS
instruções
addi, addis, bclr, bl, lbz,
addi, addiu, jal, jr, lbu,
15
lwz, mfspr, or, ori, rlwinm,
lui, lw, ori, sb, sll,
stb, stw, stwu, cmp, cmpl
srl, sw, slti, bne, j
Core 1 +
Core 1 +
add, b, bc, subf, cmpli,
sltu, addu, beq, lb, subu,
sraw, divwu, mullw, sth, stbx
srav, andi, sltiu, lhu, lh
Core 2 +
Core 2 +
and, nego, mtspr, lhz, subfme,
add, mult, div, mfhi, mflo,
bcl, addc, mull, lhaux, divw
jalr, sra, and, or, sllv
Core 3 +
Core 3 +
addme, mcrf, nand, mulhw, oris,
mthi, mtlo, sys call, break,
cmpi, slw, subfe, mfcr, divwo
blez, bgtz, sub, slt, xori, sh
Core 4 +
Core 4 +
lswi, sthx, extsh, eqv, ba,
multu, divu, srlv, xor, nor,
subfc, lswx, mtcrf, xori, addo
lwl, lwr, bltz, bgez, swl
C2
C3
C4
C5
1
Número de
Expressos em segundos.
67
25
35
45
55
A Tabela 6.3 mostra que o tempo2 de geração do montador cresce linearmente com o
tamanho do conjunto de instruções.
Tabela 6.3: Tempos de geração do montador
Core
Instruções descritas
PowerPC
MIPS
C1
15
0,97
0,98
C2
25
1,00
1,01
C3
35
1,02
1,02
C4
45
1,03
1,03
C5
55
1,10
1,10
A Tabela 6.4 caracteriza os benchmarks usados nos experimentos com as ferramentas
geradas. Para um dado conjunto de instruções, a coluna da esquerda representa o número
de instruções executadas em cada benchmark e a coluna da direita, o tamanho do código
(expresso em número de instruções).
O acrônimo N/A (não aplicável) indica casos não testados. Por exemplo, o programa
divmul não pôde ser testado no MIPS, pois necessita da instrução break, que não foi
implementada no modelo disponı́vel em [Arc04]. O programa xram não pôde ser testado
no PIC, devido a restrições do compilador utilizado.
Tabela 6.4: Caracterı́sticas dos benchmarks
Benchmark
2
MIPS
PowerPC
PIC
negcnt
154
32
121
28
150
30
gcd
209
53
198
48
125
32
int2bin
153
36
143
35
256
36
cast
80
48
87
55
68
60
divmul
N/A
N/A
167
55
296
106
fib
490
106
445
96
358
70
sort
2982
154
2744
48
2227
110
xram
43013
42
36869
38
N/A
N/A
Expresso em segundos.
68
Para fins de validação, o código executável de cada benchmark foi executado em cada
CPU-alvo. Os resultados experimentais foram consistentes para todos os casos testados.
Com objetivo de avaliar a eficiência, os tempos de pré-processamento e montagem
foram medidos, de forma conjunta, para cada benchmark, como mostra a Tabela 6.5.
Tabela 6.5: Tempos de pré-processamento e montagem de cada programa
Benchmark
Tempo [s]
MIPS
PowerPC
PIC
negcnt
0.030
0.035
0.020
gcd
0.030
0.050
0.020
int2bin
0.040
0.040
0.030
cast
0.040
0.050
0.030
divmul
N/A
0.050
0.060
fib
0.060
0.080
0.040
sort
0.070
0.110
0.050
xram
0.040
0.045
N/A
A correlação dos dados das Tabelas 6.4 e 6.5 mostra que, para uma mesma CPU, o
tempo cresce em menor proporção do que o número de instruções montadas. Por exemplo,
no caso do MIPS, se comparados os programas negnct e sort, o número de instruções é
multiplicado por 5, enquanto o tempo é multiplicado por 2,3. Este comportamento é uma
evidência experimental da eficiência das técnicas propostas e ferramentas geradas.
Por outro lado, para um mesmo programa benchmark testado em CPUs distintas, o
tempo pode crescer em proporção maior do que o número de instruções montadas. No
programa sort, por exemplo, se comparados o PIC e o PowerPC, o número de instruções
é multiplicado por 1,3, enquanto o tempo é multiplicado por 2,2. Isto pode se atribuı́do
à maior complexidade dos formatos de instrução do PowerPC.
69
Capı́tulo 7
Conclusões e perspectivas
Esta dissertação representa uma etapa importante na implementação de uma metodologia de suporte ao uso de ASIPs em SoCs. As Seções 7.1 e 7.2 resumem os principais
resultados do trabalho de pesquisa aqui descrito. A Seção 7.3 apresenta algumas perspectivas de trabalhos futuros.
7.1 Produtos de trabalho
Como resultado das pesquisas no âmbito desta dissertação e em colaboração com
atividades de iniciação cientı́fica [Fea04][Tea05a][Tea05b], foram desenvolvidos e validados
experimentalmente um modelo e duas ferramentas:
• Modelo funcional do microcontrolador PIC 16F84
• Gerador automático de montadores
• Gerador automático de pré-processadores
7.2 Contribuições e discussão
Esta dissertação contribui com uma nova técnica de geração automática de montadores
e pré-processadores. A técnica proposta baseia-se em três elementos-chave:
• Especificação unificada de aspectos léxico e sintáticos: ao contrário da
ma-ioria dos trabalhos relatados na literatura [Hea97a] que se baseiam no uso do
70
Lex [LEX04] e Yacc [YAC04], a técnica aqui adotada utiliza o GALS [Ges04], um gerador de analisadores cuja entrada é uma especificação unificada de aspectos léxicosintáticos.
• Novo algoritmo para geração de GLC: os trabalhos correlatos não apresentam
formalmente a técnica utilizada para o processo de geração de montadores. Esta
dissertação apresenta um algoritmo para geração automática de GLCs a partir de
uma ADL.
• Decomposição em etapas: a técnica decompõe o processo de geração e o processo de montagem em duas etapas distintas: o pré-processamento (macros, pseudoinstruções, modos de endereçamento) e a efetiva montagem de instruções nativas.
Isso facilita a automação, evitando que algumas informações tenham que ser inseridas manualmente como em [Kum00]. Além disso, o tratamento das caracterı́sticas
de endereçamento em nı́vel de expressão aritmética apresenta melhor usabilidade
que em nı́vel de byte ou bit como em [Kum00].
A técnica proposta possui as seguintes caracterı́sticas:
• Eficiência: foram apresentadas evidências experimentais da eficiência tanto das
ferramentas geradoras quanto das ferramentas geradas. Os tempos de geração
são suficientemente baixos e crescem linearmente com o tamanho do conjunto de
instruções. Os tempos de pré-processamento e de montagem crescem linearmente
com o número de instruções do programa.
• Robustez e corretude: a corretude é garantida por técnicas formais baseadas em
GLCs e a robustez pela adoção de uma especificação unificada de aspectos léxicosintáticos.
• Manutenibilidade e extensibilidade: o formalismo baseado em GLCs torna
segura a manutenção ou atualização das ferramentas em face de mudanças ou extensões na ADL. O processo de manutenção ou extensão é facilitado e acelerado
através de um mecanismo de co-validação entre linguagem e gramática embutido no
GALS, bem como por mecanismos de verificação de expressões regulares.
71
7.3
Trabalhos futuros
Algumas alternativas de continuidade das pesquisas são mostradas a seguir:
• Certificação do modelo funcional do PIC 16F84: o modelo desenvolvido será
submetido ao mesmo conjunto de benchmarks usados na certificação do microcontrolador i8051, já disponı́vel no repositório do Projeto BrazilIP [Net04].
• Desenvolvimento de um modelo do PIC 16F84 com precisão de ciclos: um
modelo desta natureza forneceria insumos para avaliação de desempenho e consumo
de energia.
• Implementação de um mecanismo de ligação: o tratamento de múltiplos
arquivos com código assembly não está atualmente suportado.
• Desenvolvimento de um escalonador de código: a partir de um modelo com
precisão de ciclos, poder-se-ia incorporar um escalonador para pós-processar a saı́da
do montador, reordenando as instruções para obter melhor desempenho do pipeline.
• Redirecionamento a partir de um compilador: um tópico interessante é a
adaptação do compilador da GNU/C++ para usar a descrição ADL como insumo
à geração de código assembly para o montador gerado automaticamente. O escalonador de código proposto no item anterior poderia ser adaptado e incorporado,
restando investigar-se como adaptar o mecanismo de seleção de instruções.
7.4
Expectativa de impacto
• Insumos para trabalho correlato: É de nosso conhecimento a existência de pesquisas em andamento no Laboratório de Sistemas de Computação (LSC) da UNICAMP que visam o desenvolvimento de um gerador de montadores mais genérico
para ser incorporado ao pacote ArchC. Espera-se que esta dissertação possa servir
de insumo ou contraponto para tais pesquisas.
• Disseminação do modelo no repositório do Projeto BrazilIP: espera-se que
o modelo do PIC 16F84, subproduto desta dissertação, possa ser incorporado à
plataforma Fênix e disseminado à comunidade através do Projeto BrazilIP [Net04].
72
Referências Bibliográficas
[Aea88] Alfred V. Aho and et al. Compilers: Principles, Techniques and Tools. AddisonWesley, 1988.
[Aea02] Maghsoud Abbaspour and et al. Retargetable Binary Utilities. In Design Automation Conference, 2002.
[Arc04] ArchC.
The
ArchC
Architecture
Description
Language,
2004.
http://www.archc.org. Acessado em 2004.
[Bea04] Gunnar Braun and et al. A Novel Approach for Flexible and Constistent ADLDriven ASIP Design. In DAC, Jun 2004.
[CF90]
Peter P. K. Chiu and Sammy T. K. Fu. A Generative Approach to Universal
Cross Assembler Design. SIGPLAN Notices, 25(1):43–51, 1990.
[Com04] GNU Compiler. Bison Page, 2004. http://www.gnu.org/software/bison/bison.html.
Acessado em 2004.
[Dea01] W. J. Dally and et al.
Route packets, not wires: on-chip interconnection
networks. In DAC, Jun 2001.
[ELF04] ELF.
Executable
and
Linking
Format,
2004.
http://www.cs.ucdavis.edu/~haungs-/paper/node10.html. Acessado em 2004.
[Fea04]
J. O. Carlomagno Filho and et al. Geração automática de montadores a partir
de ArchC: um estudo de caso com o PowerPC 405. Trabalho de Conclusão de
Curso, UFSC, Dezembro 2004.
[Fer66]
David E. Ferguson. Evolution of the meta-assembly program. Commun. ACM,
1966.
73
[Fre93]
Markus Freerick. The nML Machine Description Formalism. Technical report,
TU Berlin Computer Science., Jul 1993.
[Gea99] P. Grun and et al. RTGEN: An Algorithm for Automatic Generation of Reservation Tables from Architctural Descriptions. In ISSS, Jan 1999.
[Gea02] Thorsten Grötker and et al. System Design with SystemC. Klumer Academic
Publishers-pg 5-9, 2002.
[Ges04] Carlos Eduardo Gesser. GALS- Gerador de Analisadores Léxico e Sintático,
2004. Trabalho de Conclusão de Curso - UFSC. http://gals.sourceforge.net.
Acessado em 2004.
[GNU04] GNU. GNU Project, 2004. http://www.gnu.org. Acessado em 2004.
[Hea97a] George Hadjiyiannis and et al. An Instruction Set Description Language for
Retargetability. In DAC, Jun 1997.
[Hea97b] Mark R. Hartoog and et al. Generation of Software Tools from Processor Descriptions for Hardware/Software Co-design. In DAC, Jun 1997.
[Hea99] A. Halambi and et al. EXPRESSION: A Language for Architecture Exploration
through Compiler/Simulator Retargetability. In DATE, Mar 1999.
[Inc04a] Custom Computer Service Inc. Custom Computer Service Inc. PCW/CCS, 2004.
http://www.brazilip.org.br/fenix. Acessado em 2004.
[Inc04b] Microchip Technology Inc. Manual do Microcontrolador PIC 16F84., 2004.
http://www.microchip.com. Acessado em 2004.
[Kum00] Sarika Kumari. Generation of Assemblers Using High Level Processor Models.
Master’s thesis, Dept. of Computer Science and Engg., IIT Kanpur, India, Feb
2000.
[LEX04] LEX
and
YACC.
The
Lex
&
Yacc
Page.,
2004.
http://dinosaur.compilertools.net/. Acessado em 2004.
[LIS04] LISA Project Team.
Retargetable SW Development Tool Suite, 2004.
http://www.ert.rwth-aachen.de/Projekte/Tools/LISA/swtools.html. Acessado
em 2004.
74
[Mar03a] Grant Martin. SystemC: From Language to Applications, From Tools to Methodologies. Tutorial. SBCCI, Sep 2003.
[Mar03b] Peter Marwedel. Embedded System Design. Kluwer Academic Publishers, Nov
2003.
[Mea01] Prabhat Mishra and et al. Functional abstraction driven design space exploration
of heterogeneous programmable architectures. In ISSS, Jan 2001.
[Net04] BRAZIL-IP Network. BRAZIL-IP Network. The Fênix Platform., Nov 2004.
http://www.brazilip.org.br/fenix.
[Pea99] S. Pees and et al. LISA-Machine Description Language for Cycle-Accurate Models of Programmable DSP Architectures. In DAC, Jun 1999.
[Pro04] Dalton
Project.
Synthesizable
VHDL
Model
of
8051.,
2004.
http://www.cs.ucr.edu/ dalton/i8051/i8051syn/. Acessado em 2004.
[Rig04]
Sandro Rigo. ArchC: Uma Linguagem de Descrição de Arquiteturas. PhD thesis,
Jul 2004.
[Sea02]
Oliver Schliebusch and et al. Architecture Implementation Using the Machine
Description Language LISA. In DAC, Jun 2002.
[Sys04]
SystemC. SystemC Community, 2004. http://www.systemc.org. Acessado em
2004.
[Tea05a] Leonardo Taglietti and et al. Geração Automática de Ferramentas para ASIPs
a partir de Linguagem de Descrição de Arquiteturas. Submetido ao Iberchip
Workshop. 2005.
[Tea05b] Leonardo Taglietti and et al. Modelagem do microcontrolador PIC 16F84 para
projeto baseado no reuso de IPs. Submetido ao Iberchip Workshop. 2005.
[Tra87]
William J. Tracz.
Advances in Microcode Support Software.
In Annual
Workshop on Microprogramming, 1987.
[Wea87] H. Wu and et al. GPASM: A General Purpose Cross Assembler for Microprocessors. In IEEE Asian Eletronics Conference, 1987.
75
[Wic75] John Dryer Wick. Automatic Generation of Assemblers. PhD thesis, December
1975.
[Wol00] Wayne Wolf. Computers as Components. Morgan Kaufmann Publishers, 2000.
[YAC04] YACC. YACC - Yet Another Compiler Compiler. Gerador de Analisadores
Sintáticos, 2004. http://www.ma.adfa.oz.au/Local/Info/bison/bison toc.html.
Acessado em 2004.
76