Resumo - Centro de Ciências Exatas e da Terra

Transcrição

Universidade Federal do Rio Grande do Norte
Centro de Ciências Exatas e da Terra
Departamento de Informática e Matemática Aplicada
Curso de Ciências da Computação
Uma Plataforma para Sistemas Embarcados:
Desenvolvimento e Avaliação de Desempenho de um
Processador RTL e uma Cache L1 usando SystemC
RELATÓRIO DE GRADUAÇÃO
José Diego Saraiva da Silva
Natal/RN, Dezembro de 2006
Uma Plataforma para Sistemas Embarcados:
Desenvolvimento e Avaliação de Desempenho de um
Processador RTL e uma Cache L1 usando SystemC
Trabalho apresentado como requisito para aprovação na disciplina Relatório de Graduação, ministrada pelo professor Bruno Motta de Carvalho
Orientador: Prof. Dr. Ivan Saraiva Silva
Uma Plataforma para Sistemas Embarcados: Desenvolvimento e
Avaliação de Desempenho de um Processador RTL e uma Cache L1
usando SystemC
Esta relatório de graduação foi avaliado e considerado aprovado pelo Curso de Ciências da Computação do Departamento de Informática e Matemática Aplicada da Universidade Federal do Rio
Grande do Norte.
Prof. Dr. Ivan Saraiva Silva
Orientador
Banca Examinadora:
Prof. Dr. Bruno Motta de Carvalho
Membro
Profa. Dra. Elizabeth Ferreira Gouvêa Goldbarg
Membro
ii
AGRADECIMENTOS
A Deus, por me abençoar e conceder várias oportunidades, embora nem sempre tenha sido
merecedor.
Aos meus pais e ao meu irmão Diógenes, pelo apoio e reconhecimento em todos os momentos. Por me ajudarem a me manter firme em todos os momentos. Muito Obrigado.
Aos Professor Ivan Saraiva, meu orientador, por acreditar no sucesso deste trabalho e, principalmente, pelo incentivo.
À minha amiga Tássia, por contribuir no desenvolvimento dos algoritmos de substituição
e por me ajudar nos estudos durante o curso. E aos meus amigos Guilherme e Ronualdo, por
transmitirem conhecimentos valiosos.
iii
Este trabalho foi desenvolvido com o apoio da Agência Nacional do Petróleo, através do Programa de Formação de Recursos Humanos No 22 - Formação em Geologia, Geofísica e Informática no Setor Petróleo e Gás Natural na UFRN - com especialização em Sistemas em Tempo
Real para Otimização e Automação do Setor Petróleo e Gás Natural.
iv
Resumo
Diversos setores da indústria do petróleo e gás natural necessitam de soluções computacionais
com alto poder de processamento, alta escalabilidade e com capacidade para se comunicar com
o meio através de sensores e atuadores ou através de outros sistemas. Neste contexto, os sistemas
embarcados apresentam-se como ótimas soluções computacionais.
Este trabalho consiste na modelagem, design e implementação de um processador SPARC V8
e módulos de cache L1 para a concepção de uma plataforma MP-SoC para sistemas embarcados
voltada para o setor de petróleo e gás natural.
A plataforma atualmente é composta pelos seguintes componentes: processador SPARC
V8, módulo de Cache, módulo de Memória, módulo de Diretório e dois diferentes modelos
de Network-on-Chip, a NoCX4 e a Árvore Obesa. Todos os módulos de cache foram implementados utilizando a linguagem de descrição de hardware SystemC.
Palavras-chave: SPARC, Cache, Sistemas Embarcados, System-on-Chip, Network-on-Chip,
Projeto Baseado em Plataforma, SystemC.
v
Abstract
Many sectors from oil and natural gas industry need computational solutions with huge processing capabilities, high scalability and ability to communicate with the environment through
sensors, actuators and even other systems. In this context, embedded systems are presented as an
excellent computational solutions.
This work consists in the modeling, design and implementation of a SPARC V8 processor and
L1 Cache Modules in order to compose an MP-SoC Plataform for embedded systems, focusing
the oil and natural gas sector.
Currently the platform is composed of the following components: SPARC V8 processor,
Cache module, Memory module, Directory module and two different modules of network-onchip, NoCX4 and Obese tree. All modules were implemented using using the SystemC hardware
description language.
Key words: SPARC, Cache, Embedded Systems, System-on-Chip, Network-on-Chip, PlatformBased, SystemC.
vi
Sumário
1
INTRODUÇÃO
1
2
METODOLOGIA
2.1 Implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Montador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Validação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
6
6
6
3
PROJETO BASEADO EM PLATAFORMA
3.1 A Plataforma STORM . . . . . . . . . .
3.1.1 CaCoMa . . . . . . . . . . . . .
3.1.2 Diretório . . . . . . . . . . . . .
3.1.3 Memória . . . . . . . . . . . . .
3.1.4 Interconexão . . . . . . . . . . .
4
SPARC V8
4.1 A Arquitetura SPARC V8 . . . . . . . . .
4.1.1 Formato de Instruções . . . . . .
4.1.2 Conjunto de Instruções . . . . . .
4.1.3 Conjunto de Registradores . . . .
4.1.4 Formatos de Dados . . . . . . . .
4.1.5 Modo Usuário e Modo Supervisor
4.1.6 Modelo de Memória . . . . . . .
4.1.7 Modos de Endereçamento . . . .
4.1.8 Tratamento de Interrupções . . .
4.1.9 Instruções de LDSTUB e SWAP .
4.1.10 Sincronismo das Instruções . . . .
4.1.11 Mecanismos de bypassing . . . .
vii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
12
12
13
13
14
.
.
.
.
.
.
.
.
.
.
.
.
16
17
19
20
21
23
24
24
25
26
27
28
28
4.2
5
6
4.1.12 Previsão de Desvios . . . . . .
4.1.13 Unidade de Controle Distribuída
O Sistema de Caches . . . . . . . . . .
4.2.1 Mapeamento . . . . . . . . . .
4.2.2 Política de Substituição . . . . .
4.2.3 Política de Atualização . . . . .
4.2.4 Tamanho do Bloco . . . . . . .
Experimentos Computacionais
5.1 Simulações . . . . . . . . . . . . . . .
5.1.1 Fatorial . . . . . . . . . . . . .
5.1.2 Seqüência de Fibonacci . . . . .
5.1.3 Run-length encoding - RLE . .
5.1.4 Cifra de César . . . . . . . . .
5.1.5 Busca Binária . . . . . . . . . .
5.1.6 MergeSort . . . . . . . . . . .
5.1.7 Algoritmo de Prim . . . . . . .
5.1.8 Cifra de Hill . . . . . . . . . .
5.1.9 JPEG . . . . . . . . . . . . . .
5.2 Análise dos Parâmetros da Cache . . . .
5.3 Análise dos Algoritmos de Substituição
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
29
30
30
32
33
38
38
.
.
.
.
.
.
.
.
.
.
.
.
39
39
40
42
42
44
45
46
47
48
50
52
53
CONCLUSÃO
55
6.1 Trabalho Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
viii
Lista de Figuras
2.1
Duas metodologias de projeto (a) Metodologia tradicional; (b) Metodologia SystemC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
3.1
3.2
3.3
3.4
3.5
Retorno financeiro de projeto em função do tempo de projeto.
Retorno financeiro de projeto em função do tempo de projeto.
Módulos da STORM . . . . . . . . . . . . . . . . . . . . . .
Topologia NoCX4. . . . . . . . . . . . . . . . . . . . . . . .
Topologia Árvore Obesa. . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
9
11
12
14
14
4.1
4.2
4.3
4.4
4.5
4.6
4.7
Visão geral da Arquitetura SPARC V8.
Visão geral do SPARC. . . . . . . . .
Formatos de instruções . . . . . . . .
Janela de Registradores. . . . . . . . .
Mecanismo de bypassing. . . . . . . .
Árvore de decisão do pseudo-LRU. . .
Fluxo lógico de uma cache SLRU. . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
18
18
20
22
29
34
36
5.1
5.2
Figura utilizada na simulação do JPEG. . . . . . . . . . . . . . . . . . . . . . . 52
Associatividade versus Tamanho da Cache. . . . . . . . . . . . . . . . . . . . . 53
ix
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Lista de Tabelas
4.1
4.2
4.3
4.4
4.5
4.6
conjunto de instruções do SPARC. . . . . . . . . . . . . .
Equivalente SPARC de outros modos de endereçamento. .
Número de ciclos gasto para execução de instruções. . . .
Identificadores de espaço de endereçamento. . . . . . . . .
Representação da árvore binária em forma de string de bits.
Atualização dos bits de estados. . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
21
25
28
31
35
35
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12
Template das tabelas de resultados. . . . . . . . . . . . . . . . . .
Resultados do Fatorial em assembler. . . . . . . . . . . . . . . . .
Resultados do Fatorial desenvolvido em C. . . . . . . . . . . . . .
Resultados do Fibonacci. . . . . . . . . . . . . . . . . . . . . . .
Resultados do RLE. . . . . . . . . . . . . . . . . . . . . . . . . .
Resultados do algoritmo cifra de César. . . . . . . . . . . . . . .
Resultados da Busca Binária. . . . . . . . . . . . . . . . . . . . .
Resultados do Mergesort. . . . . . . . . . . . . . . . . . . . . . .
Resultados do Prim. . . . . . . . . . . . . . . . . . . . . . . . . .
Resultados da simulação do algoritmo Hill. . . . . . . . . . . . .
Resultados da simulação do JPEG. . . . . . . . . . . . . . . . . .
Tamanho versus Algoritmo de Substituição versus Taxa de acerto.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
39
41
41
42
43
44
46
47
48
50
51
54
x
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Lista de Siglas
P&G
STORM
CISC
RISC
SPARC
RTL
CI
SoC
NoC
VLIW
DSP
ASIPs
RTOS
NRE
CaCoMa
IU
FPU
CP
PC
ULA
EF
PSR
EC
Bicc
FBfcc
Petróleo e Gás Natural
MP-Soc DirecTory-Based PlatfORM
Complex Instruction Set Computer
Reduced Instruction Set Complex
Scalable Processor ARChitecture
Register Transfer Level
Circuito Integrado
System-on-Chip
network-on-chip
Very-Long Instruction Word
Digital Signal Processing
Application Specific Integrated Processor
Real Time Operating Systems
Non-Recurrent Engineering
Cache Communication Manager
Integer Unit
Floating-Point Unit
Co-Processador
Program Counter
Unidade Lógico-Aritmética
Enable Floating
Processor Status Register
Enable_Coprocessor
Branch on Integer Condition Codes
Branch on Floating-point Condition Codes
xi
CBccc
CWP
WIN
TBR
TSO
ASR
FSR
ET
TEM
PIL
tt
ASI
LDA
STA
FIFO
LFU
LRU
SLRU
ASCII
DCT
Branch on Coprocessor Condition Codes
Current Window Point
Window Invalid Mask
Trap Base Register
Total Store Order
Ancillary State Register
FPU Status Register
Enable Trap
Trap Enable Mask
Processor Interrupt Level
Trap Type
Address Space Identifier
Load Word from Alternate space
Store Word into Alternate space
First-In-First-Out
Least Frequently Used
Least Recently Used
Segmented Least Frequently Used
American Standard Code for Information Interchange
Discrete Cossine Transform
xii
Capítulo 1
INTRODUÇÃO
Vários problemas encontrados na indústria do petróleo e gás natural (P&G) exigem soluções
computacionais que atendam a requisitos rígidos de tempo na operação do sistema, baixo consumo de energia e elevado grau de processamento para atender a grande demanda de dados produzidas pelos vários sensores que monitoram ou controlam o meio. Neste contexto os sistemas
embarcados apresentam-se como ótimas soluções computacionais. Dentre as várias aplicações
dos sistemas embarcados na indústria do petróleo, temos: técnicas de avaliação de formações;
sistemas de detecção e controle de vazamento em dutos de petróleo; sistemas capazes de prover
mecanismos automáticos de posicionamento global em navios de plataformas de perfuração em
águas profundas.
As técnicas de avaliação de formações visam definir a capacidade produtiva e a valoração
das reservas de óleo e gás de uma jazida petrolífera. Estas técnicas se baseiam principalmente
na perfilagem de poço aberto, perfilagem de produção, nos testes de pressão e nos testes de
formação.
A perfilagem é o processo de traçar uma imagem visual ou perfil, em relação à profundidade,
de uma ou mais propriedades das rochas perfuradas. Tais perfis são obtidos através do deslocamento contínuo de sensores de perfilagem dentro do poço [22]. A perfilagem a poço aberto é feita
antes da descida do revestimento de produção e tem como objetivo a identificação da litologia
do poço, estimar a porosidade das rochas e detectar a presença de hidrocarbonetos leves ou gás.
Já a perfilagem de produção é feita após a descida do revestimento de produção e completação 1
inicial do poço. O objetivo desta perfilagem é determinar a efetividade de uma completação e as
condições de produtividade.
1
Conjunto de operações destinadas a preparar o poço para produzir óleo ou gás
CAPÍTULO 1. INTRODUÇÃO
2
As etapas de perfilagem geram um grande volume de informações sobre a espessura, profundidade e comportamento das camadas de rochas existentes nas vizinhanças do poço.
Os testes de pressão determinam as pressões no fundo do poço antes e durante a produção
de óleo ou gás. Conhecendo-se as pressões, as vazões e as propriedades dos fluídos produzidos,
pode-se obter informações a respeito da rocha-reservatório 2 .
Por fim, temos os testes de formação. O teste de formação é a técnica utilizada para confirmar
a presença de hidrocarboneto na formação e estimar a capacidade produtiva das zonas investigadas. Tal procedimento é baseado no estabelecimento de um diferencial de pressão entre esta zona
estudada e o interior do poço através da remoção da pressão hidrostática da coluna de lama que
se encontra acima de tal zona. Este diferencial de pressão permite que os fluidos da formação
penetrem na coluna vazia que foi descida no poço e alcancem a superfície. Os dados obtidos
nestes testes incluem a quantidade e qualidade dos fluidos produzidos, durante o intervalo de
tempo, assim como pressões de surgência e estática do reservatório.
Os dados coletados nos testes de avaliação de formações convencionais utilizam formato analógico de medição que são interpretados em algum momento após os testes feitos pelos técnicos.
O uso de sistemas embarcados pode permitir o monitoramento em tempo real do testes de
avaliação de formações, melhorar a precisão dos dados, pois coletam dados no formato digital, e
reduzir o tempo gasto na interpretação do grande volume de dados. Porém, o desenvolvimento de
sistemas embarcados é um processo complexo que envolve a definição da arquitetura de hardware
e de software a cada projeto. Isto dificulta a reutilização do sistema ou parte dele em outras
aplicações, além de aumentar o tempo e o custo do projeto.
Uma plataforma para projetos de sistemas embarcados foi iniciada no Programa de PósGraduação em Sistemas e Computação da Universidade Federal do Rio Grande do Norte por
[16]. Esta plataforma, denominada STORM (MP-Soc DirecTory-Based PlatfORM), visa diminuir o tempo e os custos de desenvolvimento de sistemas embarcados.
O presente trabalho alia-se a este esforço de desenvolvimento com o objetivo específico de
especializar esta plataforma para aplicações na área de exploração de petróleo e gás natural. As
aplicações desta área de atuação exigem soluções computacionais de alto poder de processamento, alta escalabilidade e com capacidade para se comunicar com o meio através de sensores,
atuadores ou através de outros sistemas.
O principal empecilho para a aplicação da STORM na área do petróleo e gás natural era a falta
de uma unidade de processamento capaz de prover alto poder de processamento, escabilidade e
a capacidade de comunicação à plataforma. Portanto, o objetivo deste trabalho é desenvolver
2
Rocha aonde ocorre o acumulo de petróleo. São rochas que possuem boa porosidade e permeabilidade.
CAPÍTULO 1. INTRODUÇÃO
3
um processador para a plataforma STORM que permita a mesma prover os recursos de hardware
necessários para o desenvolvimento de aplicações seqüências e distribuídas na área do petróleo
e gás.
Inicialmente, havia duas opções básicas na escolha do processador: A arquitetura CISC
(Complex Instruction Set Computer - Computador com um Conjunto Complexo de Instruções)
ou a arquitetura RISC (Reduced Instruction Set Complex - Conjunto Reduzido de Instruções
Complexas).
A primeira opção é baseada no desenvolvimento de instruções complexas e na microprogramação. A microprogramação significa que cada instrução é interpretada por um microprograma
localizado em uma memória interna à pastilha do processador. A segunda opção utiliza apenas
instruções simples, com execução direta, transferindo para o compilador a responsabilidade de
emular as funções mais complexas.
Os microprocessadores RISC possuem uma arquitetura interna mais simples, o que permite
que eles sejam implementados com tecnologia menos sofisticada, mais barata, e com menor gasto
de área, diminuindo os custos de fabricação. Estas qualidades fizeram dos microprocessadores
RISC as melhores opções para o mercado embutido, uma vez que, este mercado compete em
custo e energia. Estima-se que 90% do mercado embutido utilize a arquitetura RISC [10].
Dentre as várias arquiteturas RISC disponíveis, optou-se pelo processador SPARC V8. O
SPARC (Scalable Processor ARChitecture) [17] é uma arquitetura de microprocessador aberta
desenvolvida pela Sun Microsystems que permite a elaboração de implementações personalizadas, embora mantendo a compatibilidade binária. É um processador de porte variável, utilizado
em sistemas que vão desde sistemas embarcados até grandes servidores.
Ele foi escolhido para integração com a plataforma STORM por ter arquitetura aberta e pela
vasta gama de ferramentas disponíveis, dentre elas o compilador de C da GNU, o GCC [9], o
que facilita a simulação de aplicações reais, além de ser um compilador disponível em várias
arquiteturas de hardware e em vários sistemas operacionais.
Este texto está organizado da seguinte forma: O Capítulo 2 apresenta a metodologia adotada
no trabalho. O Capítulo 3 apresenta os conceitos e fundamentos do paradigma de concepção
de sistemas baseado em plataforma. Além disso, esta seção apresenta em detalhes a plataforma
STORM. O Capítulo 4 descreve em detalhes o processador SPARC V8 e o sistemas de cache
desenvolvidos no escopo deste trabalho. Os resultados dos experimentos computacionais realizados são apresentados no Capítulo 5. E por fim, o Capítulo 6 expõe as considerações finais
deste trabalho.
Capítulo 2
METODOLOGIA
O processador SPARC V8 e o sistema cache propostos neste trabalho foram implementados
utilizando a linguagem de descrição de hardware SystemC. De fato, o SystemC não é uma linguagem de descrição de hardware, mas sim uma biblioteca de classes C++ e uma metodologia
de desenvolvimento [20].
Tal biblioteca fornece ao C++ padrão características como temporização de hardware, atividade comportamental, concorrência e mecanismos de simulação. Desta maneira, o SystemC
combina as vantagens de C++ como popularidade, robustez e eficiência com uma biblioteca de
classes apropriada para a descrição de hardware.
O SystemC cria uma especificação executável do sistema. Uma especificação executável é
um programa em C++ que exibe o mesmo comportamento do sistema descrito quando executa.
Essa especificação executável provê muitos benefícios, tais como: evitar inconsistências e erros,
ajudar na verificação da completude da especificação, assegurar uma interpretação não ambígua
para a especificação do sistema, verificar a funcionalidade do sistema antes do início da sua
implementação, criar modelos de desempenho do sistema e estimar a performance do sistema
[20].
A metodologia de projeto, que adota a linguagem SystemC, pressupõe o refinamento progressivo do sistema, ou seja, inicia-se como uma aplicação puramente em C++ que refinada até o
nível RTL (Register Transfer Level - Nível de Transferência de Registradores). Esta metodologia
de projeto rompe com o paradigma tradicional de desenvolvimento de hardware.
Na metodologia tradicional de design, o desenvolvimento inicia-se com a construção de um
modelo em C ou C++ do sistema para verificar os algoritmos e conceitos no nível de sistema.
Após a validação dos conceitos e dos algoritmos, o modelo feito em C ou C++ é implementado
CAPÍTULO 2. METODOLOGIA
5
em hardware através transcrição do código para HDL 1 em um único passo. A Figura 2 resume
as diferenças entre as duas abordagens.
Figura 2.1: Duas metodologias de projeto (a) Metodologia tradicional; (b) Metodologia SystemC.
A abordagem tradicional possui três grande problemas que diminuem a produtividade e aumentam o tempo de projeto. O primeiro é a transcrição manual e em um único passo do modelo
em C para o modelo em HDL pela equipe de desenvolvedores. Este processo é tedioso e propício
a erros [20]. O segundo grande problema é desconexão do modelo em C do modelo em HDL.
Após a transcrição, o modelo em C fica rapidamente obsoleto pois o foco do desenvolvimento
passa a ser o modelo HDL. O último grande problema é o fato de que a equipe de desenvolvimento não pode utilizar o testbench desenvolvido para o modelo em alto nível diretamente no
modelo HDL. Ou seja, além do sistema, a equipe precisa ser transcrever toda a suíte de testes
para HDL.
A abordagem adotada pelo SystemC possui duas grandes vantagens sobre o modelo tradicional. A primeira é a metodologia de refinamento. Nesta metodologia, o projetista não converte a
descrição em C para HDL em um único passo. Ao invés disso, o projetista realiza vários refinamentos em pequenas seções, seguidos da verificação do atual modelo para uma eventual correção
de bugs. A segunda grande vantagem do uso do SystemC é o fato do projetista utilizar apenas
uma única linguagem no desenvolvimento do sistema. O que permite a reutilização direta do
1
Hardware description language ou HDL é uma classe de linguagem de computador para a descrição formal de
circuitos eletrônicos.
6
testbench desenvolvido, economizando o tempo gasto na conversão do mesmo.
2.1
Implementação
Os módulos previstos neste trabalho foram implementados utilizando a ferramenta SystemC.
Como foi dito anteriormente, esta ferramenta possibilita a implementação em diversos níveis de
abstração e precisão. Para este projeto definiu-se que os módulos devem apresentar precisão de
ciclos em suas operações. Este nível de descrição, denominado RTL cycle-accurate, foi escolhido
por permitir a verificação do comportamento da arquitetura ciclo a ciclo sem que se tenha que
implementar todas as portas e sinais da arquitetura bit a bit, e por ser o nível de descrição dos
outros módulos da plataforma STORM.
2.1.1
Montador
Um montador (assembler) SPARC foi desenvolvido junto com a plataforma STORM para permitir o desenvolvimento de aplicações em linguagem C para a plataforma. A função do montador
é fazer a conexão entre o compilador GCC e a plataforma STORM. O montador reconhece o
código gerado pelo GCC e produz um binário que é utilizado como entrada para a plataforma.
Por não ter um sistema operacional para a STORM, a gerência de memória é feita diretamente
pela plataforma e pelo montador. Isto obriga a plataforma a utilizar um esquema de alocação de
memória estática. Neste esquema, o tamanho de cada região da memória é definido em tempo
de compilação. Sendo de responsabilidade do montador alocar as variáveis globais, a memória
de programa e a região de pilha dos processadores.
2.2
Validação
A validação da plataforma STORM e dos módulos propostos neste trabalho foi realizada através de aplicações genéricas e específicas para a área do petróleo e gás natural. As aplicações
genéricas consistem em algoritmos de ordenação, criptografia, compactação de imagens, árvore
geradora mínima dentre outros. Estas aplicações são apresentadas com mais detalhes no Capítulo
5 e foram utilizadas para validar as questões mais rudimentares do funcionamento do processador como busca e decodificação de instruções, execução de saltos, acessos a memória, integração
do SPARC com a plataforma dentre outras questões de projeto.
7
As aplicações específicas para a área do petróleo e gás natural consistem de metaheurísticas
voltadas para o problema da rede de distribuição de gás natural. As metaheurísticas que foram
utilizadas para validar a plataforma são: Busca Tabu, GRASP e Algoritmos transgenéticos.
Todas essas aplicações foram desenvolvidas de forma seqüencial e paralela pela aluna Tássia
Freitas [7]. O desenvolvimento destas metaheurísticas objetiva validar a plataforma como um
todo, verificando o comportamento da mesma em ambientes seqüencias e paralelos que exigem
alto poder de processamento.
Capítulo 3
PROJETO BASEADO EM
PLATAFORMA
Nos últimos anos, a demanda por sistemas embarcados vem crescendo de maneira avassaladora
em diversas áreas e com diversos propósitos. Pode-se encontrar tais sistemas em carros, eletrodomésticos, aparelhos telefônicos, caixas eletrônicos de bancos, câmeras digitais, sistemas de
controle de vôo, etc.
Esta proliferação dos sistemas embarcados ocorreu devido ao aumento significativo da capacidade do Circuito Integrado (CI), o que permitiu a construção de sistemas inteiros em um único
chip (SoC - System-on-Chip).
Define-se como sistema embarcados todo sistema computacional de propósito especial, o
qual é completamente encapsulado pelo dispositivo que ele controla. O sistema embarcado tem
como principal característica o fato de sua principal funcionalidade não ser computacional, mas o
controle desta funcionalidade é computacional. Ou seja, os sistemas embarcados são desenhados
para realizar tarefas específicas.
A arquitetura de hardware de um SoC embarcado pode conter um ou mais processadores,
memórias, interfaces para periféricos e blocos dedicados. Os componentes são interligados por
uma estrutura de comunicação que pode variar de um barramento a redes de interconexão (NoC
- network-on-chip)[6].
Os processadores podem ser de tipos diversos (RISO, VLIW, DSP, até ASIPs - processadores
integrados para aplicações específicas), conforme a aplicação. No caso de sistemas contendo
componentes programáveis, o software de aplicação pode ser composto por múltiplos processos,
distribuídos entre diferentes processadores e comunicando-se através de mecanismos variados
[5].
CAPÍTULO 3. PROJETO BASEADO EM PLATAFORMA
9
Além disso, a arquitetura de um sistema embarcado pode conter um sistema operacional de
tempo real (RTOS) com a finalidade de oferecer serviços como comunicação, escalonamento de
processos, sincronização de tarefas, gerência de memória etc.
Em geral, nos projetos de sistemas embarcados é necessário definir toda a arquitetura de
software e hardware devido as limitações de poder computacional e capacidade de memória do
sistema. Assim, requisitos não funcionais como consumo de energia, tempo de resposta, segurança, tolerância à falhas, expectativa de vida e área ocupada também devem ser considerados
pelos projetistas. Estas características do projeto de sistemas embarcados implica em equipes
grandes de projetistas, tempos de projetos longos e caros.
A alta demanda exigida pelo mercado atual e a contínua evolução tecnológica impõe as empresas a desenvolverem novos sistemas embarcados em um curto espaço de tempo. Ou seja, as
empresas precisam diminuir o time-to-mark dos seus produtos.
Time-to-mark é o tempo decorrido desde o inicio do projeto até a sua disponibilização no
mercado. Um elevado time-to-mark representa maiores custos para o desenvolvimento do sistemas e ao mesmo tempo, representa uma menor curva de faturamento. A Figura 3.1 mostra
que o lucro gerado por um produto tem estrita relação com a velocidade de seu lançamento no
mercado.
Figura 3.1: Retorno financeiro de projeto em função do tempo de projeto.
Na figura, observa-se que à medida que o lançamento é adiado em relação ao surgimento
inicial daquele tipo de produto no mercado, o lucro obtido com a venda do produto cai rapidamente. Desta maneira, os novos produtos têm uma vida cada vez mais curta, de modo que o
10
retorno financeiro do projeto deve ser obtido também em pouco tempo.
Outro grande problema diz respeitos ao aumento dos custos de engenharia não recorrentes
(NRE, do inglês). Tais custos estão associados com design e a utilização de ferramentas no
desenvolvimento de complexos chips. Estima-se que um conjunto de máscaras de fabricação
está alcançando a ordem de milhões de dólares, o que obriga as empresas a garantirem um alto
volume de produção para amortizar os gastos de fabricação.
Entretanto, a metodologia tradicional de projeto full-custom, onde a equipe de projetistas desenha o chip transistor a transistor, está se tornando inadequada para atender alta produtividade
e o baixo time-to-mark exigidos pela atual dinâmica do mercado. Devido aos problemas apresentados, as empresas de eletrônica procuraram aumentar a produtividade e flexibilidade, e ao
mesmo tempo, diminuir o tempo e os custos de projeto através de metodologias que disciplinem
os seus designers.
Em geral, tais metodologias visam balancear os custos de produção com o custo e o tempo de
desenvolvimento do ponto de vista da performance e da funcionalidade do sistema. Nos últimos
anos, várias abordagens foram propostas para conseguir atingir este equilíbrio, dentre elas, a
metodologia de Projeto Baseado em Plataforma.
Projeto Baseado em Plataforma é um novo paradigma de concepção de sistemas embarcados
em um único chip, que é orientado à integração e ao reuso. O conceito de plataforma não tem
uma definição única, mas de maneira geral, pode ser entendido como uma abstração que cobre
diversos possíveis refinamentos em baixo-nível [1].
No contexto de sistemas integrados, uma plataforma é comumente expressa como um conjunto de componentes previamente projetados e testados. Estes componentes, geralmente chamados de IP cores, determinam a capacidade da plataforma.
A plataforma deve incluir primitivas de comunicação como barramentos, NoCs e crossbar
switches. Tais primitivas de comunicação devem garantir a ortogonalidade da comunicação
versus a funcionalidade dos blocos. Esta característica da comunicação entre os componentes
garante que o re-uso dos componentes seja feito com nenhum ou pouco esforço.
O principal benefício da política de reutilização de componentes de software e de hardware
é a redução do time-to-mark. Outro benefício é a alta flexibilidade que a plataforma oferece,
uma vez que, os componentes são altamente parametrizáveis. A Figura 3.2, retirada do roadmap
ITRS [11], mostra que as metodologias tradicionais de projeto têm custos crescentes que não
conseguem acompanhar a evolução tecnológica prevista pela lei de Moore.
Pode-se observar, na Figura 3.2, que os custos de projeto podem ser sensivelmente reduzidos
pelo re-uso de plataformas e componentes. O gráfico mostra que no período de 1997 a 2001,
11
Figura 3.2: Retorno financeiro de projeto em função do tempo de projeto.
os custos dos projetos que utilizam apenas a metodologia full-custom mais que triplicaram, enquanto que os custos dos projetos que utilizam alguma metodologia de projeto aumentaram em
1,5 vezes apenas.
O projeto da um SoC embarcado consiste em escolher uma instância da plataforma que
atenda os requisitos funcionais e não funcionais da aplicação. Uma instância da plataforma é
uma arquitetura derivada da plataforma através da seleção e do ajustes de parâmetros dos componentes que forma a biblioteca de componentes da plataforma.
Um ponto crítico do projeto é o mapeamento da aplicação para a arquitetura alvo. Nesta
etapa do projeto, decide-se que funcionalidades da aplicação serão implementadas em software e
as que serão implementadas em hardware. É evidente que o processo de mapeamento determina
o custo de design e o desempenho do SoC embarcado.
3.1
12
A Plataforma STORM
A plataforma STORM (MP-SoC DirecTory-Based PlatfORM) é uma plataforma de desenvolvimento de sistemas embarcados. Por ser uma plataforma, não possui uma arquitetura definida,
mas sim um conjunto de módulos e especificações sobre como devem ser utilizados, sendo possível para o projetista criar instâncias de arquitetura com diversas características.
A STORM é composta pelos seguintes módulos: processador SPARC V8, módulos de caches, módulos de memória, módulo de diretório e dois modelos de redes-em-chip. O processador
SPARC V8 e o sistema de caches foram desenvolvidos no escopo específico deste trabalho. Eles
serão apresentados no Capítulo 4. A Figura 3.3 ilustra os componentes da plataforma e suas
relações.
Figura 3.3: Módulos da STORM
A seguir, temos uma breve explicação sobre a funcionalidade de cada módulo da STORM
que não está no escopo específico deste trabalho.
3.1.1
CaCoMa
O CaCoMa (Cache Communication Manager) é um módulo especialmente desenvolvido para
os propósitos da plataforma. Ele possui como função principal a gerência da comunicação das
13
memórias cache (e conseqüentemente, do processador) com seu roteador, e com o resto da plataforma. O CaCoMa está ligado às caches de dados e instruções, e ao roteador da NoC.
As principais funções do CaCoMa são: tradução dos endereços lógicos enviados pelo processador em endereços físicos, envio e recebimento de pedidos de leitura e escrita de blocos para
o diretório e tratamento das requisições vinda do diretório referentes ao protocolo de coerência
de cache. Tais requisições pode ser invalidação de blocos ou envio de blocos modificados pelas
memórias caches associadas ao CaCoMa em questão.
3.1.2
Diretório
Todo ambiente concorrente que utiliza um ou mais níveis de cache associados a cada processador
deve ter um mecanismo para manter a coerência entre todas as cache do sistema. Uma vez que,
esta organização cria um problema chamado de coerência de cache. O problema ocorre porque
podem existir simultaneamente múltiplas cópias do mesmo dado em diferentes caches, e se os
processadores realizarem atualizações em suas cópias livremente, o resultado será imprevisível.
O módulo de Diretório tem a função implementar o protocolo de coerência de cache da
STORM. Cada módulo de memória está conectado um módulo Diretório, que controla seu funcionamento e faz sua conexão com a NoC e, portanto, com o resto da plataforma. O diretório é
um controlador centralizado que mantém informações sobre as localizações e o estado das cópias de blocos de um módulo de memória a ele associado. Antes que qualquer processador da
plataforma possa atualizar a sua cópia local de uma linha da cache, ele deve requisitar o acesso
exclusivo a está linha da cache ao diretório.
3.1.3
Memória
A plataforma STORM faz uso de memória compartilhada, onde diversos blocos de memória
espalhados pela NoC formam um único espaço de endereçamento, visível por todos os processadores. No modelo de memória compartilhada não existe memória local ou remota. Este modelo
de memória é de mais fácil programação do que os modelos de memória distribuída.
Em sistemas multi-processadores interligados por barramento, o modelo de memória compartilhada possui uma escalabilidade limitada devido à necessidade de operações de broadcast
realizadas pelos mecanismos de coerência de cache baseados em protocolos snoop. Entretanto,
a STORM é um sistema multiprocessado interligado por redes-em-chip e o uso de diretório evita
o broadcast na manutenção da carência de cache. Desta maneira, a escalabilidade do sistema não
é comprometida pelo modelo de memória adotado.
3.1.4
14
Interconexão
O sistema de interconexão da STORM é realizado através de redes-em-chip (do inglês, networkon-chip). Dois diferentes módulos de NoC estão presentes na STORM: a NoCX4 e a Árvore
Obesa. A NoCX4 consiste em uma malha de roteadores, cada um ligado a um módulo da plataforma (topologia direta). A Figura 3.4 a seguir mostra esta topologia.
Figura 3.4: Topologia NoCX4.
A Árvore Obesa possui topologia indireta, na qual os roteadores são alocados nos níveis da
árvore. O nível mais baixo é composto por Roteadores Folha (Leaf Routers) e os demais níveis são compostos por Roteadores Intermediários (Intermediary Routers). Os Roteadores Folha
são conectados aos elementos de processamento enquanto que os Roteadores Intermediários são
conectados a outros roteadores. A topologia Árvore Obesa é mostrada na Figura 3.5.
Figura 3.5: Topologia Árvore Obesa.
15
Uma característica importante desta topologia é o fato de que todos os roteadores filhos de
um mesmo pai são completamente interconectados. Isto evita a criação de gargalo entre os
roteadores filhos e o roteador pai, uma vez que, todo o tráfego entre nós de nível mais baixo fica
restrito aos roteadores filhos. Por utilizar o número mínimo de roteadores, esta topologia tem
baixa latência de comunicação.
Capítulo 4
SPARC V8
O SPARC (Scalable Processor ARChitecture - Arquitetura de Processadores Escaláveis) é uma
arquitetura de microprocessador RISC de propósito geral desenvolvida pela Sun Microsystems
no período de 1984 a 1987. O objetivo do SPARC é facilitar o desenvolvimento de pipeline,
obter alta performance, baixo custo e implementação multi-tecnológica.
O SPARC formulado pela Sun foi baseado nas máquinas RISC I, RISC II e SOAR desenvolvidas na Universidade da Califórnia em Berkeley ( UC Berkeley). As máquinas RISC I e RISC II
foram simples projetos que continham apenas dois e três estágios de pipeline, respectivamente.
Entretanto, introduziram conceitos importantes como janela de registradores e execução de desvios atrasados. Já o SOAR foi uma reimplementação da máquina RISC para rodar o SMALLTALK. O SOAR extende a máquina RISC I, adaptando o conjunto de instruções as necessidades
do SMALLTALK e adicionado instruções necessárias para o suporte da programação orientada
a objetos como tratamento de interrupções dentre outras.
O SPARC herdou do RISC I e II a organização dos registradores em janela e a execução de
desvios atrasados, e do SOAR, herdou as instruções para suporte à linguagem orientada a objetos. A principal diferença entre o projeto SPARC e os projetos RISCs realizados em Berkely
é que o SPARC permite alta flexibilidade para o compilador na alocação de registradores para
as variáveis de programa. Esta flexibilidade advém do fato de que o gerenciamento da janela
de registradores não é amarrado a instruções de chamada e retorno de função, como ocorre nas
máquinas RISCs da Berkeley. Além disso, o SPARC inclui instruções adicionais para ambiente multiprocessados, utilização de co-processador e unidades de ponto flutuante que não eram
previstas nos projetos RISC I, RISC II e SOAR.
O SPARC tem alta flexibilidade e desempenho podendo ser utilizado em diversas áreas como
na computação militar, fotografia digital, computação aeroespacial, processamento de imagens,
CAPÍTULO 4. SPARC V8
17
computação empresarial, notebooks e desktops, telecomunicações, redes, eletro-eletrônicos etc.
Em 1989, a Sun Microsystem transferiu a posse das especificações de SPARC a uma organização independente, a SPARC internacional, que administra, licencia a tecnologia e realiza testes
de conformidade e outros serviços para seus membros. Esta iniciativa da Sun visava estimular as
empresas a criarem a sua própria arquitetura SPARC.
Neste capítulo, será apresentada uma implementação da arquitetura SPARC V8 para a plataforma STORM. Será descrito: o conjunto de instruções e registradores, o modelo de memória, os
modos de operação e endereçamento do processador, tratamento de interrupções e as decisões de
projeto adotadas nesta implementação em particular e outros detalhes relevantes ao projeto. Por
fim, será apresentado o modelo de sistema de cache desenvolvido para o SPARC. Este sistema de
cache foi desenvolvido para apresentar a maior flexibilidade possível. Tendo vários algoritmos
de substituição e modos de mapeamento.
4.1
A Arquitetura SPARC V8
A arquitetura de um processador pode ser definida por meio de seu conjunto de instruções e pela
organização do seu conjunto de registradores. Assim, não há uma implementação de hardware
específica, vários projetos de hardware podem implementar a mesma arquitetura.
A arquitetura SPARC define o conjunto de instruções, a estrutura dos registradores e os tipos
de dados para um unidade inteira e para uma unidade de ponto-flutuante de acordo com o padrão
IEEE 754 [19]. Características como utilização ou não de barramento, gerência de memória, uso
ou não de cache interna, número de estágios do pipeline, tipo de lógica de controle e tecnologia
de implementação não são definidas e ficam dependente da implementação.
Entretanto, vale a pena ressaltar que a compatibilidade binária é mantida pela definição da
arquitetura. Isto permite a execução de um mesmo código em sistemas de portes bem variados e
independente da tecnologia utilizada no desenvolvimento.
A arquitetura do SPARC V8 é um exemplo de RISC (Reduced Instruction-Set Computer) de
32 bits. O SPARC é organizado logicamente em três unidades distintas: a IU (integer unit), a
FPU (floating-point unit) e o co-processador (CP), cada uma com os seus próprios registradores,
permitindo máxima concorrência na execução de instruções das três unidades. A Figura 4.1
mostra essas três unidades e a D-Cache, cache para dados, a I-Cache, cache para instruções, e
ainda uma RAM local.
O SPARC utiliza o modelo de execução registrador-para-registrador, ou seja, todos os acessos à memória são feitos via registradores e todas as instruções envolvem registradores. Ou
18
Figura 4.1: Visão geral da Arquitetura SPARC V8.
seja, neste modelo de execução nenhuma unidade envia ou recebe informações para memória
diretamente via algum barramento ou rede de conexão externa.
A IU controla toda as operações do processador. Ela executa instruções lógicas e aritméticas
com números inteiros, instruções de acesso à memória, atualiza o contador de programa (PC)
e ainda controla a execução da FPU e do co-processador. Para auxiliar na execução de todas
essas tarefas, a IU conta com um total de 40-520 registradores, dependendo da implementação.
A Figura 4.2 mostra a IU.
Figura 4.2: Visão geral do SPARC.
19
Embora o pipeline de instruções de cinco estágios não seja uma característica obrigatória em
um implementação de um processador SPARC V8, a maioria delas apresenta-o em cinco estágios: Busca (B), Decodificação (D), Execução (E), Memória (M) e Escrita (W). Durante a Busca,
instruções são movidas da memória para o processador. No estágio de Decodificação, o processador lê operandos do conjunto de registradores, decodifica instruções e detecta dependências
entre instruções.
Os operandos entram na ULA (unidade lógica e aritmética) ou na unidade de deslocamento
(shift) no estágio de Execução. Instruções de load e store buscam operandos na memória no
estágio de Memória. No estágio de escrita, o processador escreve o resultado da ULA ou o
dado da memória no conjunto de registradores. Assim que uma instrução entra no pipeline, ela
é executada em 5 ciclos. Se o pipeline estiver cheio, uma nova instrução é terminada em cada
ciclo do clock.
A FPU tem 32 registradores de 32 bits. Valores que necessitam de maior precisão podem ocupar mais de um registrador. Os formatos e dados de ponto flutuante estão de acordo com o padrão
ANSI/IEEE 754-1985 [19]. Entretanto, o SPARC não requer que todos os aspectos desse padrão
sejam implementados em hardware, podendo ser emuladas por software as funcionalidades não
presentes no hardware.
Nos casos em que a FPU não esteja presente na implementação ou não esteja habilitada, o bit
enable floating (EF) no registrador de estado do processador (Processor Status Register - PSR) é
zero. Qualquer tentativa de executar uma instrução de ponto flutuante irá gerar uma interrupção
de ponto flutuante - fp_disabled. Nos outros cacos, o software deve emular uma instrução de
interrupção de ponto flutuante.
A arquitetura SPARC V8 suporta um único co-processador. Ele tem o seu próprio conjunto
de registradores, geralmente são registradores de 32 bits. Para mover dados dos registradores
entre o co-processador (CP) e a memória, há instruções de load/store.
Se o co-processador não está presente na implementação ou não está habilitado, o bit enable_coprocessor (EC) no PSR é zero, a interrupção cp_disabled deve ser gerada caso haja uma
tentativa de executar instruções que envolva o co-processador. Os registradores da FPU e do
co-processador são acessados, unicamente, através das instruções de load e store. Não existe
nenhum caminho direto entre a IU e a FPU ou entre a IU e o CP, que permita este acesso.
4.1.1
Formato de Instruções
As instruções do processador SPARC V8 são codificadas em três formatos de 32 bits. Os operandos aparecem em posições fixas para permitir acesso rápido aos registradores. Na Figura 4.3,
20
pode-se ver que o formato 1 é usado somente pela instrução Call. Este formato permite um deslocamento de 30 bits em relação ao PC, gerando um deslocamento arbitrário em apenas uma instrução. O formato 2 é usado para as instruções Sethi e Branches (Bicc - desvio condicional, FBfcc
- desvio sob condição de ponto flutuante e CBccc - Desvio sob condição do co-processador). A
instrução Sethi é um instrução especial usada principalmente para armazenamento de um valor
de 32 bits em registrador. Já o formato 3 suporta as outras instruções. O formato 3 com op = 3
dá suporte às instruções de memória, e com op = 2, às instruções aritméticas, lógicas, shift e as
restantes.
Figura 4.3: Formatos de instruções
4.1.2
Conjunto de Instruções
O conjunto de instruções do SPARC pode ser dividido em seis categorias: instruções de load/store,
instruções lógicas, aritméticas e shift, instruções de transferência de controle, instruções de
controle de leitura e escrita em registradores, operações de ponto flutuante e operações de coprocessador. A Tabela 4.1 mostra essas categorias.
A maioria das instruções do SPARC usa apenas operandos em registradores. Tais Instruções
podem ser expressas da seguinte forma:
Rd ← Rs1 op S2
Onde Rd e Rs1 são referências a registradores; S2 pode referenciar um registrador ou ope-
Categoria
Instruções Load/Store
Instruções
Aritméticas/Lógicas/
Shift
Instruções de
transferência de controle
Instruções de controle de
leitura e escrita
em registradores
Instruções de ponto flutuante
Instruções de co-processador
21
Descrição
Únicas instruções a acessarem a
memória.
Com exceção da instrução Sethi,
essas instruções computam um
resultado que é uma função de
dois operandos.
Incluem branches, chamadas a
funções (Call), saltos e
interrupções condicionais.
Usadas para a leitura e escrita
do conteúdo de registradores
visíveis ao software.
Realizam cálculos ponto flutuante
Se o CP está presente, essas
instruções são definidas por sua
implementação.
Tabela 4.1: conjunto de instruções do SPARC.
rando imediato de 13 bits. Essa forma é bastante adequada para programas que têm alta proporção de constantes e variáveis locais escalares.
4.1.3
Conjunto de Registradores
O processador SPARC tem dois tipos de registradores: registradores de propósito-geral e registradores de controle e status. A IU contém 32 registradores de propósito geral sempre visíveis ao
programa . Desses, 8 são globais e os outros 24 organizados na forma de janela de registradores.
Uma implementação do processador SPARC pode ter de 2 a 32 dessas janelas, variando de 40 a
520 o número de registradores.
Uma janela de registradores consiste em três grupos de três registradores, chamados in, out
e local. Os registradores do tipo in e out são usados para passagem de parâmetros de funções e
receber resultados delas. Os registradores do tipo local são utilizados para variáveis automáticas.
A cada momento, somente uma janela está visível, determinado pelo CWP (current window
point) que é parte do PSR (processor status register). O CWP é um valor de 5 bits que pode ser
decrementado pela instrução SAVE e incrementado pela instrução RESTORE. Essas instruções
são para salvar e recuperar o estado do processador, respectivamente, sendo geralmente executas
em chamadas a funções e retorno dessas. Assim, o grupo de registradores in contém os parâmetros de entrada, o grupo local, os registradores usados dentro da função e o grupo out, os
22
resultados de saída.
As janelas de registradores se sobrepõem parcialmente. Dada uma janela de registradores
atual, se uma instrução RESTORE for executada, CWP será incrementado e o grupo de registradores in da janela atual será o grupo out da próxima janela. Caso contrário, se a instrução SAVE
for executada, CWP será decrementado e o grupo de registradores out da janela atual passa a ser
o grupo in dessa próxima janela. Para ilustrar esse procedimento, considere a Figura 4.4.
Figura 4.4: Janela de Registradores.
Múltiplas janelas provêem maior agilidade nas chamadas de funções e trocas de contexto,
uma vez que, elas evitam a necessidade de salvar o estado atual do processador na memória durante estas operações. Isto reduz o trafego off-chip1 e é particularmente eficiente em linguagens
orientadas a objetos como C++ e Java, pois a programação orientadas a objetos, freqüentemente,
resulta em programas com um grande número de pequenas chamadas a funções.
As variáveis de estado são salvas na janela atual, e uma nova janela é aberta para uma nova
função. Note que a passagem de parâmetros é feita sem movimentação física de dados.
1
O Tráfego off-chip é o tráfego entre o processador e qualquer unidade externa
23
Há também os registradores para controle e status da IU que incluem PSR (Processor State
Register), WIN (Window Invalid Mask), TBR (Trap Base Register), PC e nPC (Program Counters).
O registrador PSR contém vários campos para o controle do processador e para armazenar
informações sobre o seu status. Já o WIN é controlado pelo software supervisor e usado pelo
hardware para determinar se houve uma interrupção de overflow ou de underflow causada por
uma instrução Save, Restore ou Rett. O registrador TBR armazena um endereço para o qual
o controle é transferido em caso de ocorrência de interrupção. O PC contém o endereço da
instrução que está sendo executada no momento e o nPC, o endereço da próximo instrução a ser
executada.
A organização em janelas de registradores possui várias vantagens em relação ao conjunto
fixo de registradores. A principal vantagem é a redução do número de instruções load/store
necessárias para a execução do programa. Isto implica em uma redução na taxa de falta da cache
de dados.
Para programas longos em C, estima-se que 20% das instruções sejam instruções de load/store,
incluindo o overhead de processamento dos overflow/underflow das janelas. Em arquiteturas
RISCs sem janelas de registradores, este número sobe para algo entre 30% a 40% das instruções
[8].
4.1.4
Formatos de Dados
A arquitetura SPARC reconhece três tipos fundamentais de dados
• Inteiro com sinal - 8, 16, 32 e 64 bits.
• Inteiro sem sinal - 8, 16, 32 e 64 bits.
• Ponto flutuante - 32, 64 e 128 bits.
O tamanho dos formatos são:
• Byte - 8 bits.
• Halfword - 16 bits.
• Word - 32 bits.
• Tagged Word - 32 bits.
24
• Doubleword - 64 bits.
• Quadword - 128 bits.
Os formatos de inteiro com sinal codificam apenas números inteiros em complemento de
dois. Os formatos de inteiro sem sinal são formatos de propósito geral e não codificam nenhum
tipo de dado em particular. Eles podem ser usados para representar string, valores booleanos,
números inteiros, frações e etc. Os formatos com tag definem palavras nas quais os dois bits
menos significativos são utilizados como tag. Finalmente, os formatos de ponto flutuante são
definidos de acordo com o padrão ANSI/IEEE 754-1985 [19].
4.1.5
Modo Usuário e Modo Supervisor
A arquitetura SPARC suporta dois modos de operações: o modo supervisor, que é o modo de
operação do sistema operacional e tem acesso a todo conjunto de instruções; e o modo usuário,
que é o modo de funcionamento das aplicações do usuário. Qualquer tentativa de executar uma
operação de modo supervisor em uma aplicação de modo usuário causa uma interrupção. Os
modos de operação delimitam não apenas um conjunto de instruções diferenciados, mas também
espaços de endereçamento de memória diferenciados.
A existência deste dois modos de operação é fundamental para a colocação de um sistema
operacional na STORM.
4.1.6
Modelo de Memória
O modelo de memória do SPARC define a semântica das operações tais como load e store, e
especifica como a ordem em que estas operações são emitidas por um processador é relacionada
com ordem em que são executados pela memória. Especifica também como as instrução buscadas
pelo SPARC são sincronizados com as operações de memória.
O modelo de memória padrão do SPARC é conhecido como Total Store Order (TSO). Este
modelo pode aplicado tanto em ambientes uniprocessados como em ambientes multiprocessados
com memória global compartilhada, como é o caso da STORM.
O modelo garante que as operações de store, FLUSH e atomic load-store de todos os processadores são executadas pela memória de modo serial e na mesma ordem em que foram emitidas
pelo processador.
Para o SPARC, a memória é uma coleção de endereços acessados via instruções load/store.
Esta coleção de endereços inclui a memória tradicional, os registradores de entrada e saída e
25
registradores especiais do SPARC. Dentro desta coleção, define-se uma região especial chamada
de memória principal ou real que contém a área de instruções e dados do usuário e do sistema
operacional. Esta área é livre de efeitos colaterais; isto é, um load, store ou atomic load-store em
um endereço dentro desta área não tem nenhum efeito visível exceto nesta posição.
O SPARC utiliza entrada e saída mapeadas na memória. Neste esquema, cada registrador de
controle de dispositivos de E/S é associado de maneira unívoca a um endereço de memória. O
modelo de memória do SPARC define que os registradores de E/S não estão na memória real.
O acesso a estes registradores pode ser feito através de instruções load/store, instruções de coprocessador e instruções de leitura e escrita nos ASR (Ancillary State Register). Os ASRs são
registradors de controle e de status da IU.
4.1.7
Modos de Endereçamento
Os modos de endereçamento do SPARC são: endereçamento de registrador e modo de deslocamento. No primeiro modo, o campo de endereço refere-se a um registrador. Enquanto que no
segundo modo de endereçamento, o campo de endereço consiste em um deslocamento relativo a
um endereço contido em um registrador [18]:
EA = (Rs1 ) + S2
ou EA = (Rs1 ) + (Rs2 )
Dependendo se o segundo operando é um valor imediato ou uma referência a registrador. Onde
Rs1 e Rs2 são referências a registradores, e S2 é um operando imediato de 13 bits. O modo de
endereçamento via deslocamento é muito flexível e pode emular outros modo de endereçamento
como mostra tabela a seguir:
Modo
Algoritmo
Equivalente SPARC
Imediato
operando = A
S2
Direto
EA = A
R 0 + S2
Registrador
EA = R
Rs1 ,Rs2
Indireto
EA = (R)
Rs1 + 0
Deslocamento EA = (R) + A
Rs1 + S2
Tabela 4.2: Equivalente SPARC de outros modos de endereçamento.
Onde A é conteúdo do campo de endereço da instrução, R é o conteúdo de campo de endereço
que referencia um registrador. EA é endereço real e (R) indica o conteúdo da posição dada por
R.
4.1.8
26
Tratamento de Interrupções
O fluxo de execução do SPARC é baseado no modelo seqüencial, mas uma implementação da
arquitetura SPARC com pipeline de instruções pode modificar o estado do processo em uma
ordem diferente da definida pelo modelo seqüencial. Em decorrência disto, a ocorrência de uma
interrupção pode deixar o hardware em um estado que não é consistente com nenhum valor
especificado pelo contador de programa [15].
Quando uma interrupção ocorre, o estado do processo é salvo pelo hardware ou pelo software.
Neste trabalho, o contexto é salvo pelo hardware. As interrupções podem ser precisas, imprecisas
ou externas. Uma interrupção é dita precisa se obedece às seguintes propriedades:
• Todas as instruções anteriores à instrução apontada pelo contador de programa foram completamente executadas e modificaram o estado do processo corretamente.
• Todas as instruções após a instrução apontada pelo contador de programa não foram executadas e não modificaram o estado do processo.
• Se uma interrupção é causada por uma exceção em uma instrução do programa, o contador
de programa salvo aponta para a instrução interrompida. E esta instrução deve ter sido
completada ou não iniciada.
Se o estado do processo salvo é inconsistente com o modelo seqüencial da arquitetura e não obedece a alguma das condições acima, então a interrupção é dita imprecisa. Por fim, as interrupções
externas são exceções que não tem relacionamento com a execução de nenhum instruções anterior, como interrupções de I/O ou time.
A arquitetura SPARC determina que todas as interrupções devem ser precisas com 4 exceções: exceções de Ponto-Flutuante e de co-processador, exceções ocorridas devido a erro de
hardware, exceções devido a interrupções externas e exceções causadas após o primeiro acesso
de uma instrução de acesso múltiplo a memória, como load/store double, atomic load store ou
SWAP.
As interrupções são controladas principalmente por dois registradores: o PSR e o FSR (FPU
Status Register). O campo ET (Enable Trap) PSR habilita as interrupções da IU e o campo
TEM (FSR Trap Enable Mask) do FSR habilita as interrupções da FPU. As prioridades das
interrupções são estabelecidas pelo campo PIL (Processor Interrupt Level) no PSR.
O SPARC utiliza uma esquema de transferência de controle para o sistema operacional baseado em uma tabela. Esta tabela, denominada de tabela de interrupções, contém as quatro
primeiras instruções das rotinas de tratamento das interrupções. O endereço de início da tabela
27
é armazenado no TBR ( Table Base Register). O TBR contém um campo denominado tt (Trap
Type) que identifica unicamente cada interrupção. Este campo é usado para indexar a tabela de
interrupções no processo de transferência de controle.
Quando ocorre uma interrupção de qualquer natureza e as mesmas estão habilitas, as seguinte
ações ocorrem: As interrupções são desabilitadas, ou seja, ET ← 0; O modo de operação
do processador é salvo; o processador entra no modo supervisor; uma nova janela é aberta; o
contexto do processador é salvo; o campo tt é gravado pelo hardware no TBR e o controle é
transferido para a o endereço que tabela de interrupções aponta.
Caso as interrupções estejam desabilitadas e uma interrupção precisa ocorre, o processador
suspende a execução da instrução corrente. O tratamento de interrupções imprecisas é dependente da implementação. O presente trabalho prevê o tratamento de interrupções precisas e
externas. O tratamento de interrupções imprecisas não foi abordado, pois ainda não existem
módulos executando paralelamente a unidade inteira. Desta maneira, a existência de interrupções imprecisas só ocorreriam devido a erros de hardware, entretanto estes problemas não são
simulados.
4.1.9
Instruções de LDSTUB e SWAP
Em ambientes mono-processados multi-tarefas ou de processamento paralelo há a necessidade
de evitar a ocorrência de condições de corrida (race condition)2 e gerenciar o sincronismo entre
processos.
A habilidade fundamental para realizar a sincronização em ambientes multiprocessados é a
capacidade de ler e escrever de forma atômica em uma posição de memória. Sem tal recurso, o
custo de construir primitivas de sincronização aumentaria com o aumento do número de processadores [10].
A STORM necessita de um mecanismo de Test-and-Set para evitar as condições de corrida
e realizar o sincronismo entre processos. O mecanismo de Test-and-Set é implementado no
SPARC usando-se as instruções LDSTUB (Atomic Load-Store) e SWAP. A primeira realiza uma
leitura e em seguida uma escrita de forma átomica, enquanto que a segunda troca o conteúdo
de registrador e de uma posição de memória de forma atômica. Quando um processo deseja
entrar em uma determinada região crítica, ele executa a instrução LDSTUB. Tal instrução lê uma
posição da memória e, em caso esta seja ’0’, modifica seu valor para ’-1’. Caso contrário não
faz nada. Quando o processo desejar deixar a região crítica, ele executa a instrução SWAP que
2
Condições de corrida são situações em que dois ou mais processos estão acessando dados compartilhados e o
resultado depende da ordem de execução dos mesmos.
28
escrever novamente ’0’ na posição de memória para indicar que a região está livre. Note que
esta solução deixa a cargo do programador a definição das regiões críticas da aplicação através
do uso de monitores ou semáforos.
4.1.10
Sincronismo das Instruções
A arquitetura SPARC é aberta e não define o caminho de dados do pipeline que implementa o
conjunto de instruções. Isto implica em decisões de projeto que são visíveis ao nível de software.
O principal efeito da implementação do pipeline é o número de ciclos necessário para execução
das instruções. A Tabela 4.3 mostra estes valores para esta implementação.
Instrução
Número de Ciclos
Load single, taken ticc, JMPL, RETT
2
Load double, store single, untaken Ticc
3
Store double, LDSTUB, SWAP
4
Todas as outras instruções
1
Tabela 4.3: Número de ciclos gasto para execução de instruções.
Na primeira linha da Tabela 4.3 temos o tempo em número de ciclos para realizar carga de
uma palavra na memória, tomada de saltos condicionais sob condições inteiras e para saltos e
retorno de funções. Na segunda linha temos o número de ciclos gastos para realizar carga dupla,
armazenar uma palavra e executar um salto condicional não tomado. Na penúltima linha, temos
o tempo para armazenar uma palavra dupla e realizar as instruções de test-and-set. Todas as
outras instruções da IU gastam 1 ciclo para executar.
4.1.11
Mecanismos de bypassing
Bolhas no pipeline também podem ser causadas devido à ocorrência de uma instrução que necessite de dados que estão prontos mas ainda não estão disponíveis nos registradores. Por exemplo,
considere um pipeline de cinco estágios e a seguinte sequência de instruções:
ADD %g1, %g2, %g3
SU B %g4, %g1, %g5
Na situação acima, imagine que a primeira instrução tem sua execução iniciada no instante
t0 e que a segunda instrução inicie no tempo t1 . Note que, a segunda instrução necessita do
29
resultado da primeira instrução na sua fase de decodificação no instante t2 . Entretanto a primeira
instrução grava o resultado no seu estágio de escrita no instante t4 . A situação apresentada
provoca uma bolha no pipeline.
Para evitar a ocorrência deste tipo de bolha a arquitetura proposta conta com um mecanismo
de bypassing entre os estágios de decodificação, execução e memória. Este mecanismo funciona
da seguinte maneira:
1. O resultado das unidades de decodificação, execução e memória são encaminhados à entrada da unidade anterior no pipeline e realimenta a própria unidade.
2. Se o hardware de bypassing detectar que a instrução executada anteriormente na unidade
alterou algum registrador de origem da instrução atual, a lógica de controle seleciona o
resultado encaminhado como entrada da unidade e não o valor lido dos registradores.
A Figura 4.5 ilustra o mecanismo de bypassing.
Figura 4.5: Mecanismo de bypassing.
4.1.12
Previsão de Desvios
Para evitar bolhas no pipeline devido à hazards de desvios, uma instrução é buscada a cada
ciclo de clock para manter o pipeline cheio. No caso de instruções de desvios, considera-se que
o desvio não foi tomado, assim a execução continua seqüencial. Se o desvio for tomado, as
instruções que estão no pipeline são descartadas automaticamente.
30
Nas arquiteturas SPARC, os desvios representam cerca de 20% das instruções executadas
[14]. Logo diminuir a penalidade no caso de uma previsão errada significa um melhor desempenho da arquitetura. Uma técnica para conseguir esta redução é mover a avaliação e execução
do desvio para o estágio de decodificação. Isto permite que o atraso na execução de desvios
tomados seja de apenas um ciclo.
4.1.13
Unidade de Controle Distribuída
A unidade de controle da arquitetura é distribuída pelos estágios. Desta maneira, cada estágio do
pipeline coordena a suas atividades e se comunica via sinais com os outros estágios. Os controles
embutidos nos estágios de busca e decodificação realizam o gerenciamento e o despacho de
instruções para o estágio de execução.
Entretanto, a parte principal do controle está na máquina de estados finitos localizada no
estágio de execução. Esta máquina de estados controla todas as ações necessárias para a execução das instruções, produz os sinais de controle para os outros estágios e determina o modo de
operação do processador.
4.2
O Sistema de Caches
A cache é o nome dado ao primeiro nível de hierarquia de memória encontrado assim que o
endereço deixa o processador [10]. A memória cache é uma pequena memória estática de alto
desempenho, cujo finalidade é aumentar o desempenho do processador realizando uma busca
antecipada na memória RAM com base nos princípios da localidade temporal e espacial. O uso
de memória cache é feito desde que o acesso à memória principal tornou-se muito custoso por
causa da diferença entre os períodos de relógio do processador e da memória [21].
O princípio da localidade temporal nos diz que o dado usado mais recentemente tem grande
probabilidade de ser acessado novamente num futuro próximo. Já o princípio da localidade
espacial nos diz que os dados adjacentes ao dado requisitado tem alta probabilidade de serem
utilizados no futuro.
O SPARC possui uma arquitetura de cache Harvard [17] com barramento de endereços e
dados separados, conectados a dois controladores de cache separados. Esta divisão na cache é
comum à maioria das arquiteturas pipeline atuais pois possibilita acessos simultâneos a instruções e dados.
A Cache de Instruções é dedicada a armazenar as instruções executadas pelo processador
mais recentemente. A Cache de Instruções é acessada exclusivamente pelo módulo de Busca do
31
processador. Tal cache não tem permissão de escrita nos dados armazenados por ela.
A Cache de Dados é destinada ao armazenamento dos dados mais recentemente acessados
pelo SPARC. A cache de dados possui suporte ao mecanismo de coerência de cache da plataforma STORM [16]. Este mecanismo exige que a mesma tenha para cada linha da cache, um
bit de permissão de escrita, que indicam se uma operação de escrita pode ser feita sobre uma
dada linha. Além disso, a cache deve ser capaz de atender as requisições de invalidação e enviar
blocos editados para o diterório associado a ela.
As caches possuem endereçamento real de 32 bits. Para endereçamento extra, o processador
provê um identificador de espaço de endereçamento de 8 bits (do inglês, ASI - Address Space
Identifier), produzindo até 256 diferentes espaços de endereçamento de 32-bits.
Durante o modo normal de operação o processador trabalhar acessando instruções e dados
utilizando um ASI de 0x08 a 0xB como definido no padrão SPARC. Utilizando instruções LDA
(Load Word from Alternate space) e STA (Store Word into Alternate space), os espaços de endereçamento extras podem ser utilizados. Na Tabela 4.4 temos a divisão do espaço de endereçamento do SPARC.
ASI
Espaço de Endereçamento
0x00 - 0x07 Dependente da implementação
0x08
Instruções do modo usuário
0x09
Instruções do modo supervisor
0x0A
Dados do modo usuário
0x0B
Dados do supervisor
0x0C - 0xFF Dependente da implementação
Tabela 4.4: Identificadores de espaço de endereçamento.
Os espaços de endereçamento acessados via as instruções LDA e STA podem ser usado pelo
software supervisor para acessar registradores especiais, como MMU, controladores de caches,
registradores de espaço de endereçamento dentre outros.
A cache proposta neste trabalho foi projetada para ser altamente parametrizável permitindo
escolher o modo de mapeamento, configurar o tamanho do bloco, o tamanho da linha e o tamanho
da cache. O único parâmetro fixo é a política de atualização da cache que segue o padrão definido
durante a concepção do projeto STORM. A seguir, apresentamos uma breve explicação sobre
cada parâmetro da cache.
4.2.1
32
Mapeamento
Dado que o número de linhas da cache é menor do que o número de linhas da memória é necessário um algoritmo para mapear as linhas da memória em blocos da cache. Esta função de
mapeamento determina como a memória cache é organizada. Existem três técnicas básicas para
fazer este mapeamento: O mapeamento direto, mapeamento completamente associativo e o mapeamento associativo por conjunto. A seguir temos uma breve descrição de cada técnica citada.
• Mapeamento Direto: Neste tipo de mapeamento um linha da memória principal é mapeado em uma único bloco da cache. Pode-se expressar este mapeamento através da seguinte
expressão:
i = j modulo m
Onde i é o número da linha da cache, j é o número da linha da memória e m é o tamanho
da cache. É um esquema simples e de baixo custo de implementação. Entretanto, se
um programa fizer referência a duas linhas distintas da memória principal mapeadas na
mesma linha da cache, haverá uma menor taxa de acerto na cache, uma vez que, elas serão
constantemente substituídas.
• Mapeamento Completamente Associativo: O mapeamento completamente associativo
permite que uma linha da memória seja mapeada em qualquer posição da cache. Isto implica em maior flexibilidade. Porém, este tipo de mapeamento necessita varrer toda as
linhas da cache, o que pode degradar o desempenho da mesma. Em algumas implementações, adiciona-se um complexo hardware para realizar todas as comparações em paralelo.
Entretanto isto aumenta o custo e a complexidade da cache.
• Mapeamento Associativo por Conjunto: Neste tipo de mapeamento, a memória é dividida em v conjuntos cada um com k linhas. Desta maneira, uma linha da memória é
mapeada em um conjunto e depois inserida na cache em qualquer linha deste conjunto.
Este mapeamento pode ser expresso pelas funções:
m = vxk
i = j mod v
Uma das diretrizes do projeto baseado em plataforma é utilizar componentes altamente parametrizáveis. Devido a este fato, a cache proposta implementa o mapeamento associativo por
conjunto. Este tipo de mapeamento permite emular os outros dois tipos de mapeamento. Note
33
que se o número de linhas de cada conjunto for igual a um e o número de conjunto for igual ao
número de linhas da cache, temos o mapeamento direto. E se o número de conjuntos for igual
a um e o número de linhas de desse conjunto for igual ao número de linhas da cache, temos um
mapeamento completamente associativo.
4.2.2
Política de Substituição
Quando a cache enche e ocorre uma falha, o controlador da cache deve escolher um bloco para
ser substituído pelo bloco desejado. Caso a cache seja diretamente mapeada não é necessário
nenhum algoritmo específico para determinar qual bloco substituir pois o próprio mapeamento
determina o bloco a ser retirado. Por outro lado, em caches completamente associativas ou
associativas por conjunto, há vários blocos que são candidatos a sair da cache. É evidente que se
deseja uma política que maximize a taxa de acerto da cache (hit rate).
O sistema de cache proposto neste trabalho possui vários algoritmos de substituição que
foram desenvolvidos juntamente com a aluna Tássia Aparecida Vieira de Freitas, aluna deste
mesmo departamento. A seguir temos uma breve descrição sobre cada algoritmo implementado.
4.2.2.1
LFU (Least Frequently Used):
Esta política utiliza o histórico de acesso para prever a probabilidade de uma referência subseqüente. Desta maneira, o algoritmo LRU substitui a linha menos freqüentemente utilizada.
Para isto, o LFU mantém um contador de acesso para cada linha da cache.
Infelizmente, linhas muito freqüentemente utilizadas em um passado próximo e que não serão utilizadas novamente tendem a permanecerem na cache, impedindo que blocos mais novos
tenham freqüências suficientes para permanecerem na cache. Este fenômeno é conhecido como
poluição da cache. Tal fenômeno provoca um aumento da taxa de falta da cache devido ao
número de dados inicializados.
4.2.2.2
LRU (Least Recently Used):
Esta política explora o princípio da localidade temporal e substitui a linha menos recentemente
utilizada na suposição que esta linha não será utilizada em um futuro próximo, ou seja, a política
LRU utiliza apenas o intervalo de tempo desde o último acesso as linhas da cache e não considera
a freqüência de acesso a tais linhas ao fazer a decisão de realocação.
Esta política é eficiente, porém cara para cache grandes, devido a necessidade de mater o
histórico de acesso das linhas da cache. Além disso, para caches grandes, avaliar todos os blocos
34
para escolher aquele que deve ser retirado da cache, pode consumir muito tempo, o que aumenta
o tempo de resposta da cache.
Devido ao alto desempenho deste algoritmo, ele é largamente utilizado em gerenciamento de
buffers de banco de dados, sistemas de arquivos, gerenciamento de memória virtual, proxy de
internet dentre outras aplicações.
4.2.2.3
Pseudo-LRU:
O algoritmo LRU tradicional é de fácil implementação para caches pequenas mas torna-se computacionalmente caro para caches grandes. O algoritmo Pseudo-LRU é uma aproximação do
algoritmo LRU de implementação computacionalmente mais barata.
O algoritmo Pseudo-LRU funciona da seguinte maneira: Constrói-se uma árvore binária de
decisão para cada conjunto da cache. Nas folhas de tal árvore estão as linhas e nos nós intermediários os pontos de decisão. Nos nós não-folha, o valor 1 indica que o filho esquerdo
foi referenciado mais recentemente do que o direito. E o valor 0 indica que o filho direito foi
referenciado mais recentemente do que o esquerdo.
Durante o processo de substituição percorre-se a árvore procurando o elemento menos recentemente utilizado. Para atualizar a árvore durante um acerto em linha da cache, basta percorrer
o caminho que leva a linha em questão, e durante a travessia, alterar a flag de cada nó não folha para indicar a direção oposta a atual. A Figura 4.6 ilustra está abordagem para uma cache
conjunto-associativo com fator de associatividade 4.
Figura 4.6: Árvore de decisão do pseudo-LRU.
35
Note que são necessários apenas n-1 bits para uma cache de associatividade n. Quando uma
falta ocorre, os bits de estado permanecem inalterados e a decisão sobre qual linha deve ser
retirada da cache ocorre com na base no estado atual da árvore. A Tabela 4.2.2.3 mostra os
possíveis estados para a árvore da Figura 4.6 e a linha a ser substituída em cada caso.
Estado Atual Substituir
00x
linha 0
01x
linha 1
1x0
linha 2
1x1
linha 3
Tabela 4.5: Representação da árvore binária em forma de string de bits.
Na tabela acima, o símbolo “x” representa o valor “don’t care”. Tabela 4.2.2.3 mostra como
ocorre o processo de atualização dos bits de estado quando ocorre um acerto na cache.
Estado Atual Próximo Estado
linha 0
11_
linha 1
10_
linha 2
0_1
linha 3
0_0
Tabela 4.6: Atualização dos bits de estados.
Note que quando as linhas 0 e 1 são acessadas, o bit 0 é colocado em 1 e o bit 3 permanece
inalterado. O segundo bit decide se o acesso é para linha 0 ou para a linha 1. Na tabela acima, o
símbolo “_” indica que o bit permanece inalterado.
4.2.2.4
SLRU (Segmented Least Frequently Used):
O algoritmo SLRU considera tanto a freqüência quanto a recenticidade de um bloco durante o
processo de substituição. O SLRU divide a cache em dois segmentos: Um segmento protegido
para armazenar dados que são acessados freqüentemente e um segmento não-protegido para dados acessados apenas uma única vez. As linhas em cada segmento são ordenadas de acordo com
a política LRU. Ou seja, da linha mais acessada para a menos acessada recentemente. Quando um
objeto é acessado pela primeira vez, o mesmo é adicionado no segmento não-protegido. Quando
ocorre um acerto em uma linha da cache, a mesma é movida para o segmento protegido.
A migração de uma linha do segmento não protegido para o segmento protegido deve forçar
a migração da linha menos usada recentemente do segmento protegido para o segmento nãoprotegido. Desta maneira, a linha removida do segmento protegido terá uma nova chance de
36
ser acessada antes de ser substituída. Durante o processo de substituição somente as linhas que
estão no segmento não-protegido podem ser escolhidas. A Figura 4.7 mostra o fluxo lógico de
migração das linhas da cache.
Figura 4.7: Fluxo lógico de uma cache SLRU.
Este algoritmo protege a cache de padrões de acesso que podem inundar as caches LRU com
dados que não serão reusados, o que pode provocar o descarte de linhas que tem alta probabilidade de serem reusadas. Por exemplo, em operações de backup ou em acessos a longos arquivos
de dados seqüenciais, vários dados serão utilizados apenas uma única vez [12]. O problema se
agrava quando as linhas dentro deste padrão de acesso representam uma fração significativa da
carga de trabalho e o tamanho da cache é pequeno.
Isto ocorre porque o LRU não considera a freqüência de uso dos dados. Este problema é
amenizado pelo algoritmo SLRU, pois ele leva em consideração a freqüência e a recenticidade
do bloco durante o processo de substituição. Desta maneira, o SLRU reconhece as linhas que
podem ser acessadas múltiplas vezes e as linhas que podem ser acessadas apenas uma única vez.
4.2.2.5
37
FIFO (First-In-First-Out):
Este algoritmo consiste em substituir o bloco que foi carregado há mais tempo na cache. É
uma política de fácil implementação e de baixo custo. Entretanto, por não considerar se a linha
substituída estava sendo muito utilizado ou não, um aumento no tamanho da cache pode provocar
uma aumento na taxa de falta da cache (miss hate). Esta deficiência do algoritmo é denominada
anomalia de Belady [3].
4.2.2.6
GreedyDual:
Este algoritmo é focado para sistemas onde o tamanho do dado a ser buscado é fixo, mas o
custo de buscá-lo é diferente. No caso da STORM, se a instância da plataforma possuir vários
diretórios, o custo de ser buscar um dado vai depender da distância entre o processador e o
diretório e da taxa de ocupação do mesmo.
O GreedyDual considera o custo e o quão recentemente este bloco foi utilizado para tomar
a decisão de substituição. O algoritmo associa um valor, denominado H, para cada linha l da
cache. Quando uma linha é carregada na cache, a H é atribuído o custo de trazer esta linha para
a cache. Quando uma substituição é necessária, a página com o menor H é escolhida para sair
e todas as outras linhas reduzem seus valores de H por Hmin . Onde Hmin é a linha com menor
custo. Quando uma ocorre um acerto em uma linha da cache, seu o valor de H é restaurado para
o custo de trazer a mesma para a cache.
Note que seria necessário K subtrações quando uma substituição é feita, onde K é o número
de linha da cache. Para evitar isso, utilizamos um valor de inflação L. Este valor irá deslocar
todos os futuros valores de H. A seguir temos o pseudo-código desta implementação:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
procedure G REEDY D UAL
while true do
if p está na cache then
H(s, p) ← L(s, p) + c(s, p)
else
L(s) ← minq∈M H(q)
carregue p na cache
c(s, p) ← custo de buscar p
H(s, p) ← L(s, p) + c(s, p)
end if
end while
end procedure
4.2.3
38
Política de Atualização
A política de atualização da cache determina quando uma alteração local será espelhada na memória principal. A cache utiliza a política de atualização de write-back. Tal política funciona
da seguinte maneira: As atualizações feitas em blocos da cache são gravadas apenas na própria cache. O bloco da cache modificado será gravado na memória principal apenas quando for
substituído da cache. Para diminuir o número de gravações na memória principal durante a substituição de um bloco, utiliza-se um bit de status que indica se o bloco em questão foi modificado
ou não. Este bit é comumente chamado de bit sujo (dirty). A idéia é que apenas blocos sujos precisam ser gravados na memória principal, pois os blocos não modificados, ditos limpos, possuem
uma cópia do dado na memória principal.
O write-back têm várias vantagens. Com o write-back, as gravações ocorrem na velocidade
da memória cache, pois não é necessário esperar que o bloco seja espelhado na memória principal. Além disso, com o write-back, várias gravações em um mesmo bloco geralmente exigem
apenas uma escrita na memória principal. Uma vez que, nem todos as gravações vão para a
memória principal, a política em questão utiliza menos largura de banda de memória. Utilizar
menos a NoC ou o barramento significa poupar energia e reduzir o tráfego off-chip.
As características citadas acima, tornam o write-back atraente em ambiente embutidos e multiprocessados como a STORM. A plataforma STORM utiliza uma política de escrita write-back
com alocação. Ou seja, quando ocorre uma falta durante um pedido de escrita de um bloco, este
bloco é alocado na cache.
4.2.4
Tamanho do Bloco
Outro parâmetro importante da cache é o tamanho dos blocos. Segundo o princípio da localidade
de referências, a vizinhança de uma palavra que acabou de ser usada tem grande probabilidade de
ser utilizada em um futuro próximo. Desta maneira, quando uma palavra é requerida pela cache
à memória principal, não apenas esta palavra é trazida, mas também um conjunto de palavras
adjacentes a palavra requerida.
Inicialmente, quando maior o tamanho do bloco, maior é a taxa de acerto na memória cache
devido ao princípio da localidade. Entretanto, a taxa de acerto na cache tende a diminuir se o
tamanho do bloco se tornar tão grande que a probabilidade de utilizar os dados buscados recentemente se tornar menor do que a probabilidade de reutilizar os dados que foram substituídos [21].
A relação entre o tamanho da cache e a taxa de acerto é complexa. Segundo Smith (1987 apud
[21]), um tamanho de bloco entre dois a oito parece estar próximo do ótimo.
Capítulo 5
Experimentos Computacionais
Este capítulo apresenta as aplicações desenvolvidas para validar o processador SPARC V8, os
módulos de caches e a metodologia de programação da STORM. Além disso, um breve estudo
sobre como o tamanho da cache, associatividade e o algoritmo de substituição afetam a taxa de
acerto da cache é apresentado.
5.1
Simulações
As simulações realizadas variam em complexidade e em propósito, o que permite uma análise
do desempenho e da aplicabilidade da plataforma em aplicações de pequeno e médio porte. As
aplicações começam em um simples cálculo do fatorial de um número, indo até uma complexa
compressão JPEG. Os resultados das simulações serão exibidos em tabelas semelhantes à esta:
Módulo
Descrição
Instruções Executadas
Quantidade de Ciclos
Ciclos por Instrução
Processador
Tempo de Execução
Ciclos/Segundos
Número de Operações
Cache de Instruções Taxa de Acerto
Ciclos de Espera
Cache de Dados
Taxa de Acerto
Ciclos de Espera
Valor
xx
xx
xx
xx
xx
x
x%
x
x
x%
x
Tabela 5.1: Template das tabelas de resultados.
CAPÍTULO 5. EXPERIMENTOS COMPUTACIONAIS
40
A primeira linha das tabelas é destinada aos dados do processador. Primeiramente, temos
“Instruções Executadas”, ou seja, o número de instruções executadas pelo SPARC. Em seguida,
“Quantidade de Ciclos” que informa a quantidade de ciclos gastos para completar a execução
da aplicação em questão. “Ciclos por instruções” ou CPI é número de ciclos gasto para realizar
cada instrução. Esta razão é dada pela seguinte fórmula matemática:
N úmero de Instrucões
Por sua vez, “Tempo de Execução” denota o tempo gasto para realizar a simulação em um
computador Pentium IV 3.0 HT com 512 MB de RAM. E por fim, “Ciclos/Segundos” é o de
número de ciclos realizados por cada segundo.
A segunda e a terceira linhas são destinadas a cache de instruções e dados respectivamente.
Tais linhas contém: “Número de operações”, Número de pedidos de leitura e escrita realizados
pela aplicação; “Taxa de Acerto”, proporção de acertos para todas as requisições; “Ciclos de Espera”, Número de ciclos que o processador para devido a faltas de leituras e escritas e operações
de coerência de cache.
Todas simulações foram realizadas com 1 processador SPARC e 1 módulo de memória interligados por uma árvore obesa. Já o sistema de cache utilizado foi composto por caches de
tamanho 8K, associatividade 1 e algoritmo de substituição FIFO. A seguir, apresenta-se cada
aplicação em ordem crescente de complexidade.
CP I =
5.1.1
Fatorial
O fatorial de um número é dado pela seguinte expressão matemática:
n! =
n
Y
k
∀n ≥ 0
k=1
Este algoritmo serviu para o teste de instruções mais simples do SPARC, como comparações,
saltos e estrutura de controles essenciais para a construções de aplicativos em linguagem de alto
nível.
Primeiramente, esta aplicação foi desenvolvida puramente em assembler SPARC. O objetivo
deste teste era verificar o processador isoladamente. Pela Tabela 5.2, nota-se que esta implementação não realizou acessos a cache de dados, pois os dados foram armazenados no próprio
conjunto de registradores do SPARC.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Taxa de Acerto
Cache de Dados
Ciclos de Espera
41
Valor
43
275
6,4
0’7"
39
45
95,56%
58
0
0%
0
Tabela 5.2: Resultados do Fatorial em assembler.
A tabela 5.2 exibe os resultados obtidos para o cálculo do fatorial de 1 até 10. Já a Tabela 5.3
apresenta a mesma aplicação, agora desenvolvida em C e compilada com o GCC. Esta segunda
simulação do fatorial permitiu verificar a integração do processador SPARC com a metodologia
de programação da STORM.
Uma comparação direta entre as duas versões do fatorial indica que o código escrito diretamente em assembly SPARC é bem mais eficiente do que o gerado pelo GCC. Por fim, pode-se
notar que esta segunda versão possui uma maior taxa de acerto na cache de instruções, entretanto
o número de instruções mais que triplicou.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Cache de Dados
Taxa de Acerto
Ciclos de Espera
Valor
145
941
6,49
0’17"
58,81
148
97,98 %
87
64
98,43 %
30
Tabela 5.3: Resultados do Fatorial desenvolvido em C.
5.1.2
42
Seqüência de Fibonacci
A seqüência de Fibonacci consiste em uma seqüência de números, tais que, definindo os dois
primeiros números da seqüência como sendo 0 e 1, os números seguintes são obtidos através
da soma dos seus dois antecessores. Matematicamente a seqüência de Fibonacci é definida pela
seguinte fórmula de recorrência:


se n = 0
 0
F (n) =
1
se n = 1


F (n − 1) + F (n − 2) outros casos
Este algoritmo foi implementado de forma recursiva e serviu para verificar as instruções de
chamada e retorno de funções, passagem de parâmetros e a verificar a alocação da pilha utilizada
durante a chamada de função. A Tabela 5.4 mostra os dados obtidos na simulação deste algoritmo
para o vigésimo primeiro elemento da seqüência de Fibonacci. Tal tabela mostra que o algoritmo
teve um bom desempenho, tendo taxa de acerto superior a 98% em ambas as caches. A execução
correta deste algoritmo validou as questões relativas a chamadas e retornos de funções.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Cache de Dados
Taxa de Acerto
Ciclos de Espera
Valor
558
3.581
6,42
0’ 13"
275,46
565
98,76%
203
331
99,03%
117
Tabela 5.4: Resultados do Fibonacci.
5.1.3
Run-length encoding - RLE
O Run-length é um simples algoritmo de compressão de dados, em que as seqüências de dados
com o mesmo valor são armazenadas com um contador e único valor. Essa técnica é muito
utilizada em dados que contém muitas seqüências de dados repetidos. Este tipo de padrão pode
ser encontrado em gráficos simples de imagens como ícones e logotipos.
43
Por exemplos, considere que temos uma linha de contendo texto plano preto em uma plano de
fundo branco. Ela terá uma longa seqüência de pixels brancos nos espaços em brancos e alguns
pixels pretos no texto. Podemos representar tal linha da seguinte forma:
W W W W W W W W W W W W BW W W W W W W W W W W W BBBW W W W W W W W W W
Se aplicarmos a compressão RLE na seqüência acima obtemos:
12W B12W 3B10W
Note que na seqüência original temos 40 caracteres contra 12 da versão comprimida, ou seja,
a versão comprimida é cerca de 3 vezes menor do que a original. O processo de descompactação
é imediato e consiste expandir a seqüência de caracteres de acordo com o valor do contador. Esta
simulação consistiu em compactar um pequeno ícone que continha 300 elementos. Os resultados
são relatados na Tabela 5.5.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Taxa de Acerto
Cache de Dados
Ciclos de Espera
Valor
29.099
162.955
5,6
0’ 26"
6.267,5
29.116
99,9%
493
8.849
99,5%
1.249
Tabela 5.5: Resultados do RLE.
Está simulação serviu para verificar a utilização de vetores na plataforma. Operações como
indexação, leitura e atribuição foram validadas ao final desta simulação. A taxa de compressão
foi de 16:1. Para carregar a imagem na plataforma, utilizou-se um programa auxiliar que coloca
a imagem em um vetor de inteiros. Este vetor é incluído no código fonte da aplicação e então
carregado na memória. Como mostra a Tabela 5.5, a cache teve uma taxa de acerto maior do que
99%.
5.1.4
44
Cifra de César
A cifra de César é um dos mais simples e conhecido algoritmo de encriptação de mensagens. O
nome do método faz referência ao imperador Júlio César que utilizava uma técnica semelhante
para se comunicar com os seus generais.
Trata-se de uma cifra de substituição em que cada letra do texto é substituída pela outra, que
está situada na ordem do alfabeto a um número fixo de posições. Por exemplo, com uma troca
de 3 posições a letra “A” seria trocada pela letra “D”, a letra “B” seria trocada pela letra “E”,
a letra “Z” pela letra “C”, e assim sucessivamente. Note que este algoritmo mantém mesmo
mapeamento durante toda a mensagem.
O processo de encriptação pode ser representado através de aritmética modular, primeiro
transforma-se as letras em número. Em seguida, aplica-se a seguinte equação matemática:
En (x) = (x + n)
mod S
De modo semelhante, a decifração é representada como:
Dn (x) = (x − n)
mod S
Onde S é o tamanho da alfabeto considerado, x é número que representa a letra e n é um deslocamento fixo. Este trabalho utilizou a tabela ASCII para converter letras em números.
Como a plataforma não suporta o tipo de dado caractere, utilizou-se um algoritmo preliminar
que transforma a mensagem do usuário em números inteiros de 32 bits. A Tabela 5.6 mostra os
resultados obtidos aplicando-se o algoritmo descrito em uma texto contendo 2.169 caracteres.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Taxa de Acerto
Cache de Dados
Ciclos de Espera
Valor
195.399
1.114.370
5,7
0’ 31"
35.947,41
195.417
99,32 %
522
58.398
99,06 %
16.078
Tabela 5.6: Resultados do algoritmo cifra de César.
45
A cifra de César foi a primeira aplicação com quantidade de ciclos e instruções consideráveis.
Os resultados mostram que foram executadas 195.399 instruções em 1.114.370 ciclos. Além
disso, nota-se na Tabela 5.6 que o simulador rodou a uma taxa de 35.947 ciclos/segundo.
5.1.5
Busca Binária
A busca binária é um eficiente algoritmo de busca em vetores ordenados. A idéia do algoritmo
é realizar sucessivas divisões do espaço de busca, comparando o elemento buscado (chave) com
o elemento no meio do vetor. Se o elemento do meio do vetor for a chave, a busca termina com
sucesso. Caso contrário, se o elemento do meio vier antes do elemento buscado, então a busca
continua na metade posterior do vetor. E finalmente, se o elemento do meio vier depois da chave,
a busca continua na metade anterior do vetor.
A complexidade desse algoritmo é da ordem de log2 n, onde n é o tamanho do vetor de busca.
A seguir temos o pseudo-código do mesmo. Onde A é o vetor de entrada, X é chave a ser buscada
e N é o tamanho do vetor.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
procedure B USCA B INARIA(A,X,N )
menor ← 0
Alto ← N − 1
while (menor ≤ maior) do
meio = (menor+maior)
2
if A[meio] < X then
baixo ← meio + 1
else if X < A[meio] then
alto ← meio − 1
else
return meio
end if
end while
return − 1
end procedure
O teste deste algoritmo consistiu em buscar o elemento central de uma lista de 500 elementos.
Os resultados da simulação são exibidos na Tabela 5.7. Os dados coletados nesta simulação
mostraram que o número de ciclos com o processador parado é insignificante quando comparado
com a quantidade total de ciclos simulados.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Taxa de Acerto
Cache de Dados
Ciclos de Espera
46
Valor
7.807
47.596
6,1
0’ 22"
663,45
7.818
99,85%
347
3.125
97,85%
2.037
Tabela 5.7: Resultados da Busca Binária.
5.1.6
MergeSort
O Mergesort, ou ordenação por mistura, é um algoritmo de ordenação baseado na estratégia de
dividir para conquistar. É um algoritmo estável que executa em O(n ∗ log n). Um algoritmo de
ordenação é dito estável quando ele preservar a ordem de entrada de elementos iguais na saída
produzida pelo mesmo.
A idéia da abordagem dividir-para-conquistar é dividir o problema em vários subproblemas
semelhantes mas menores em tamanho, resolver os subproblemas recursivamente e depois combinar essas soluções com o objetivo de produzir uma solução para o problema original. Essa
técnica aplica três passos a cada nível de recursão que são: dividir, conquistar e combinar.
Os três passos dessa estratégia aplicados ao Mergesort são:
1. Dividir: A seqüência de entrada de n elementos é dividida em duas subseqüências de n/2
elementos cada.
2. Conquistar: Ordena as duas subseqüência recursivamente através de chamadas recursivas
a mergesort.
3. Combinar: Faz a intercalação das duas seqüências ordenadas, de modo a produzir a resposta ordenada.
A Tabela 5.8 apresenta os dados da simulação. Esta simulação consistiu em ordenar 1.000 elementos de um vetor formado aleatoriamente e depois verificar se estes elementos estão realmente
ordenados. Esta segunda etapa se faz necessária porque não existem rotinas de I/O para inspeção
do vetor. Além disso, como a plataforma STORM não possui suporte as bibliotecas de C, não
47
foi possível utilizar a função rand do C. Para contornar este problema, foi implementado um
conjunto de funções que geram números aleatórios para a STORM.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Cache de Dados
Taxa de Acerto
Ciclos de Espera
Valor
740.537
4.341.641
5,86
1’08"
63.847,26
740.573
99,9%
1.094
322.882
99,9%
8.250
Tabela 5.8: Resultados do Mergesort.
O objetivo deste teste era submeter o SPARC a uma carga maior de operações para verificar
o seu comportamento, visando iniciar o desenvolvimento aplicações mais complexas. Observase na Tabela 5.8 a simulação com sucesso de mais de quatro milhões de ciclos. Novamente,
destaca-se o excelente desempenho do sistema de cache que atingiu uma taxa de acerto superior
a 99%.
5.1.7
Algoritmo de Prim
O algoritmo de Prim é um algoritmo em teoria dos grafos que produz uma árvore geradora
mínima a partir de um grafo conexo ponderado. Uma árvore geradora mínima é uma árvore que
inclui todos os vértices e cujo a soma dos pesos de todas as arestas que estão na árvore é mínimo.
O algoritmo funciona da seguinte maneira: Cria-se uma árvore contendo um único vértice
arbitrário e a cada passo, adiciona-se uma aresta mínima que conecte uma vértice presente na
árvore a um não presente a árvore.
Considere um grafo G = (N, M, D), onde N denota o conjunto de vértices, M denota o
conjunto de arcos e D = [dij ] o conjunto dos pesos associados às arestas de G. E os conjuntos B
e T tal que T ⊆ M e B ⊆ N . O seguinte pseudo-código descreve os passos do algoritmo em
questão.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
48
procedure P RIM(G = (N, M, D))
B=i
V =V \i
while (B! = N ) do
Encontrar a menor aresta (j,k) ∈ M tal quej ∈ B, k ∈ V
B =B∪k
V =V \i
T = T ∪ (j, k)
end while
end procedure
O algoritmo descrito acima é da ordem de θ(M log N ). Outra característica importante deste
algoritmo é fato de pertencer a classe dos algoritmos gulosos. A Tabela 5.9 exibe os resultados
da aplicação do algoritmo Prim aplicado a uma árvore de 100 nós. Com base nesta tabela, podese inferir que apenas 1,2% da quantidade de ciclos total foram gastos em operações de acesso a
dados na cache.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Cache de Dados
Taxa de Acerto
Ciclos de Espera
Valor
521.336
2.964.642
5,69
1’ 24"
35.293,35
521.363
99,9%
837
143.758
98,88%
35.611
Tabela 5.9: Resultados do Prim.
5.1.8
Cifra de Hill
A cifra de Hill é uma clássica cifra de substituição polialfabética baseado em álgebra linear.
Inventada por Lester S. Hill em 1929, este método consiste em fazer m combinações lineares dos
m caracteres que compõem o texto original, produzindo m caracteres criptografados.
O processo de encriptação da cifra de Hill funciona da seguinte maneira: todas as letras da
mensagem são tratadas como dígitos na base 26, onde A = 0, B = 1, ..., Z = 25. A mensagem
49
é dividida em blocos de n letras que formando um vetor de n dimensões. Cada bloco é então
multiplicado por uma matriz quadrada de ordem n módulo n. O resultado representa o texto
cifrado. Os elementos da matriz quadrada de ordem n constituem a chave e devem formar uma
matriz inversível em Zn26 .
Em resumo, para um n = 2, um dado texto P = ( p1, p2 ) será levado para um texto criptografado C = ( c1, c2 ), onde c1 é uma combinação linear de p1 e p2 descrita por uma chave K (uma
matriz n x n).
Considere a mensagem “ACT” e a chave:
"
6 24 1
13 16 10
#
Desde que ’A’ seja 0, ’C’ seja 2 e ’T’ seja 19, a mensagem é dada pelo seguinte vetor:

0


 2 
19

Assim o vetor criptográfico é dado por:
"
6 24 1
13 16 10
#

 
 
15
67
0

 
 

 2  ≡  222  ≡  14 
7
319
19

mod 26
O vetor acima corresponde a mensagem cifrada “POH”.
O processo de decifração é feito em dois passo. Primeiro, transformamos o texto cifrado em
um vetor de n dimensões. Em seguida, multiplicamos este vetor pela matriz inversa da matriz
chave. A inversa da matrix do exemplo anterior é dada por:


8 5 10


 21 8 21 
21 12 8
Logo, para descriptografar a seqüência “POH” procedemos da seguinte maneira:


 
 

8 5 10
15
260
0


 
 

 21 8 21   14  ≡  574  ≡  2 
21 12 8
7
539
19
mod 26
50
Desta maneira conseguimos o texto original “ACT”.
A implementação utilizada neste trabalho extendeu o alfabeto de entrada para 29 letras e
utilizou 5000 caracteres contidos nas duas primeiras cenas do primeiro ato do livro "THE TRAGEDY OF OTHELLO" de William Shakespeare. A Tabela 5.10 resume os dados obtidos após a
simulação. Nesta simulação foram executadas 530.023 instruções em 3.054.248 de ciclos, logo
o simulador executou uma instrução a cada 6 ciclos aproximadamente.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Cache de Dados
Taxa de Acerto
Ciclos de Espera
Valor
530.023
3.054.248
5,76
1’02"
49.262
530.040
99,9%
5.305,16
179.163
99,47%
26.733
Tabela 5.10: Resultados da simulação do algoritmo Hill.
5.1.9
JPEG
O JPEG é um formato de compressão de imagens com perda de dados. JPEG é a sigla de Joint
Photographers Experts Group, nome do comitê que desenvolveu o formato. Em 1994, o JPEG
foi aprovado como ISO 10918-1, tornando-se o primeiro padrão internacional de compressão de
imagens.
O JPEG é o formato ideal para imagens que precisam ter tamanho reduzido, como imagens
para serem usadas em sites da web, ou para serem enviadas por email, etc. O tamanho das
imagens (em bytes) torna-se bastante reduzido , pois sua compressão pode chegar a até 90%. Mas
é claro que com um poder de compressão tão alto, existe uma perda na qualidade da imagem.
E vale ressaltar que, uma vez perdida, esta qualidade não pode ser recuperada. Devido a esta
característica, o JPEG é denominado um padrão ’lossy’, ou seja, ocorre perda de qualidade na
compressão da imagem. Por sua vez, outros padrões de compressão podem ter sua qualidade
recuperada. Sendo então caracterizados como ’lossless’ – sem perda da qualidade de imagem no
processo de compressão.
51
O processo de compressão do padrão JPEG funciona, em linhas gerais, da seguinte forma:
Primeiramente, o formato de representação de cores pode ser alterado de RGB para YUV. Essa
transformação melhora o desempenho do JPEG, pois nos espaços de cores do tipo luminância e
crominância, os componentes são mais descorrelacionados do que no formato RGB, potencializando a eliminação de informações menos importantes para o olho humano.
Com a imagem no espaço de cores YUV, é efetuada uma operação denominada de downsampling. Esta operação reduz a taxa de amostragem dos componentes de crominância, associando
a vários pixels a informação de crominância de um único pixel amostrado. O downsampling é
baseada na constatação que a informação de luminância é a mais importante para a percepção do
olho humano do que as informações de crominância.
Após a operação de downsampling, a imagem é organizada em blocos de 8x8 pixels e em
cada um destes blocos é calculada a transformada discreta do cosseno ( DCT - discrete cossine
transform). A função da DCT é converter as informações no domínio do tempo para o domínio
da freqüência. Em seguida, os coeficientes gerados pela DCT são quantizados e alguns coeficientes são até eliminados. O processo de quantização1 é o maior responsável pelo o grau de
compactação conseguido pelo JPEG. Por fim, um algoritmo de compressão lossless, chamado de
codificação de entropia, é aplicada a imagem.
O algoritmo implementado neste trabalho usa imagens com 8-bit de cores, quantização padrão e não realiza a transformação do espaço de cores e operações de downsampling. A Tabela
5.11 mostra os resultados obtidos aplicando-se uma imagem bitmap de 176x144 pixels ao algoritmo JPEG.
Módulo
Descrição
Processador
Tempo de Execução
Ciclos/Segundos
Ciclos de Espera
Cache de Dados
Taxa de Acerto
Ciclos de Espera
Valor
9.772.020
57.708.135
5,91
12’23"
77.669
15.268.402
98,88%
5.003.279
2.672.212
96.18%
3.785.874
Tabela 5.11: Resultados da simulação do JPEG.
1
quantização é o processo de discretização de uma variável contínua.
52
O JPEG foi o algoritmo mais complexo desta bateria de testes. Foram executadas 9.772.020
instruções em 743 segundos, ou seja, foram executadas, aproximadamente, 13.153 instruções por
segundo. A taxa de acerto da cache de dados foi superior a 96%. A seguir, temos a figura utilizada
nesta simulação. Novamente, um arquivo de pre-processamento foi utilizado para carregar a
imagem na plataforma.
Figura 5.1: Figura utilizada na simulação do JPEG.
5.2
Análise dos Parâmetros da Cache
A crescente distância entre a velocidade da CPU e a da memória principal incentivou os projetistas a procurarem maximizar o desempenho da cache. Em ambientes multi-processados, o custo
de se buscar um dado na memória é geralmente muito mais elevado do que o custo de se buscar
o mesmo dado em ambientes uniprocessados, devido a concorrência pelo acesso a memória e o
overhead dos mecanismo de coerência de cache.
Entretanto, como foi dito anteriormente, o mercado de embarcados compete em custo e em
potência, desta maneira, a relação custo/benefício é fundamental importância para o projeto.
A principal métrica de desempenho da cache, é a taxa de acerto. Existem três importantes
parâmetros que afetam diretamente a taxa de acerto da cache. O tamanho da cache, a associatividade e o tamanho do bloco. O efeito da mudança do tamanho do bloco não será analisado
neste trabalho. Analisaremos, portanto, os efeitos do tamanho da cache e da associatividade da
cache. Para realizar está análise, utilizou-se um algoritmo GRASP para o problema de redes de
distribuição de gás desenvolvido em [7].
53
Figura 5.2: Associatividade versus Tamanho da Cache.
O gráfico da Figura 5.2 mostra que a taxa de acerto da cache cresce com o aumento de seu
tamanho. Entretanto, este crescimento ocorre até um certo ponto. Além disso, o custo, área
ocupada e o consumo de energia também aumentam com o aumento do tamanho da cache.
O gráfico também mostra que um aumento na associatividade provoca um aumento na taxa
de acerto da cache. Por outro lado, nota-se que o ganho com o aumento da associatividade
diminui com o aumento do tamanho da cache. Entretanto, aumentar a associatividade implica em
aumentar a complexidade da cache, pois o número de blocos a serem considerados no processo
de substituição também aumenta. O aumento da complexidade, por sua vez, eleva o custo e o
tempo de acesso da cache.
Desta maneira, conclui-se que o projeto da cache visa balancear o custo e o desempenho. A
questão a ser respondida é: Qual deve ser o tamanho e a complexidade da cache para se obter
uma taxa de acerto aceitável a um custo também aceitável?.
É evidente que a resposta para esta questão é dependente das restrições, do tipo e do propósito
do sistema. Cabe a equipe de projetistas encontrar o ponto ótimo para o sistema em questão.
5.3
Análise dos Algoritmos de Substituição
O algoritmo de substituição tem um profundo impacto na taxa de acerto da cache e conseqüentemente influi diretamente no desempenho e indiretamente no tamanho da cache. Pois, um bom
desempenho do algoritmo de substituição pode permitir a utilização de cache menores.
54
Para validar dos algoritmos apresentados na Seção 4.2.2, utilizaremos o mesmo algoritmo do
teste anterior e caches de tamanho 4 KB e 8 KB com associatividade 4. Estas configurações foram escolhidas porque apresentaram os melhores resultados nos testes exibidos na seção anterior.
A Tabela 5.12 resume os dados coletados durante as simulações.
Tamanho Algoritmo
FIFO
LFU
LRU
4 KB
Pseudo LRU
SLRU
GreedyDual
FIFO
LFU
LRU
8 KB
Pseudo LRU
SLRU
GreedyDual
Taxa de Acerto
94,02 %
90,74 %
94,18 %
93,25 %
94,5 %
88,44 %
95,36 %
97,01%
97,14 %
94,97 %
97,8 %
95,6 %
Tabela 5.12: Tamanho versus Algoritmo de Substituição versus Taxa de acerto.
Os resultados da Tabela 5.12 mostram que o algoritmo SLRU teve o melhor desempenho nos
testes. Este resultado demonstra que combinar os mais recentes com os mais freqüentes pode
evitar os problemas inerentes a cada uma dessas abordagens quando utilizadas isoladamente.
Por outro lado, os testes indicam que mesmo quando utilizadas isoladamente ambas as estratégias conseguem bons resultados. Além disso, a tabela mostra que não há diferença significativa
entre as políticas LRU e LFU quando o tamanho da cache aumenta.
Os resultados indicaram que o algoritmo Pseudo-LRU fornece uma boa aproximação do
LRU. A diferença entre os dois algoritmos ficou em torno de 2%. Entretanto, essa diferença
tende a aumentar com o aumento da associatividade da cache.
Por fim, o razoável desempenho apresentado pelo algoritmo GreedyDual ocorreu devido ao
ambiente de simulação utilizado que era composto por um processador, uma memória e uma
NoC. O GreddyDual é voltado para ambientes onde os custos de falhas na cache não são uniformes, entretanto no ambiente utilizado, os custos de falhas na cache são uniformes. É evidente
que uma análise mais profunda do desempenho deste algoritmo se faz necessária. Porém, tal
análise foge do escopo específico deste trabalho.
Capítulo 6
CONCLUSÃO
O presente trabalho abordou o desenvolvimento de uma implementação da arquitetura SPARC e
de módulos de cache L1 para a plataforma STORM. O desafio era suprir a falta de uma unidade
de processamento e ao mesmo tempo, prepara a plataforma para ser utilizada na área do P&G.
O SPARC desenvolvido no âmbito do trabalho é um processador comercial de alto desempenho com suporte a ambientes multiprocessados, tratamento de interrupções, suporte a dispositivos de I/O e ao compilador GCC. O suporte ao compilador GCC é particularmente interessante
para o desenvolvimento de aplicações em linguagens de alto nível como a linguagem C.
A nível de arquitetura, foram abordados aspectos comuns a toda implementação SPARC
e aspectos específicos desta implementação. Os resultados obtidos com a modelagem, design e
implementação demonstraram que de acordo com as decisões de microarquitetura, o processador
pode ser incorporado em diferentes níveis de design de sistemas embarcados. Esta característica
da arquitetura SPARC, permite o desenvolvimento de sistemas embarcados com uma grande
variedade de preço e de desempenho.
Os módulos de cache L1 desenvolvidos foram planejados para oferecer alto grau de personalização. O sistema de cache permite configurar o modo de mapeamento e a política de
substituição, como também o tamanho das caches, da linha da cache, do bloco da cache.
Além disso, o sistema de caches suporta os três modos de mapeamento tradicionais: mapeamento direto, completamente associativo e associativo por conjunto. Além de 6 algoritmos de
substituição: FIFO, LFU, LRU, Pseudo-LRU, SLRU e GreedyDual.
Todos os módulos foram feitos em SystemC e validados com um rica suite de aplicações. Os
testes verificaram o comportamento do processador tanto isoladamente quanto integrado com a
STORM.
CAPÍTULO 6. CONCLUSÃO
56
A conclusão deste trabalho possibilitou a execução de aplicações reais na plataforma. Seja
aplicações voltadas para área de P&G, como as desenvolvidas em [7], seja para grafos, compressão de imagens ou dados, criptografia e etc.
Por fim, a integração do SPARC a STORM é mais um passo na concepção e avaliação de
sistemas MP-SoC. O processador permitiu a execução de aplicações reais na plataforma. Através
destas execuções, foi possível estimar a complexidade e o desempenho deste tipo de sistema.
Além de possibilitar a realização de diversos estudos sobre os mecanismos de coerência de cache,
sincronização e escalonamento de processos, Entrada/Saída, interconexão, dentre outros.
6.1
Trabalho Futuros
Vários trabalhos futuros podem ser apontados ao final deste trabalho. O primeiro é o desenvolvimento de módulos de Entrada/Saída. Sua implementação é de particular interesse da área
do petróleo e gás natural, pois permitirá à plataforma ter comunicação com o meio na qual está
inserida. A nível acadêmico, os módulos de Entrada/Saída para ambiente MP-SoC interligados
por NoC é um campo aberto para pesquisas.
A implementação de um sistema operacional para prover a gerência de recursos e permitir
a multiprogramação é outro trabalho de grande importância acadêmica. A nível de arquitetura,
pode-se realizar várias melhorias no SPARC como: desenvolvimento de técnicas de previsão de
desvio, unidades de ponto-flutuante ou de co-processadores, tratamento de interrupções imprecisas, dentre outros. A abrangência das possibilidades é bastante grande e esse trabalho abre
margem para sua exploração.
Referências Bibliográficas
[1] Angiovanni-Vincentelli, A.; Martin G.; Platform-based design and software design
methodology for embedded systems. Design & Test of Computers, IEEE Volume 18, Issue
6, pp. 23-33, Nov.-Dec. 2001.
[2] Bautista, T.; Núñez, A. Design of Efficient SPARC cores for embedded systems. In: Euromicro Conference, 25, 1999. Proceedings... Milan: 1999, vol. 1, p. 1236-1239.
[3] Belady, L. A.; Nelson, R. A.; Shedler, G. S. An anomaly in space-time characteristics
of certain programs running in a paging machine. Commun. ACM 12, 1969. Montvale:
1969. p. 349-353.
[4] Cao, P.; Irani, S. Cost-aware WWW proxy caching algorithms. In: USENIX Symp. on Internet Technologies and Systems. Proceedings... Monterey, CA: 1997, p. 193-206.
[5] Carro, L.; Wagner, F. Capítulo 2 das Jornadas de Atualização em Informática. In: XXII
JAI 2003. (Org.). Sistemas Computacionais Embarcados. Campinas: Sociedade Brasileira
de Computação, 2003, v. 1, p. 45-94.
[6] de Micheli, G.; Benini, L. Networks-on-Chip: A New Paradigm for Systems-on-Chip Design. In: Design, Automation and Test in Europe Conference and Exhibition. Proceedings...
Paris: 2002, p. 418-419.
[7] Freitas, Tássia A. Vieira. Desenvolvimento de Aplicações da Indústria do Petróleo e Gás
em uma plataforma MP-SoC. 2006. Relatório Final de Graduação ( Bacharel em Ciências
da Computação) - Curso de Ciências da Computação, Universidade Federal do Rio Grande
do Norte, Natal, 2006.
[8] Garner, B. et al. The Scalable Processor Architecture (SPARC). In Proceedings of the IEEE
COMPCON 88, New York, NY, IEEE, pp 278-283, 1988.
REFERÊNCIAS BIBLIOGRÁFICAS
58
[9] GNU Compiler Collection. Disponível em: http://gcc.gnu.org/. Acessado em 20/11/2006.
[10] Hennessy, J. L.; Patterson, D. A. Arquitetura de Computadores: Uma Abordagem Quantitativa. 3.ed. Rio de Janeiro: Campus Editora, 2003. 927p.
[11] ITRS (2001). International Technology Roadmap for Semiconductors, versão 2001. Disponível em http://public.itrs.net/.
[12] Karedla, R.; Love, J. S.; Wherry, B. G. Caching Strategies to Improve Disk System
Performance. IEEE Computer, Vol.27, No. 3, p. 38-46.
[13] Kilburn, T. et al. One-level storage system. IRE Trans. on Electronic Computers, pages
223-235, April 1962.
[14] Namjoo, Masood et al. CMOS Gate Array Implementation of the SPARC Architecture. In:
COMPCON Conference. Proceedings... San Franciso: 1988. p. 10-13.
[15] Smith, J.; Pleszkun, A. R. Implementing Precise Interrupts in Pipelined Processors. In: Annual International Symposium on Computer Architecture, 12, 1985. Proceedings... Boston:
1985 p. 36-44.
[16] Rego, Rodrigo Soares de Lima Sá. Projeto e Implementação de uma Plataforma MPSoC usando SystemC. 2006. 134p. Dissertação (Mestrado em Sistemas e Computação) Curso de Pós-graduação em Sistemas e Computação, Universidade Federal do Rio Grande
do Norte, Natal, 2006.
[17] SPARC International, Inc. The SPARC Manual Architecture Manual Version 8. Upper
Saddle River, NJ, USA: Prentice Hall, 1992.
[18] Stallings, W. Arquitetura e Organização de Compuratores: Projeto para o Desempenho.
5.ed. São Paulo: Prentice Hall, 2002. 786p.
[19] Standard for Binary Floating-Point Arithmetic.
per.ieee.org/groups/754/. Acessado em 04/12/2006.
Disponível
em:
grou-
[20] SystemC User’s Guide. Version 2.0. Update for SystemC 2.0.1. 2003. 216p.
[21] Tanenbaum, A. S. Organização Estruturada de Computadores. 4 ed. LTC Editora, 1999.
[22] Thomas, José Eduardo. Fundamentos de Engenharia de Petróleo. 2.ed. Rio de Janeiro:
Interciência, 2004. 287p.

Resumo - Centro de Ciências Exatas e da Terra

Transcrição

Documentos relacionados

Baixando vídeos pelo cache do Mozilla

+ IceWarp Server 10.4.0

Conceitos de Sistemas Operacionais Estrutura de Sistemas

Memória ROM – ( Memória somente Leitura)

IceWarp Server 10.4

processador

5201 Po Sparc IS 6/02

lista 1

Avaliação de Caches em Dispositivos de Armazenamento

Limpeza do navegador Mozilla Firefox