Centro Universitário Positivo - UnicenP
Computação Configurável utilizando
Processamento Paralelo
Curitiba - PR
2004
Centro Universitário Positivo - UnicenP
Núcleo de Ciências Exatas e Tecnológicas – NCET
Engenharia da Computação
Rafael Nakatani Rucinski
Computação Configurável utilizando
Processamento Paralelo
Monografia de Projeto Final do Curso
de
Engenharia
da
Computação
(Matutino) do UnicenP.
Orientador: Prof. Edson Pedro Ferlin.
Curitiba - PR
2004
2
Termo de Aprovação
Rafael Nakatani Rucinski
Computação Configurável utilizando
Processamento Paralelo
Monografia aprovada como requisito parcial à conclusão
do Curso de Engenharia da Computação (Matutino) do Centro
Universitário Positivo, pela seguinte banca examinadora:
Prof. Edson Pedro Ferlin (Orientador)
Prof. Álvaro Cantieri
Prof. Valfredo Pilla Jr
3
Sumário
Lista de Figuras.............................................................................................................................. 06
Lista de Tabelas ............................................................................................................................. 08
Lista de Siglas e Abreviaturas........................................................................................................ 09
Resumo........................................................................................................................................... 10
Abstract .......................................................................................................................................... 11
1 – Introdução ................................................................................................................................ 12
2 – Estudo Teórico ......................................................................................................................... 14
2.1 – Processamento Paralelo .................................................................................................. 14
2.2 – Computação Configurável .............................................................................................. 21
2.3 – Fourier............................................................................................................................. 23
2.3.1 – A Série de Fourier .................................................................................................. 24
2.3.2 – A FFT e a DFT....................................................................................................... 26
3 – Descrição.................................................................................................................................. 29
3.1 – Descrição Geral............................................................................................................... 29
3.2 – Hardware......................................................................................................................... 30
3.3 – Etapas de Desenvolvimento ............................................................................................ 30
4 – Hardware.................................................................................................................................. 31
4.1 – Microntrolador 8031 ....................................................................................................... 34
4.1.1 – Sinais de Controle .................................................................................................. 35
4.2 – Kit de PLD da Altera ...................................................................................................... 39
4.2.1 – Diagrama em Blocos.............................................................................................. 41
5 – Software do Computador ......................................................................................................... 44
5.1 – Algoritmo FFT ................................................................................................................ 48
6 – Funcionamento do Sistema ...................................................................................................... 49
7 – Recursos Necessários............................................................................................................... 51
8 – Custos e Viabilidade ................................................................................................................ 52
9 – Testes e Validação do Projeto.................................................................................................. 54
10 – Resultado................................................................................................................................ 56
11 – Conclusão............................................................................................................................... 61
Referências Bibliográficas ............................................................................................................. 63
Anexo I – Fluxogramas.................................................................................................................. 65
Anexo II – Resumo do DataSheet dos demais Componentes........................................................ 73
4
Anexo III – Listagem dos Programas ............................................................................................ 77
Anexo IV – Artigo Técnico ........................................................................................................... 91
Anexo V – Manual do Usuário ...................................................................................................... 98
Anexo VI – Manual Técnico....................................................................................................... .103
5
Lista de Figuras
Figura 1 – Evolução dos diversos tipos de computadores no decorrer do tempo...........................14
Figura 2 – Arquitetura SISD (Single Instruction Single Data).......................................................16
Figura 3 – Arquitetura SIMD (Single Instruction Multiple Data)..................................................17
Figura 4 – Arquitetura MISD (Multiple Instruction Single Data)..................................................18
Figura 5 – Arquitetura MIMD (Multiple Instruction Multiple Data).............................................19
Figura 6 – Gráfico de exemplo da Lei da Amdahl..........................................................................20
Figura 7 – Estrutura básica de um sistema configurável ................................................................23
Figura 8a – Função seno .................................................................................................................24
Figura 8b – Função cosseno............................................................................................................24
Figura 9a – Soma das funções seno e cosseno................................................................................25
Figura 9b – Uma função periódica mais complexa.........................................................................25
Figura 10 – A Função f(x) representa a soma de todas as funções.................................................25
Figura 11 – Amostragem em função do tempo e seu espectro (DFT) ............................................26
Figura 12 – Estrutura geral do sistema lógico ................................................................................29
Figura 13 – Sistema Dual................................................................................................................30
Figura 14 – Estrutura Geral do Sistema..........................................................................................31
Figura 15 – Foto do Projeto Físico .................................................................................................32
Figura 16 – Esquemático do Projeto...............................................................................................33
Figura 17 – Pinagem do chip do microntrolador 8031 ...................................................................35
Figura 18 – Esquema de Multiplexação da porta P0 ......................................................................35
Figura 19 – Ilustração da utilização da porta P3.............................................................................36
Figura 20 – Ilustração da ligação da EPROM no 8031 ..................................................................37
Figura 21 – Kit do Altera ................................................................................................................39
Figura 22 – Diagrama de Blocos do PLD EPF10K20RC240-4......................................................41
Figura 23 – Diagrama em Blocos do Modelo Distribuído..............................................................42
Figura 24 – Diagrama em Blocos do Modelo Compartilhado ........................................................43
Figura 25 – Interface gráfica do software .......................................................................................44
Figura 26 – Fluxograma do Funcionamento Geral do Sistema ......................................................47
Figura 27 – Butterfly.......................................................................................................................48
Figura 28 – Exemplo 1 da Butterfly................................................................................................48
Figura 29 – Exemplo 2 da Butterfly................................................................................................48
Figura 30 – Cronograma do Projeto................................................................................................53
6
Figura 31 – Gráfico do desempenho entre os modelos de processamento .....................................57
Figura 32 – Gráfico do SpeedUP ....................................................................................................57
Figura 33 – Gráfico que demonstra a diferença entre o tempo real e o ideal .................................58
Figura 34 – Gráfico do SpeedUP entre os modelos duais ..............................................................59
Figura 35 – Tela do MatLab com o Resultado Obtido ...................................................................60
Figura 36 – Resultado obtido pelo software ...................................................................................60
7
Lista de Tabelas
Tabela 1 – Resumo das funções especiais do porta P3 ...................................................................37
Tabela 2 – Características dos PLDs ..............................................................................................40
Tabela 3 – Valores Correspondentes ..............................................................................................45
Tabela 4 – Custos do Projeto ..........................................................................................................52
Tabela 5 – Tempos obtidos para o cálculo da FFT.........................................................................56
Tabela 6 – Resultado do Sistema x MatLab ...................................................................................59
8
Lista de Siglas e Abreviaturas
A/D – Analógico/Digital
AHDL – Altera Hardware Description Language
ALU – Arithmetic Logic Unit
ASIC – Application-Specific Integrated Circuit
CPLD – Complex Programmable Logic Devices
CPU – Central Process Unit
E/S – Entrada/Saída
EPROM – Erasable Programmable Read-Only Memory
FFT – Fast Fourier Transform
FPGA – Field Programmable Gate Array
LAB – Logic Array Block
LE – Logic Element
MIMD – Multiple Instruction Multiple Data
MISD – Multiple Instruction Single Data
MMX – MultiMedia eXtention
NVRAM – Non-Volatile Random Access Memory
PAL – Programmable Array Logic
PIA – Programmable Interconnect Array
PLD – Programmable Logic Device
PROM – Programmable Read-Only Memory
RAM – Random Access Memory
ROM – Read-Only Memory
SIMD – Single Instruction Multiple Data
SISD – Single Instruction Single Data
VLSI – Very Large Scale Integration
9
Resumo
Ultimamente nota-se o crescente interesse na computação configurável, pois até pouco
tempo atrás só o software sofria alterações e o hardware estava limitado pela aplicação. O
desempenho dependia muito do software e agora com essa nova tecnologia pode se, por exemplo,
conseguir uma otimização do hardware devido ao fato de que podemos configurá-lo de acordo com
a necessidade.
Na área do processamento paralelo também há muita pesquisa, principalmente, pelo fato
de que se pode atingir um alto grau de processamento sem há necessidade de se criar um projeto
para um novo processador. O projeto se baseia no processamento da FFT (Fast Fourier Transform –
Transformada Rápida de Fourier), utilizando o processamento paralelo, com modelo distribuído ou
compartilhado da memória, e utiliza-se a computação configurável para comutar entre esses
modelos de configuração.
O sistema se compõe basicamente de dois microcontroladores 8031, um PLD
(Programmable Logic Device) da Altera e uma memória RAM (Random Access Memory). O PLD
promove a interligação dos componentes, bem como o controle de seu funcionamento. A
arquitetura utilizada para o processamento em paralelo é do tipo MIMD (Multiple Instruction
Multiple Data). O algoritmo de FFT e rotina de comunicação serial estarão armazenadas na
EPROM (Erasable Programmable Read Only Memory) a qual é acessada diretamente pelo
processador, os modelos de funcionamento do sistema, o distribuído e o compartilhado, são
configurados no PLD.
Mesclando-se as duas idéias, a da computação configurável e o do processamento
paralelo, têm-se inúmeras aplicações possíveis, tais como manipulação e processamento de imagens
digitais, compactação e compressão de dados, criptografia, entre outras e tudo isso com um custo
bem reduzido devido à possibilidade de se utilizar o mesmo hardware para diversas tarefas e um
alto poder de processamento sem a necessidade de se investir em um novo projeto de processador.
10
Abstract
Lately we have noticed a growing interest in configurable computing, because formerly
only the software was changed and the hardware was limited by application. The performance
relied on software e now with this new technology we could, for instance, achieve a hardware
optimization due the fact that we can configured it according to our need.
There is also a lot of research regarding parallel processing, mainly, by the fact that we
could achieve a massive processing without need to create a project to brand new processor. The
project is based on FFT’s (Fast Fourier Transform) processing, using parallel processing, with
distributed and shared model, and it uses configurable computing to change between the
configuration models.
The system consist basically of two 8031 microprocessors, a Altera’s PLD
(Programmable Logic Device) and a RAM (Random Access Memory). The PLD promote the
components interconnection, as well as its functioning control. The architecture used to the parallel
processing is MIMD (Multiple Instruction Multiple Data). The FFT algorithm and serial
communication routines are stored into the EPROM (Erasable Programmable Read Only Memory),
which is accessed directly by microprocessor, the system’s functioning models, the distributed and
shared, are configured into the PLD.
Merging both ideas, configurable computing and parallel processing, we have countless
possible applications, such as digital imaging processing and manipulation, data compression,
cryptography, and many more, and all of that with a reduced cost due the possibility to use the same
hardware to several tasks and a massive processing without need to invest in a project to a brand
new processor.
11
1 – Introdução
O tema principal do projeto é o desenvolvimento de um sistema de computação
configurável com dois processadores, usando microcontroladores 8031, configurável em dois
modos de compartilhamento da memória: compartilhada ou distribuída para executar aplicações em
paralelo. O sistema executará em paralelo um algoritmo o de FFT (Fast Fourier Transform). A
interconexão entre os processadores e a memória é realizada por PLDs (Programmable Logic
Devices) programados usando AHDL (Altera Hardware Description Language) da Altera.
Este projeto utiliza os conceitos de processamento paralelo, processadores, arquitetura de
computadores, lógica programável, séries de Fourier e as transformada de Fourier.
O sistema permitirá a reconfiguração rápida da arquitetura sem modificar o hardware em
termos físicos (ligações) apenas de forma lógica dentro do PLD. O elemento integrador de todos os
componentes do sistema é o PLD.
Este tipo de projeto [CARVALHO, 2002] é um dos segmentos que está tendo grande
enfoque atualmente na área da computação, pois utilizando-se o conceito de processamento paralelo
podemos aumentar o poder de processamento dos computadores. Com isso se evita o
desenvolvimento de um novo processador com tal capacidade de processamento diminuindo os
custos.
Com o advento da computação configurável, que permite a readequação dos sistemas
dinamicamente ou estaticamente, visando um melhor desempenho e um melhor aproveitamento da
arquitetura para uma determinada aplicação.
O ponto forte desse projeto é a utilização da computação configurável, pois através dela
pode-se adaptar a maneira de como o hardware se comporta de acordo com o problema encontrado
e também aumentar a vida útil na qual o produto permanece no mercado. Assim como nos sistemas
de softwares que recebem atualizações constantes, o hardware implementado em dispositivos
reconfiguráveis também pode usufruir desta estratégia, possibilitando uma melhor configuração e
como conseqüência um melhor desempenho.
12
Objetivo Geral
Objetivo geral do projeto é construir um sistema paralelo dual reconfigurável o qual
executa a transformada de Fourier.
O sistema é composto por dois processadores 8031, cada um com sua memória de
programa, configurável nos modos distribuído ou compartilhado de memória por meio de um
dispositivo lógico programável.
Os objetivos específicos são:
•
Dominar a tecnologia de sistemas reconfiguráveis;
•
Compreender o funcionamento interno do PLD bem como a representação das
estruturas de dados, a AHDL (Altera Hardware Description Language);
•
Entender e aplicar o conceito de processamento paralelo;
•
Aplicar o estudo de processamento de sinais com base na Transformada Rápida
de Fourier (FFT) para captação, aplicação do algoritmo de FFT e por fim a
função que representa o sinal;
•
Desenvolver um hardware capaz de captar um sinal analógico, aplicar um
algoritmo o de FFT, calculá-lo paralelamente utilizando os conceitos de
lógica configurável;
•
Criar um software capaz de interagir com o hardware e também como uma
interface amigável entre o usuário e o sistema.
13
2 - Estudo Teórico
Neste capítulo está sendo abordado todo o estudo inicial necessário para o
desenvolvimento do projeto e são eles, o conceito de processamento paralelo, uma explicação sobre
a computação configurável, estudo das Séries e Transformada de Fourier, o microcontrolador 8031,
o PLD da Altera, e bem como o estado da arte de cada tecnologia envolvida no projeto.
2.1 - Processamento Paralelo
Com a crescente demanda por mais poder de processamento recentemente optou-se por
construir computadores com mais de um processador, estes computadores tem um maior poder de
processamento sem a necessidade de um único "chip" potente, ou seja, pode-se obter um
computador com uma capacidade de processar um maior número de instruções sem ser necessário o
projeto de um processador revolucionário com tal capacidade.
Figura 1 – Evolução dos diversos tipos de computadores
Fonte: Parallel Computer Architecture [CULLER, 1999]
Como mostrado na figura 1 percebe-se que a desempenho dos microprocessadores vem
crescendo a uma taxa de 50% por ano desde metade da década de 80. Os mais tradicionais
mainframes e supercomputadores têm desempenho crescente em torno de 25% [CULLER, 1999] ao
ano neste mesmo período. Como resultado, estamos vendo que o processador é o que mais se
enquadra para o processamento paralelo e tornando se também o líder em desempenho.
Porém computadores com mais de um processador possuem arquiteturas mais complexas,
ou seja, há a necessidade de programas especificamente escritos para estes computadores de forma
14
a aproveitar todo o seu potencial, pois a maioria absoluta dos programas até hoje se destinam a
computadores com apenas um processador, ou seja, monoprocessados.
Os principais modelos de arquitetura de computadores paralelos são:
•
Computador com memória compartilhada, onde os processadores acessam uma
única memória compartilhada;
•
Computador com memória distribuída, onde cada processador possui sua
própria memória local.
No modelo de memória compartilhada, a mesma memória é acessível a múltiplos
processadores, contudo deve-se tomar o cuidado que para uma mesma posição na memória não seja
modificada enquanto outro processador a esteja acessando. O ponto forte do modelo compartilhado
é maior facilidade de programação.
No modelo de memória distribuída, a memória é fisicamente distribuída entre os
processadores, e cada memória local é acessível apenas pelo seu processador. Esta abordagem
implica na decomposição dos dados para cada processador, e um posterior agrupamento de dados e
grande vantagem dessa arquitetura é sua alta escalabilidade.
A vetorização de um determinado código deve ser realizada antes de se considerar a
paralelização. O alto desempenho de computadores vetoriais reside na capacidade de execução de
somas ou multiplicações simultaneamente. Para realizar essas operações não deve haver
dependência de dados.
Na primeira arquitetura toda memória do sistema pode ser acessada por cada processador
individualmente, na segunda cada processador possui a sua própria memória quando um
processador necessita de informações armazenadas na memória de outro processador estes "trocam
mensagens" usando pinos de controle para tal.
Segundo [FERLIN, 1998a] podemos dividir o processamento paralelo nas seguintes
formas quanto à programação:
•
Paralelização explícita, onde o programador é quem informa as tarefas que
podem ser executadas em paralelo, e a forma como elas devem trabalhar.
•
Paralelização implícita, onde o paralelismo é baseado apenas na semântica de
alguns comandos e construções.
•
Paralelização automática, onde o programador utiliza uma linguagem
seqüencial tradicional, e o compilador é responsável por extrair automaticamente o
paralelismo.
15
É muito difícil a tarefa de classificar computadores paralelos. Já foram feitas diversas
sugestões. Porém, a que trouxe melhores resultados e ainda hoje é usada, é a proposta por Flynn
[ZELENOVSKY, 2004]. Essa classificação está baseada em dois conceitos: fluxo de instruções e
fluxo de dados. O fluxo de instruções está relacionado com o programa que o processador executa,
enquanto que o fluxo de dados está relacionado com os operandos manipulados por essas
instruções. O fluxo de instruções e o fluxo de dados são considerados independentes e por isso
existem quatro combinações possíveis.
Nas figuras 2 a 5 apresentamos os diagramas de blocos para essas quatro combinações. A
sigla MM representa o “Módulo de Memória” e a sigla EP representa o “Elemento de
Processamento”, ou seja, o processador.
•
SISD - Instrução Única, Dado Único (Single Instruction Single Data)
Essa arquitetura é usada nos computadores chamados pessoais ou desktop, onde há
somente um processador, ou seja, o sistema é monoprocessado estas arquiteturas seguem o proposto
por Von Neumann [ZELENOVSKY, 2004] e é por isso denominada de “Arquitetura de Von
Neumann”, também chamado de computador serial. Temos um único fluxo de instruções (SI),
caracterizado pelo contador de programa do processador, que opera sobre um único dado (SD) por
vez. A figura 2 apresenta um diagrama de blocos ilustrativo desta arquitetura.
Figura 2 - Arquitetura SISD (Single Instruction Single Data)
16
•
SIMD - Única Instrução, Múltiplos Dados (Single Instruction Multiple Data)
A arquitetura mostrada na figura 3 apresenta N processadores (EP), sendo que cada
processador trabalha sobre um dado distinto, que vem de cada um dos N módulos de memória
(MD). O ponto importante é que todos os processadores (EPi) trabalham sincronizados e executam
todos a mesma instrução, ou seja, cada instrução é passada, ao mesmo tempo, para os N EPs.
Assim, os processadores executam a mesma instrução, porém sobre um dado diferente. Como é
fácil de concluir, um computador com essa arquitetura é capaz de operar um vetor de dados por vez.
Por esse motivo dá-se o nome de Computador Vetorial, ou “Array Processor”.
Figura 3 - Arquitetura SIMD (Single Instruction Multiple Data)
Um grande exemplo desta arquitetura são os famosos supercomputadores Cray [MORON,
2004]. Outro exemplo é o conjunto de instruções MMX (MultiMedia eXtension). Eles são muito
usados quando um mesmo programa deve ser executado sobre um grande volume de dados, como é
o caso de prospecção de petróleo. Note que essa arquitetura não sofre com problemas de
sincronização, pois existe um único programa em execução.
17
•
MISD - Múltiplas Instruções, Dado Único (Multiple Instruction Single Data)
Essa arquitetura é um pouco mais difícil de ser explicada. Tentemos imaginar como é que
se pode fazer múltiplas operações (MI) sobre um mesmo dado (SD). Os próprios pesquisadores têm
opiniões divergentes sobre esse assunto. De forma simples, vamos estudar a figura 4, onde pode ser
visto que, apesar de existir um único fluxo de dados, existem vários dados sendo operados ao
mesmo tempo. A figura 4 é conhecida na literatura especializada com o nome de “pipeline” ou linha
de produção.
A figura 4 mostra que N processadores operam sobre K diferentes dados. Podemos fazer
uma analogia com uma linha de montagem de carros, onde pessoas trabalham simultaneamente
sobre um mesmo carro. Voltando aos computadores temos um único fluxo de dados (SD), porém
vários instruções (MI) processam esses dados, ao mesmo tempo.
Figura 4 - Arquitetura MISD (Multiple Instruction Single Data)
•
MIMD - Múltiplas Instruções, Múltiplos Dados (Multiple Instruction Multiple Data)
Essa é a arquitetura que esperaríamos encontrar em um computador paralelo e é a qual
implantamos em nosso sistema. Temos vários dados (MD) sendo operados por vários instruções
(MI), simultaneamente. Essa é a arquitetura mais usada pelos modernos supercomputadores. Nesse
caso, é importante que os processadores possam se comunicar entre si para fazer a sincronização e
trocar informações. Além disso, é necessário ter uma memória, chamada de global, onde todos
processadores possam disponibilizar, para os demais, os resultados intermediários. A figura 5
apresenta uma solução genérica para essa arquitetura MIMD.
18
Figura 5 - Arquitetura MIMD (Multiple Instruction Multiple Data)
Note que agora temos N processadores e dois tipos de memória: a local e a global. A
memória global pode ser acessada por qualquer um dos processadores, por isso existe a chamada
“Estrutura de Comunicação”, que disponibiliza a memória global para qualquer um dos
processadores. Uma única memória global criaria um grande gargalo, pois só um processador
poderia acessá-la por vez. Por isso, a figura 5 apresenta duas memórias globais e, com isso, dois
processadores podem ser atendidos ao mesmo tempo.
Para evitar uma quantidade excessiva de acessos a essa memória, os processadores
possuem a chamada memória local, onde está a maioria das suas instruções e dos dados que devam
ser operados. Essa memória local evita que a estrutura de comunicação se transforme num enorme
gargalo. Os processadores precisam trocar informações e, no caso, a própria estrutura de
comunicação se encarrega desta tarefa.
Uma simples análise da arquitetura MIMD, a figura 5, mostra que agora existe um fluxo
de múltiplos dados (MD) sendo operado por um fluxo de múltiplas instruções (MI). Se já é difícil
escrever e depurar programas seriais, imagine fazer isso em um computador com, por exemplo,
1024 diferentes programas trabalhando sobre 1024 conjunto de dados diferentes.
Apesar do quanto promissor a computação paralela possa parecer, ela não é uma solução
para todo o problema de processamento. Existem tarefas que são eminentemente seqüenciais e que
não tiram proveito de um computador paralelo. Assim, é comum que as tarefas a serem executadas
possuam porções paralelizáveis e porções que precisam ser executadas de forma seqüencial. Note
que um computador paralelo operando de forma seqüencial é um grande desperdício, pois enquanto
um processador trabalha no trecho serial, todos os demais ficam ociosos.
19
Abordando esse tema, Amdahl propôs uma expressão para esse problema, que ficou
conhecida como Lei de Amdahl [ZELENOVSKY, 2004]. Imaginemos uma tarefa que executada em
um computador seqüencial gaste "T" segundos. Porém, quando preparada para execução em um
computador paralelo, ela tem uma porção que obrigatoriamente deve ser executada de forma serial.
Digamos que "p" represente a porção serial, em conseqüência "(1-p)" representa a porção
paralelizável. Quando executado em um computador paralelo com N processadores, o tempo gasto
será igual à pT + (1 – p) . T / N.
Somente o trecho paralelizável tira proveito dos "N" processadores, e o Ganho de
Processamento (GP) é dado pela equação (1):
GP =
1
T
ou GP =
(1 − p )
(1 − p ) ⋅ T
pT +
p+
N
N
(1)
que é a forma consagrada da Lei de Amdahl. Deve-se notar que estamos ignorando os custos de
sincronização e de troca de parâmetros entre os processadores.
Ganho no Processamento
100
1
90
2
80
70
1 - p=0%
2 - p=0,1%
3 - p=1%
60
3
50
4 - p=10%
40
30
20
4
10
0
0
20
40
60
80
Número de Processadores
100
Figura 6 – Gráfico de exemplo da Lei da Amdahl
O gráfico da figura 6 apresenta quatro curvas. A curva 1 é a de uma tarefa 100%
paralelizável, ou seja, p = 0. Nesse caso o aumento do número de processadores reflete linearmente
no desempenho. A curva 2 ilustra o caso de p = 0,001 ou 0,1%, ou seja, apenas 0,1 % das tarefas
não puderam ser paralelizadas. A curva 3 é para o caso onde 1% (p = 0,01) da tarefa precisa ser
executada de forma serial. Nota-se uma grande queda de desempenho para grande quantidade de
20
processadores. A curva 4 representa o caso de uma tarefa onde 10% (p = 0,1) precisam ser
executadas de forma serial. Nota-se que há uma saturação, e que o aumento de processadores, por
exemplo, de 50 para 100 processadores, pouca diferença traz para o desempenho.
Devem ser ressaltados dois pontos importantes. O primeiro é que, exceto para o caso de
p = 0, todos os demais casos apresentarão saturação em algum ponto. Se p é pequeno, a saturação só
ocorre com um elevado número de processadores. O segundo ponto é que, contrastando com o
gráfico da figura 6, a Lei de Amdahl não prevê queda no desempenho, no pior caso, ele fica fixo em
algum valor.
2.2 - Computação Configurável
O FPGA (Field Programmable Gate Array) é o resultado da convergência de duas
tecnologias, o PLD e o ASIC (Application-Specific Integrated Circuit). A história do PLD começou
com os primeiros dispositivos de PROM (Programmable Read-Only Memory) e adicionada à
versatilidade com o PAL (Programmable Array Logic) o qual permitiu um número muito maior de
entradas e a inclusão de registradores internos. Esses dispositivos continuam a crescer em tamanho
e quantidade de portas lógicas por mm2. Nesse período, o ASIC tem sido um dispositivo poderoso,
mas seu uso requer geralmente um investimento considerável de tempo e dinheiro. Tentativas para
reduzir isso foram conseguidas através da modularização dos elementos do circuito como nas
células base do ASIC e através da padronização das camadas de máscaras pela pioneira empresa
Ferranti Electronics [RIVER, 2004] com a Uncommitted Logic Array, um tipo de circuito integrado
semi-customizável nos quais as portas lógicas não estão interligadas, e estão são conectadas
conforme a aplicação de cada fabricante. O passo final foi combinar essas duas tecnologias com um
mecanismo que pudesse ser programado usando fusíveis, antifusíveis ou células de memória como
nos dispositivos Altera [VILLASENOR, 2004] no meio dos anos 80. Os circuitos resultantes são
muito parecidos em potencialidade e aplicação com os maiores PLDs. Além de computação
configurável, os PLDs são usados como controladores, codificadores, decodificadores, e para
prototipação de circuitos e microprocessador VLSI (Very Large Scale Integration) customizados.
O primeiro fabricante desses dispositivos foi a Xilinx e seus dispositivos permanecem um
dos mais populares entre companhias e grupos de pesquisa. Há mas outros fabricantes nessa área
incluem a Atmel, AMD e Motorola. Neste projeto utilizamos os dispositivos lógicos da Altera.
Pode notar-se o crescimento acentuado do interesse em computação configurável, este
interesse crescente tem sua causa atribuída diretamente ao também crescente nível de integração de
componentes em um circuito integrado VLSI. A flexibilidade proporcionada pela computação
21
configurável é outro fator relevante. Através dela pode-se adaptar a maneira de como o hardware se
comporta de acordo com o problema encontrado e também aumentar a vida útil na qual o produto
permanece no mercado por exemplo. Assim como nos sistemas de softwares que recebem
atualizações constantes, o hardware implementado em dispositivos reconfiguráveis também pode
usufruir desta estratégia se adequando melhor à aplicação.
Desde a sua introdução os PLDs baseados em RAM vem prometendo ao desenvolvimento
de hardware a mesma flexibilidade que o desenvolvimento de software. O advento e a vertiginosa
ascensão de complexidade e uso de dispositivos de hardware configurável geram a necessidade de
novos paradigmas de projeto em todos os níveis de abstração, desde os inferiores aos mais
abstratos. Sistemas reconfiguráveis são aqueles onde o hardware pode, após sua fabricação, ter
alterada, ainda que parcialmente, sua funcionalidade [CARVALHO, 2003].
Um PLD baseado em RAM é um dispositivo naturalmente configurável. De uma maneira
grosseira, pode-se pensar num PLD como um hardware customizável a cada instante pelo usuário
para executar diferentes funções, através do preenchimento dos bits da memória de controle. A este
processo de personalizar o hardware a cada instante, dá-se o nome de reconfiguração. Em um dado
instante, pode-se modificar o comportamento de um hardware mudando sua lógica interna,
realizando uma reconfiguração do hardware. Dessa forma, uma reconfiguração é o processo de
alterar uma dada configuração.
Os dois dos tipos de Dispositivos Lógicos Programáveis (Programmable Logic Devices PLDs) mais empregados são os CPLDs (Complex Programable Logic Devices) e os PLDs. Em
geral, PLDs são dispositivos de maior porte que CPLDs.
Genericamente, uma configuração em um dispositivo/sistema de hardware configurável é
um conjunto de bits carregado em posições de uma memória de controle interna do dispositivo
(FPGA/CPLD) para determinar as funções e a estrutura do hardware que se deseja construir.
Alguns dispositivos podem ser reconfigurados apenas totalmente, ou seja, todos os itens
configuráveis do dispositivo devem receber uma configuração antes deste poder ser utilizado.
Outros podem ser reconfigurados parcialmente, onde alguns dos bits de configuração, e não todos,
são alterados de cada vez. Estes são chamados dispositivos parcialmente reconfiguráveis.
As reconfigurações podem ser dinâmicas ou estáticas [RIVER, 2004]. Se o sistema não
necessita ter seu processamento interrompido para que uma reconfiguração seja realizada então ele
é dito dinâmico, caso contrário, é dito estático.
Pode-se classificar dispositivos reconfiguráveis de acordo com o tamanho do grão
configurável. Entende-se por grão a menor unidade configurável da qual um dispositivo é
22
composto. Modernamente, se as configurações se dão no nível de bits diz-se que o dispositivo
possui grau pequeno. Se estas se dão em unidades maiores, tais como os Uncommitted Logic
Arrays, diz-se que o dispositivo possui grau médio. Quando estas se dão em unidades ainda
maiores, tais como um microprocessador inteiro, diz-se que o dispositivo é de grau grande.
Os PLDs estão entre os dispositivos de mais alto grau de integração, ultrapassando
dezenas de milhões de transistores em um único chip (System-on-a-Chip ou SoC). Isto habilita que
eles sirvam de suporte a implementação de sistemas completos em um único chip. As vantagens do
uso de SoCs são: a diminuição do tempo de desenvolvimento que reduz o tempo para o produto
chegar ao mercado, o alto desempenho devido ao fato de todos os componentes do sistema estarem
no mesmo circuito integrado, onde os sinais são transmitidos mais rapidamente, pois as distâncias
são menores, o tamanho reduzido do produto e sua baixa potência dissipada. Para permitir a
implementação eficiente em termos de desenvolvimento de SoCs é necessário empregar ao máximo
técnicas de reutilização de hardware.
A estrutura geral de um sistema configurável [CARVALHO, 2002], como mostrado na
figura 7, é composta por três módulos principais: um Repositório de Configurações, um
Controlador de Configurações e uma Aplicação. De uma forma simplificada, o Controlador de
Configurações e responsável por gerenciar os modelos de configuração disponíveis, contidos no
Repositório de Configurações, o qual é memória principal ou secundária, onde ficarão armazenadas
as possíveis configurações do sistema, geralmente em um dispositivo como o PLD de acordo com a
execução da aplicação. O Controlador de Configurações pode ser implementado ou em hardware,
ou em software ou em um misto de hardware e software.
Repositório de
Configurações
Controlador de
Configurações
Aplicação
Figura 7 - Estrutura básica de um sistema configurável
2.3 – Fourier
A Transformada de Fourier (FFT) é uma ferramenta largamente empregada em
processamento de sinais, processamento de sons e em processamento de imagens. Denominada
assim em homenagem ao físico francês Jean Baptiste Joseph Fourier (1768-1830) [FOURIER,
2004a], a FFT decompõe um sinal em suas componentes elementares seno e cosseno. A FFT
aplicada, por exemplo, a uma imagem no domínio espacial gera uma informação no domínio da
freqüência, em que cada ponto, definido por um vetor, representa uma dada freqüência contida no
domínio espacial da imagem.
23
As aplicações referentes à FFT são inúmeras: filtragem, segmentação, reconhecimento de
padrões, descrição de imagens, compressão e reconstrução constituem algumas delas. A
transformada de Fourier representa a soma de uma série de formas de onda senoidais com diferentes
amplitudes, fase e freqüência.
2.3.1 – A Série de Fourier
A figura 8a mostra o gráfico da função sen(x), onde x é um ângulo medido em radianos.
Essa função é periódica, isto é, sua forma se repete a cada período. No caso da figura 8a, a função
seno se repete a cada período de 2π. O valor máximo da função é 1.
a)
b)
Figura 8 – a) Função seno, b) Função cosseno
A função cosseno, que é mostrada na figura 8b, também é periódica, com o mesmo
período e amplitude que o seno, mas é deslocada de π/2 em relação ao seno. Isso é fácil de constatar
examinando os gráficos. Tecnicamente, diz-se que as funções seno e cosseno diferem na fase e a
diferença de fase entre elas é de π/2.
Na figura 9a, vemos a soma das funções sen(x) e cos(x) e que é obtida traçando-se, em
cada ponto x, a soma dos valores de sen(x) e cos(x) nesse ponto. Por exemplo, o ponto da curva na
região x=5,5 é zero pois o valor de sen(x) é igual e de sinal oposto ao valor de cos(x) nesse ponto.
24
a)
b)
Figura 9 – a) Soma das funções seno e cosseno, b) Uma função periódica mais complexa
Uma função periódica pode ser bem mais complicada que uma senóide. Veja o exemplo
da função f(x) mostrada na figura 9b. Essa curva também é periódica, mas não é apenas um seno ou
um cosseno.
Fourier [FOURIER, 2004b] descobriu, no início do século 19 a função matemática dos
sinais. Segundo ele, qualquer função periódica, por mais complicada que seja, pode ser representada
como a soma de várias funções seno e cosseno com amplitudes, fases e períodos escolhidos
convenientemente.
Existem alguns requisitos para que essa afirmação seja totalmente verdadeira. Mas, eles
são tão poucos e especializados que podemos ignorá-los nesse relato simplificado.
A figura 10 mostra a mesma curva da figura acima juntamente com duas funções seno e
duas funções cosseno. A curva original é a soma dessas quatro funções. Note que as amplitudes e
períodos das ondas componentes são diferentes entre si.
Figura 10 – A função f(x) representa a soma de todas as funções
25
Matematicamente, a decomposição da função f(x) na curva acima é a equação (2).
f(x) = 2sen(x) + 7sen(2x) + 5cos(3x) + 4cos(5x)
(2)
Em resumo, qualquer função f(x) pode, segundo Fourier, ser escrita na forma da soma de
uma série de funções seno e cosseno conforme a equação (3).
f(x) = a0 + a1sen(x) + a2sen(2x) + ... + b1cos(x) + b2cos(2x) + ...
(3)
Resta obter uma forma de calcular os coeficientes a0, a1, ..., b0, b1, ..., de cada termo da
série. Esses coeficientes, como vemos, são as amplitudes de cada onda componente do
desenvolvimento em série. Pois foi isso que Fourier conseguiu fazer: achou uma forma simples e
elegante de calcular esses coeficientes.
2.3.2 – A Transformada Discreta de Fourier e a Transformada Rápida de Fourier
Bem como foi descrito acima as Séries de Fourier só valem para sinais periódicos, e como
quase nunca os sinais que trataremos serão períodos precisamos de algo mais abrangente que
funcione tanto com sinais periódicos quanto os não periódicos, e foi pensando nisso que Fourier
criou a Transformada as quais funcionam tanto para sinais periódicos ou não.
A essência do cálculo da Transformada Rápida de Fourier (FFT) é uma série de operações
matemáticas conhecidas como Transformada Discreta de Fourier (DFT) que é um conjunto m de
variáveis no domínio da freqüência a partir de um conjunto n de amostras no domínio do tempo. A
figura 11 ilustra um sinal x(n) com N amostras em intervalos de T segundos. Para n variando de 0 a
(N – 1), a duração do sinal é Tp = N.T.
Figura 11 - Amostragem em função do tempo e seu espectro (DFT)
26
A DFT de x(n) é definida pela soma finita na equação (4).
1
X ( m) =
N
n −1
∑ x ( n) ⋅ W
n−m
(4)
n =0
onde:
W = e − i 2π / N
(5)
A função X(m) gera m variáveis no domínio da freqüência com incremento F = 1/Tp. Para
x(n) real com N amostras, um único espectro pode ser computado para N/2 pontos da freqüência.
Na verdade, X(m) é uma função periódica em m com N pontos em cada período, mas apenas N/2
são únicos.
Observando a definição da DFT, verifica-se que são necessárias cerca de N multiplicações
e adições complexas para computar o espectro de cada m em particular e, se forem calculados N/2
componentes espectrais, o número de computações para o cálculo de todo o espectro é da ordem de
N2. Como foi demonstrado por Cooley e Tukey [FOURIER, 2004] pode-se calcular esta
transformada com um número de processos computacionais da ordem de N.log2(N), o que poupa
um grande esforço computacional. Este método é conhecido como Transformada Rápida de Fourier.
Os algoritmos de DFT funcionam melhor quando o número de pontos da amostra é uma
potência inteira de 2, ou seja: N = 2k, onde k é um inteiro positivo. Um programa que utiliza DFT
com a finalidade de análise espectral, apresenta certas particularidades na relação entre a DFT e a
transformada contínua de Fourier. Deve-se considerar que o tratamento matemático considera o
sinal como se ele fosse periódico, embora, na realidade, o sinal pode não ser periódico no sentido
matemático estrito.
Um algoritmo para o cálculo da DFT deve levar em consideração alguns fatores básicos.
Se tomarmos N = 2k, para k inteiro positivo, amostras em um período, e se T é o incremento entre
cada amostra, então o período Tp = 2k . T. O espectro obtido da DFT, também será periódico e
conterá 2k componentes espectrais. Entretanto, se a amostragem em função do tempo for real, pode
ser demonstrado que metade dos componentes são coincidentes, logo apenas N/2 componentes
espectrais complexos são significativos. Tais componentes são incrementados de F = 1/Tp; m = 0
corresponde a própria componente, m = 1 é a fundamental, m = 2 é o segundo harmônico, etc...
Para se evitar a sobreposição espectral, a taxa de amostragem deve ser maior ou igual ao dobro da
maior freqüência do espectro, ou seja, se a maior freqüência for fm, então de acordo com o
27
Teorema de Nyquist [SMITH, 2004] o máximo intervalo entre as amostras deve satisfazer a
equação (6):
T ≤ 1 /(2 ⋅ f m )
(6)
logo, se a maior freqüência do espectro for de 20KHz, por exemplo, o intervalo máximo entre as
amostras deve ser menor que 25µs. Devemos respeitar o Teorema de Nyquist, pois caso ele não seja
satisfeito o resultado obtido não será condizente com o real, pelo fato de ocorrer sobreposição de
espectro.
28
3 – Descrição
3.1 - Descrição Geral
O projeto consiste em uma arquitetura dual paralela configurável utilizando
microcontroladores 8031 para resolução do cálculo da Transforma de Fourier utilizando um
algoritmo de FFT, conforme apresentado na figura 12.
Para acessar a memória externa, nesse projeto foi utilizado o modelo distribuído, no qual
cada processador possui sua memória e o modelo compartilhado, onde existe apenas uma memória
física de acesso comum aos dois processadores, e para que não haja a necessidade de se construir
um projeto para cada modelo de memória, utilizamos um dispositivo lógico programável o PLD, o
qual é o elemento integrador do sistema, ele é o encarregado de controlar o acesso a memória
externa pelos processadores, ou seja, o mesmo hardware é capaz de trabalhar no modelo de
memória distribuído e compartilhado bastando apenas carregar o modelo desejado no PLD.
O cálculo da FFT é realizado com amostras de 16, 32, 64, 128, 256, 512 e 1024, os
processadores trabalham a 11,0592MHz, com a serial ajustada para 9600bps, podendo acessar até
64KB de memória externa. Para o sistema funcionar é necessário um computador com essas
características mínimas, Pentium III 500MHz, com 64MB de memória RAM, HD de 20GB, com
porta serial, o sistema operacional Windows 98 e o software da Altera Quartus II para realizar a
comutação entre os modelos de memória.
Serial
Serial
Modulo Adicional
Figura 12 – Estrutura geral do sistema lógico
29
3.2 - O Hardware
O sistema é composto por dois microcontroladores 8031, que trabalham paralelamente, ora
com a configuração de memória compartilhada, figura 13a, ora com distribuída, figura 13b, de
acordo com a opção escolhida inicialmente. Os dados são enviados pela porta serial do computador,
e ambos os processadores são interconectados a um PLD, que por sua vez é ligada a uma memória
que serve para armazenar os dados como mostra a figura 12, e para a conversão e tratamento do
sinal é utilizado um algoritmo de FFT.
a)
b)
Figura 13 – Sistema Dual - a) Sistema com Memória Compartilhada, b) Sistema com Memória Distribuída
3.3 – Etapas de Desenvolvimento
Etapa 1. Sistema básico com um microcontrolador 8031: com uma EPROM e um latch, um
programa para ler o dado da porta serial e reenviá-lo, após algum tempo, ao
computador pela porta serial;
Etapa 2. Incorporação do PLD: o PLD é programado para que o mesmo teste acima
mencionado seja realizado transparentemente, ou seja, que o sistema funcione
como se não houvesse o PLD;
Etapa 3. Incorporado o segundo sistema básico: com uma EPROM e um latch, o PLD é
reprogramado para dividir as tarefas entre os processadores utilizando-se dos dois
modelos de memória: o compartilha ou o distribuída.
Etapa 4. Testes: com o PLD programado foram enviados alguns dados pela porta serial do
computador e o PLD se encarrega de gravar os dados na memória e depois repassálos aos processadores para o processo de cálculo;
Etapa 5. Módulo Adicional: um módulo adicional seria implementado caso houvesse
tempo, ele receberia um sinal analógico e se encarregaria de enviar ao sistema os
coeficientes da série de Fourier para realizar o cálculo da FFT, porém não foi
implementado por falta de prazo.
30
4 - Hardware
O sistema é baseado em dois microcontroladores 8031, como mostra a figura 14,
trabalhando a freqüência de 11,0592MHz, ligados cada um a um latch modelo 74LS373 que por sua
vez é conectado a uma EPROM de 64Kbytes, pois é o máximo de memória que o este processador
pode trabalhar, modelo 27C512 todos esses dispositivos serão alimentados com uma tensão de
operação de 5 volts.
O processador Mestre é conectado a serial de um computador e o processador Escravo
seria ligado a um módulo adicional que se encarregaria de captar os coeficientes para o cálculo da
FFT, mas como não sobrou tempo para a realização do mesmo o módulo adicional não foi feito,
então os dados são simulados pelo próprio computador.
Foram utilizadas duas memórias NVRAM para dados, no caso não foi usada uma, porque
para que fosse possível ela deveria permitir acesso múltiplo de endereço e de dados, como esse tipo
de memória é cara, difícil de se encontrar e complicada para se trabalhar, foram utilizadas duas
memórias comuns, e emulando-as como se fossem apenas uma.
Porta Serial
Figura 14 – Diagrama em Blocos do Sistema
31
A EPROM, o qual conterá a programação bem como suas configurações inicias, é ligada
ao processador pelo latch, e é de uso privado de cada processador. O PLD se encarregará de
distribuir as tarefas entre os processadores e de acessar a EPROM de dados para os mesmos.
Para simular os coeficientes da Série de Fourier foi utilizado o próprio computador que
envia os coeficientes pela porta serial, a uma taxa de 9600bps, esta seria a tarefa do Módulo
Adicional.
Na figura 16 está o esquemático do sistema com todos os componentes utilizados, e logo
na seqüência vem a especificação e características gerais dos principais componentes empregados
nesse projeto. Na figura 15, tem-se o projeto físico montado com o Kit da Altera, os dois Kits com o
8031 e também a memória externa.
Kit Altera
Processador Escravo
Memória Externa
Processador Mestre
Kit Altera
Figura 15 – Foto do Projeto Físico
32
Figura 16 – Esquemático geral do sistema
33
4.1 – Microntrolador 8031
Um microcontrolador é um componente [NICOLOSI, 2000] que tem, num único chip,
além de um processador, elementos tais como memória, temporizadores, contadores, canais de
comunicação e conversores analógico-digitais. Esta característica diferencia os sistemas baseados
em microcontroladores daqueles baseados em microprocessadores, onde normalmente se utilizam
vários componentes para implementar essas funções. Com isso, os microcontroladores permitem a
implementação de sistemas mais compactos e baratos do que aqueles baseados em
microprocessadores.
Um microprocessador é um chip feito de silício, o qual contem uma CPU (Central Process
Unit) que por sua vez contem a ALU (Arithimetic Logic Unit) que é responsável pelos cálculos
aritméticos e operações lógicas e uma unidade de controle que realizará o controle do ciclo de
máquina, que será explicado a seguir, e o microprocessador pode também ter uma memória interna
para fins diversos.
Cada ação feita pelo microprocessador deve ser desdobrada em seus passos mais básicos.
Uma seqüência de passos, desde a busca da instrução até o resultado final desta instrução, se chama
ciclo de máquina, o qual consiste de uma seqüência de seis estados na família 8051. Cada estado
toma 2 períodos de clock e, portanto, um ciclo de máquina toma 12 períodos de clock ou 1µs sob
uma freqüência de 12MHz.
Um ciclo de máquina se divide da seguinte maneira:
1) Busca – Lê uma instrução da memória principal;
2) Decodifica – Interpreta a instrução;
3) Executa – Processa a instrução;
4) Armazena – Salva o resultado.
Em contrapartida, os processadores dos microcontroladores são, em geral, menos
poderosas do que os microprocessadores. Seu conjunto de instruções costuma se limitar às
instruções mais simples encontradas nestes, sua freqüência de clock é mais baixa e o espaço de
memória endereçável costuma ser bem menor. O campo de aplicação dos microcontroladores é
diferente daquele dos microprocessadores, e que um sistema que possa ser controlado por um
microcontrolador tende a ter menor complexidade e menor custo do que um sistema que exija a
capacidade de processamento de um microprocessador. A figura 17 detalha a pinagem do 8031 e a
sua descrição vem logo em seguida.
34
8031
Figura 17 - Pinagem do chip do microntrolador 8031
Fonte: [NICOLOSI, 2000]
4.1.1 - Sinais de Controle
ALE (Address Latch Enable): É o pino que comanda a demultiplexação das informações
de dados e endereços (menos significativo) da porta P0. Este sinal é automaticamente gerado pelo
8031, sem a interferência do programador.
O pino ALE (Address Latch Enable), que ligado a um chip latch, permite demultiplexar
externamente os dados e endereços no tempo, separando assim as informações. Isto é transparente
ao programador, isto é, você não precisa se preocupar com o comando desse pino ALE. Ele é
automaticamente gerenciado pelo microprocessador, você só liga o latch e o pino ALE no latch, e o
microcontrolador se encarrega de acionar o latch, como mostrado na figura 18.
Figura 18 – Esquemático de multiplexação da porta P0
Fonte: [NICOLOSI, 2000]
35
•
Porta P0: Porta de propósito geral, se não for utilizada memória externa. É porta de
utilização como via multiplexada no tempo, entre dados e endereços (só os endereços menos
significativos) quando usamos memória externa. Na mesma via, num dado tempo, apresentam-se
dados e em outro tempo, endereços. Foi uma maneira de economizar pinos no chip. Se não
multiplexasse dados com endereços, deveríamos ter uma porta para dados e outra porta para
endereços, o que acrescentariam 8 pinos ao chip.
•
Porta P1: Porta de propósito geral como "E/S" (Entrada e Saída). São oito bits de
comunicação de propósito geral. Via software, pode-se ler ou escrever nessa porta.
•
Porta P2: Porta de propósito geral, se não for utilizada nenhuma memória externa,
pode-se usar essa porta como E/S.
•
Porta P3: Porta de propósito geral de E/S, isto se não for utilizado nenhum
periférico interno ao chip, nenhuma interrupção externa e também se não utilizar memória externa.
Essa porta é utilizável como interface entre os periféricos internos do chip para fora do mesmo,
além de ter entradas programáveis, como interrupção e dois pinos que gerenciam uma memória
externa (pinos de Read - RD e Write - WR). Logo, essa porta também, em geral, é comprometido
parcialmente com alguma utilização que se deseja dos periféricos internos, interrupções, etc, como
demonstra a figura 19.
Figura 19 - Ilustração da utilização da porta P3
Fonte: [NICOLOSI, 2000]
36
A seguir, apresenta-se a tabela 1 que resume as funções especiais da porta P3:
Tabela 1 - Resumo das funções especiais da porta P3
Nome
Número Função
do Pino Especial
Função
Normal
Função Especial
Comentários da Função Especial
P3.0
10
RXD
E/S
RDX, Receive Data Usado como receptor de dados serial
P3.1
11
TXD
E/S
TXD, Transmit Data Usado como transmissor de dados serial
P3.2
12
INTO
E/S
Extemal interrupt O Usado para algum evento externo interromper o 8031
P3.3
13
INT1
E/S
Extemal interrupt 1
Usado para outro evento externo interromper o 8031
P3.4
14
T0
E/S
Timer/counter O:
Extemal input
Usado quando se quer que o timer zero se tome um
contador de eventos externos
P3.5
15
T1
E/S
Timer/counter 1:
External input
Usado quando se quer que o timer1 se tome um
contador de eventos externos
P3.6
16
WR
E/S
External data:
Usado quando se conecta RAM externa no chip.
Memory write strobe Sinaliza que o Mp vai "escrever" na RAM
P3.7
17
RD
E/S
External Data:
Usado quando se conecta a RAM externa no
Memory read strobe chip.Sinaliza que o Mp vai "ler" da RAM
•
PSEN (Program Store Enable): É um dos quatro pinos de controle do chip. Ele
aciona a ROM/EPROM externa (chamada de memória de código) quando o 8031 vai fazer uma
busca de instrução na ROM, para, em seguida, executá-la. Também é acionado (sempre
automaticamente) quando se faz uma consulta a alguma tabela fixa, gravada na ROM, por meio de
instrução especial para isto. Note que existe uma barra acima do nome PSEN, indicando que ele é
ativo em nível lógico 0. Ele vai automaticamente para zero toda vez que o 8031 está no estado de
busca de instrução (fetch) para, após isto, decodificá-la e executá-la.
Figura 20 - Ilustração da ligação da EPROM no 8031
Fonte: [NICOLOSI, 2000]
37
•
EA (External Access): É um pino de comando externo, que determina se vamos usar
a ROM / EPROM interna do chip ou se vamos ler somente uma ROM/EPROM externa ao chip. Se
o pino EA estiver em nível lógico 1, o chip lerá sua ROM/EPROM interna, e após acabar todo o
espaço de memória interna, trabalhará automaticamente com a memória ROM/EPROM externa, se
ela existir. Com o pino EA em 0, ele só enxerga memórias ROM/EPROM externas, como mostrado
na figura 20.
•
RST (Reset): É o disparador do chip quando se quer iniciar adequadamente sua
função. Esse pino deve estar no estado 1 por, ao menos, dois ciclos de máquina. Ele organiza os
valores internos do chip para iniciar o trabalho adequadamente e sempre da mesma maneira.
•
XTAL1 e XTAL2 (Cristal/Oscilador): Esse chip tem um sistema de oscilação
interna que só exige do exterior o cristal, de 12MHz no máximo, e dois capacitores para gerar a
oscilação, que se tornará o clock ou padrão de tempo para o microcontrolador trabalhar.
•
Vcc e Vss (Alimentação): É por onde se alimenta o chip: +5 Vdc em Vcc e terra em
Vss.
O microcontrolador 8031 é amplamente conhecido e usado para aplicações diversas, pois
possui uma pinagem simples, é de fácil manuseio e seu funcionamento interno é simplificado.
Porém, nada impede de que seja utilizado outro processador, pois como o sistema se
baseia em computação configurável, basta apenas alguns ajustes na lógica do PLD para que o
sistema funcione com um novo processador.
As principais características do 8031 são:
•
Freqüência máxima de clock de 12 MHz;
•
Até 64 KB de memória de dados externa;
•
128 bytes de RAM interna;
•
Até 64 KB de memória externa de programa;
•
4 portas bidirecionais de E/S, cada uma com 8 bits individualmente endereçáveis,
duas dessas portas (P0 e P2) e parte de uma terceira (P3) ficam comprometidas no
caso de se utilizar qualquer tipo de memória externa;
•
2 temporizadores / contadores de 16 bits;
•
1 canal de comunicação serial (full-duplex);
•
5 fontes de interrupção (dois timers, dois pinos externos e o canal de comunicação
serial) com 2 níveis de prioridade selecionáveis por software;
•
Oscilador de clock interno.
38
4.2 – PLD da Altera
A Altera Corporation é uma das maiores no segmento quando se trata em dispositivos
programáveis, tais como PLD, CPLD, FPGA. Existem inúmeras empresas que fabricam PLDs, mas
optamos pelo dispositivo da Altera principalmente pelo fato de que a UnicenP disponibiliza o Kit
Educacional da Altera, e também por já termos trabalhado com ele.
Utilizou-se um kit educacional EP-1 de PLDs da Altera, mostrada na figura 21, disponível
no Laboratório de Lógica Programável do Curso de Engenharia da Computação do UnicenP, que
contem uma placa pré-montada com dois PLDs (o FPGA EPF10K20R e o CPLD EPM7128S),
sendo que um deles é soldado na própria placa e o outro é removível, o que pode possibilitar a
utilização deste PLD em outra placa com uma outra aplicação. Ao kit também acompanha um cabo
para conexão com o computador através da porta paralela, para programar os PLDs.
Figura 21 – Kit Educacional EP-1 da Altera
Os PLDs que compõem esse kit são o FPGA EPF10K20R e o CPLD EPM7128S, as suas
principais características são descritas na tabela 2. O PLD utilizado em nosso projeto foi o
EPF10K20R devido ao fato dele possuir número suficientes de pinos de E/S, o que não acontece no
EPM7128S .
39
As principais características dos PLDs da Altera que acompanham o kit educacional estão
mostradas na tabela 2.
Tabela 2 – Características dos PLDs
Características
FPGA - FLEX
EPM10K20R
CPLD – MAX
EPM7128S
20000
2500
Pinos de E/S
189
68
tpd(ns)
4,5
6,0
tsu(ns)
2,8
3,4
tco1(ns)
3,1
4,0
222,2
147,1
Gates Disponíveis
fcnt(MHz)
A arquitetura do EPM7128 inclui quatro entradas dedicadas que podem ser usadas para
entrada de propósito geral ou como entradas de high-speed, sinais de controle global (clock, clear, e
dois sinais de output enable) para cada macro-célula e pino de E/S. O Logic Array Block (LAB)
consiste de 16 macro-células e os LABs são ligados entre si através do Programmable Interconnect
Array (PIA), um barramento global é alimentado por todas as entradas dedicadas, pinos de E/S e
macro-células. A macro-célula consiste de três blocos funcionais: o vetor lógico, o seletor da matriz
produto-termo e o registrador programável. Elas podem ser individualmente configuradas para uma
operação lógica seqüencial ou combinatória.
A arquitetura do EPF10K20R é mais complexa e possui uma estrutura mais densa, possui
um Embedded Array Block (EAB) que é um bloco flexível de RAM com registradores nas portas
entrada e saída, e é usado para implementar megafunções, por exemplo, memória eficiente e
funções lógicas especializadas. O EAB é também apropriado para funções como as multiplicações,
vetores escalares e para correção de circuitos, porque é denso e flexível. Essas funções podem ser
combinadas em aplicações, como filtros digitais.
O Logic Element (LE), é a menor unidade de lógica na arquitetura do EPF10K20R, tem
um tamanho compacto que fornece uma utilização mais eficiente. O LE contêm uma entrada com
quatro sinais Look-Up Table (LUT), que é um gerador de função que pode rapidamente computar
qualquer função de quatro variáveis. Cada LE contêm um flip-flop programável com synchronous
enable, um carry chain e um cascade chain.
40
Figura 22 - Diagrama de Blocos do PLD EPF10K20R
O PLD conterá toda a lógica de funcionamento do circuito, a forma como os
processadores trabalham, a forma de como eles acessarão a memória e como as tarefas são dividas
entre eles.
Para o funcionamento em paralelo o PLD se encarregará de controlar os processadores, e
se da desta forma: os microprocessadores fazem os pedidos de acesso à memória pelas portas P0 e
P2 e usando sinais de controle pela porta P3, o PLD recebe os sinais de leitura e escrita dos
processadores, verifica se a posição está livre ou se não está sendo acessada pelo outro processador,
caso sim procurar outra posição ou esperar até que o mesmo tenha liberado a posição, e então
retorna o dado pela porta multiplexada P0.
4.2.1 – Diagramas de Bloco dos Modelos de Memória
A seguir são apresentados os diagramas de bloco dos modelos de memória distribuído e o
compartilhado feitos no software da Altera, o Quartus II.
41
No modelo distribuído, mostrada na figura 23, cada processador possui sua memória, ou
seja, o controle é direto, pois o processador apenas indica qual posição deseja acessar e o PLD
interpreta essa posição seleciona o endereço na memória externa e retorna o dado.
Figura 23 – Diagrama em bloco do modelo distribuído
42
Já no modelo compartilhado, conforme mostrado figura 24, existe apenas uma memória
compartilhada entre os processadores, mas eles podem acessar a memória ao mesmo tempo, desde
que sejam posições diferentes, quando um processador tenta acessar uma posição que está sendo
acessado pelo outro processador ele deve aguardar até que o outro processador libere a posição de
memória.
Figura 24 – Diagrama em bloco do modelo compartilhado
43
5 – Software do computador
Foi desenvolvido um software para o computador (código para x86 for Windows),
utilizando a linguagem de programação C no ambiente Borland Builder, o qual comunicará o
mesmo com o sistema dual através da porta serial. Para a troca de funcionamento interno do PLD,
para modelo distribuído ou compartilhado, é necessário a utilização do software Quartus II da
Altera, para modificar o programa gravado internamente na mesma.
O software, em conjunto com o HyperTerminal, também serve para realizar testes de
comunicação entre o hardware e o computador, com isso é possível rapidamente saber se à parte de
comunicação entre todos os módulos do sistema estão funcionando corretamente e caso não
estejam, o problema é encontrado e solucionado com facilidade, graças a essa interação do sistema
com computador.
Figura 25 – Layout do software do computador
Através desse software o resultado final do cálculo é mostrado no monitor do computador,
como demonstra a figura 25, e sendo assim pode ser comparado o resultado obtido com o resultado
44
calculado por um software confiável e já existente no mercado, como por exemplo o MatLab, para a
análise do comportamento do sistema bem como sua validação.
O software tem quatro botões, um chamado “Random”, o qual gera os coeficientes
aleatoriamente, um outro “Abrir” onde o usuário escolhe um arquivo contendo os coeficientes a
serem calculados, um botão “Iniciar” que dá inicio ao processo de cálculo e por fim um chamado
“Fechar” o qual encerra o programa. Como trabalhamos com microprocessador de 8 bits os valores
possíveis para os coeficientes estarão entre 0 e 255, mas foi padronizado para valores entre -10 e 10,
para gerar resultados mais precisos, e para realizar isso usamos uma função que gerou a tabela 3,
que para cada valor entre 0 e 255 possui um representativo entre -10 e 10, por exemplo, se o
coeficiente a ser calculado é -4,769, então o software envia o valor 64, quando o processador ler o
valor 64, o passa por uma fórmula e por conseguinte identifica que o valor correspondente é -4,769.
Foi feito isso para que se pudessem gerar números negativos e também para criar
resultados mais precisos, pois, se fossem usados valores entre 0 e 255, não seria possível utilizá-lo
em uma aplicação em que se houvessem valores negativos e também os resultados não seriam bons
por não se poderem usar números reais e sim apenas inteiros positivos.
Tabela 3 – Conversão de valores reais para inteiros
Valor Inteiro
Valor Real
Valor Inteiro
Valor Real
Valor Inteiro
Valor Real
Valor Inteiro
Valor Real
0
-9,769
64
-4,846
128
0,077
192
5,000
1
-9,692
65
-4,769
129
0,154
193
5,077
2
-9,615
66
-4,692
130
0,231
194
5,154
3
-9,538
67
-4,615
131
0,308
195
5,231
4
-9,462
68
-4,538
132
0,385
196
5,308
5
6
-9,385
-9,308
69
70
-4,462
-4,385
133
134
0,462
0,538
197
198
5,385
5,462
7
-9,231
71
-4,308
135
0,615
199
5,538
8
-9,154
72
-4,231
136
0,692
200
5,615
9
-9,077
73
-4,154
137
0,769
201
5,692
10
11
-9,000
-8,923
74
75
-4,077
-4,000
138
139
0,846
0,923
202
203
5,769
5,846
12
-8,846
76
-3,923
140
1,000
204
5,923
13
-8,769
77
-3,846
141
1,077
205
6,000
14
-8,692
78
-3,769
142
1,154
206
6,077
15
-8,615
79
-3,692
143
1,231
207
6,154
16
17
-8,538
-8,462
80
81
-3,615
-3,538
144
145
1,308
1,385
208
209
6,231
6,308
18
-8,385
82
-3,462
146
1,462
210
6,385
19
-8,308
83
-3,385
147
1,538
211
6,462
20
-8,231
84
-3,308
148
1,615
212
6,538
21
22
-8,154
-8,077
85
86
-3,231
-3,154
149
150
1,692
1,769
213
214
6,615
6,692
23
-8,000
87
-3,077
151
1,846
215
6,769
24
-7,923
88
-3,000
152
1,923
216
6,846
25
-7,846
89
-2,923
153
2,000
217
6,923
26
-7,769
90
-2,846
154
2,077
218
7,000
45
27
-7,692
91
-2,769
155
2,154
219
7,077
28
-7,615
92
-2,692
156
2,231
220
7,154
29
30
-7,538
-7,462
93
94
-2,615
-2,538
157
158
2,308
2,385
221
222
7,231
7,308
31
-7,385
95
-2,462
159
2,462
223
7,385
32
-7,308
96
-2,385
160
2,538
224
7,462
33
-7,231
97
-2,308
161
2,615
225
7,538
34
-7,154
98
-2,231
162
2,692
226
7,615
35
36
-7,077
-7,000
99
100
-2,154
-2,077
163
164
2,769
2,846
227
228
7,692
7,769
37
-6,923
101
-2,000
165
2,923
229
7,846
38
-6,846
102
-1,923
166
3,000
230
7,923
39
-6,769
103
-1,846
167
3,077
231
8,000
40
41
-6,692
-6,615
104
105
-1,769
-1,692
168
169
3,154
3,231
232
233
8,077
8,154
42
-6,538
106
-1,615
170
3,308
234
8,231
43
-6,462
107
-1,538
171
3,385
235
8,308
44
-6,385
108
-1,462
172
3,462
236
8,385
45
-6,308
109
-1,385
173
3,538
237
8,462
46
47
-6,231
-6,154
110
111
-1,308
-1,231
174
175
3,615
3,692
238
239
8,538
8,615
48
-6,077
112
-1,154
176
3,769
240
8,692
49
-6,000
113
-1,077
177
3,846
241
8,769
50
-5,923
114
-1,000
178
3,923
242
8,846
51
52
-5,846
-5,769
115
116
-0,923
-0,846
179
180
4,000
4,077
243
244
8,923
9,000
53
-5,692
117
-0,769
181
4,154
245
9,077
54
-5,615
118
-0,692
182
4,231
246
9,154
55
-5,538
119
-0,615
183
4,308
247
9,231
56
-5,462
120
-0,538
184
4,385
248
9,308
57
58
-5,385
-5,308
121
122
-0,462
-0,385
185
186
4,462
4,538
249
250
9,385
9,462
59
-5,231
123
-0,308
187
4,615
251
9,538
60
-5,154
124
-0,231
188
4,692
252
9,615
61
-5,077
125
-0,154
189
4,769
253
9,692
62
63
-5,000
-4,923
126
127
-0,077
0,000
190
191
4,846
4,923
254
255
9,769
9,846
No sistema é utilizada a linguagem Assembly e C para 8051, usando o software Keil, para
a programação dos processadores e a linguagem AHDL para o PLD. Nos processadores estarão
todas as rotinas, como, por exemplo, rotina de receber os dados da serial, enviar dados para PLD,
executar o cálculo FFT e suas configurações iniciais, por sua vez no PLD estão rotinas de controle
de sinal dos processadores, de acesso à memória, de divisão de tarefas entre os processadores entre
outras. A figura 26 apresenta uma idéia geral e mais clara de como o sistema funciona.
46
Computador
Processador Mestre
Processador Escravo
Início
Envia “Iniciado”
pela Serial
Não
Espera
“Iniciado”
Sim
Enviar Dados
Gravar Dados
na Memória
Sincronizar
Escravo
Iniciar
Processador
Escravo
Receber Dados
Receber Dados
Algoritmo FFT
Algoritmo FFT
Receber
Resultado do
Processador
Escravo
Somar Resultados
Enviar para o
Computador
Não
Espera
Resultado
Sim
Mostra Resultado
no Computador
Fim
Figura 26 – Fluxograma de funcionamento geral do sistema
47
5.1 - O Algoritmo FFT
O algoritmo de FFT utilizado é o Butterfly, que também é um método gráfico de mostrar
as multiplicações e adições. A notação do fluxo do gráfico é usada aonde o círculo com setas
entrando representa uma adição de dois valores e no fim das setas multiplicado por uma constate. A
constante é um número que aparece ao lado da seta, se não existe um valor então a constante é
tomada como um. A figura 27 mostra um simples exemplo da multiplicação de duas entradas e
soma delas no fim da operação.
Figura 27 – Método gráfico da Butterfly
Usando essa notação podemos construir redes Butterfly que, juntas, realizam a FFT. A
figura 28 mostra o cálculo de duas multiplicações e duas adições complexas, enquanto a figura 29
demonstra uma multiplicação e duas adições complexas.
Figura 28 – Exemplo 1 de Butterfly
Figura 29 – Exemplo 2 de Butterfly
Os dados são enviados para a serial de um dos processadores, o qual se encarregará de
salvar os dados na memória e assim que o número de amostras for igual ao escolhido, o processo de
cálculo da FFT começa e cada processador se encarrega de calcular metade das amostras e assim
que o cálculo for finalizado o resultado é enviado para o computador.
48
6 – Funcionamento do Sistema
O sistema funciona basicamente da seguinte maneira:
1. Escolher a configuração de memória será utilizada, a distribuída ou compartilhada,
para isso se utiliza o software da Altera Quartus II;
2. Definir quais os coeficientes serão enviados, através do software que foi descrito
anteriormente, para o sistema realizar a cálculo da FFT;
3. Então os coeficientes são enviados pela serial, o processador mestre grava-os na
memória através do PLD;
4. Com os coeficientes gravados, então se dá inicio ao processo de cálculo, cada
processador requisita seus dados para realizar o cálculo da FFT;
5. O processador mestre se encarrega de somar o seu resultado com o do processador
escravo e o resultado final é enviado ao computador, que tem um software próprio
desenvolvido com o intuído de mostrar o resultado no monitor.
O PLD usado é o EPM10K20R, pois o EPM7128S possui apenas 68 pinos para serem
usados como E/S e para esse projeto são necessários 110 pinos e como o EPM10K20R possui 189
pinos será o mesmo utilizado.
A seguir segue a descrição dos pinos utilizados pelo PLD EPM10K20R:
•
No processador mestre os pinos da porta P0, P1, P2, P3, menos o RX e o TX que
são usados para a transmissão com o computador, e o pino reset, totalizando um
total de 31 pinos;
•
No microntrolador escravo os pinos da porta P0, P2, P3 e o pino de reset, a porta
P1 é seria utilizada pelo módulo adicional para o processamento dos coeficientes,
totalizando um total de 25 pinos;
•
Para a memória RAM os pinos de controle, de seleção de endereço e de dados
somando 27 pinos e como o sistema possui duas memórias, para poder trabalhar
no sistema distribuído, o total de pinos para as memórias são de 54 pinos;
•
Com isso o total de pinos usados pelo PLD são de 110 pinos como mencionado
anteriormente.
49
Inicialmente se define qual o modelo de memória será utilizado, compartilhado ou
distribuído, e então o modelo definido é gravado na PLD para a respectiva configuração, através do
Quartus II.
A configuração no hardware é a seguinte nos dois microcontroladores 8031, a interrupção
serial, a INT0 e a INT1 ativadas e a taxa da porta serial de 9600 bps funcionando de forma
assíncrona.
Inicialmente o software se encarregará de enviar os coeficientes pela porta serial, para o
processador Mestre, com a mesma taxa no qual os microprocessadores funcionaram, a 9600 bps.
Quando o dado for enviado para o processador é ativada a interrupção serial o qual conterá
uma rotina que se encarregará de captar de 8 bits pela porta P3.0 e repassá-lo para o PLD, ativando
a interrupção da porta P3.4, pela porta P1, assim o PLD seleciona uma posição na memória RAM,
ativa o bit de escrita e grava o dado na memória, esse processo se repetirá até que sejam gravados
1024 dados na memória. Quando esse número for alcançado o processador desativará a interrupção
da porta P3.4 e então o PLD começa a enviar os coeficientes pela porta P1 para os processadores,
no caso 512 amostras para cada, assim conforme os dados são enviados a interrupção INT0 e
ativada nos processadores, o qual conterá a rotina para o cálculo da transformada de Fourier, assim
que o todos os coeficiente forem enviados e processados e o cálculo for finalizado o processador
Mestre se encarregará de somar seu resultado com o resultado do processador Escravo e envia o
resultado final serialmente pela porta P3.1. O software do computador então capta o resultado que
foi calculado pelos processadores mostra na tela.
Para se alterar o número de amostras a serem processados pelo algoritmo de FFT deve-se
alterar um “define” chamado “NAmostras”, que se encontra no início do código do processador
Mestre e no início do código do processador Escravo, para o número de amostras desejados,
compilar o código e regrava-lo na EPROM.
O sistema se limita a processar dados reais de -10 a 10 conforme a tabela 4 e como
comentado anteriormente, a taxa de transmissão serial a 9600 bps e devido ao processador trabalhar
a 11,0592MHz a maior freqüência do espectro não deve ser maior que 5MHz, segundo o teorema de
Nyquist visto no capítulo 2 (estudo teórico), caso contrário o cálculo da FFT não será calculado de
maneira correta, pois haverá sobreposição espectral.
50
7 – Recursos Necessários
Os recursos utilizados estão disponíveis no Laboratório de Lógica Programável do Curso
de Engenharia da Computação do UnicenP.
Na realização desse projeto foram necessários os seguintes recursos:
1 – Hardware:
•
Microcomputador (Pentium III 500MHz, RAM 64MB);
•
Microcontroladores 8031;
•
Kit Educacional da Altera (EPM7128S e EPF10KR);
•
Componentes eletrônicos diversos.
2 – Software:
•
Ambiente de programação em C++ (Borland Builder C++ v5.0);
•
Ambiente para estudo e desenvolvimento das Séries de Fourier – DFT / FFT
(MatLAB v6.5);
•
Ambiente de desenvolvimento de lógica da Altera (Quartus II v4.1);
•
Ambiente para a programação em Assembly para 8051 (Keil v2.7);
•
Ambiente de desenvolvimento do esquemático (OrCad v10.0).
3 – Equipamentos:
•
Osciloscópio digital e analógico;
•
Multímetro digital e analógico;
•
Emulador de EPROM;
•
Apagador de EPROM;
•
Gravador de EPROM;
•
Ferro de Solda;
•
Protoboards.
51
8 – Custos e Viabilidade Econômica
Os custos calculados na tabela 4 se baseiam na construção de um sistema.
Tabela 4 – Custos do Projeto Físico
Descrição
Microcontroladores 8031 (2)
Preço (R$)
12,00
Kit Educacional Altera
570,00
EPROM 64Kbytes (2)
14,00
NVRAM 128Kbytes (2)
48,00
Latch 74LS373 (2)
Placa 8031/EPROM (2)
2,00
24,00
Cabo Serial (2)
8,00
Cristal 11,052MHz (2)
2,00
Capacitores Diversos
2,40
Resistores Diversos
2,40
Componentes Eletrônicos
TOTAL
15,00
R$ 699,80
Vemos que o custo do desenvolvimento do projeto ficaria em torno de R$ 700,00, o tempo
gasta para desenvolver o projeto foi em torno de 1000h, só para efeito de comparação uma placa
dual para um processador Pentium III custa perto de R$ 510,00, o que encarece muito o sistema é a
construção de apenas um sistema e também a utilização do kit educacional da Altera, que inclui
diversos componentes desnecessários ao nosso projeto, se ao invés fosse usado apenas o PLD e
feito uma construção em larga escala o circuito sairia por menos de R$ 350,00.
Na figura 30 temos o cronograma geral do projeto, com todas as fases e etapas descritas.
52
Figura 30 – Cronograma do projeto
53
9 – Testes e Validação do Projeto
A validação do projeto foi realizada em 5 etapas, listadas a seguir:
•
Teste da Comunicação:
Primeiramente foi testada a comunicação serial entre o computador e o
sistema, utilizando um software já existente, como HyperTerminal, o qual
envia um dado pela porta serial. Caso o sistema esteja funcionando
corretamente o mesmo responderá reenviando o dado para o computador, e
sendo assim passa-se para próxima fase de testes;
•
Teste Lógico do Software:
Para verificação do funcionamento do software do PLD e do software do
computador é utilizado o próprio ambiente de programação no caso o Quartus
II e o Borland Builder respectivamente, os quais nos dão total suporte para
testes, depuração e validação dos softwares. Quanto ao programa feito para o
computador não foi encontrado problema algum, porém em se tratando do
PLD tive grandes dificuldades, principalmente no modelo compartilhado o
qual requer uma lógica muito mais complexa e elaborada que a do modelo
distribuído;
•
Teste dos Processadores:
Para testar os processadores, são realizados testes de leitura e escrita, em cada
processador separadamente. Com um software já existente, um dado é escrito
na memória e depois o mesmo é lido, caso os dados sejam iguais e então é
validado o funcionamento do conjunto processador-memória bem como as
rotinas feitas em C para 8051 no software Keil. Já nesta parte de validação
ocorreram alguns problemas, como o programa compila o código C para
Assembly pode haver algum tipo de falha nessa conversão, em poucos casos
o programa funcionava corretamente quando depurado pelo próprio software,
54
mas quando foi testado o software no hardware algumas vezes ele não
funcionou corretamente, em torno de 10% das tentativas foram problemáticas.
•
Teste de Funcionamento:
Em seguida realizar os testes para checar o funcionamento dos processadores
rodando em no modo seqüencial e paralelo, neste utilizando-se a arquitetura
do modo com memória distribuída e em seguida com o modo de memória
compartilhado, para a troca do modelo de funcionamento é utilizado o
Quartus II, os resultados obtidos pelo modo seqüencial devem ser iguais aos
obtidos pelo modelo dual. Nesta parte do projeto o principal problema foi
sincronizar os dois processadores;
•
Teste de Operação (Resultados):
Para checar o resultado final, basta usar um programa que faça o cálculo da
transformada de Fourier corretamente, como o MatLab, aplicar um conjunto
de coeficientes e guardar o resultado. Depois usando os mesmos coeficientes
passá-los para que o sistema proposto faça o cálculo, e por fim analisar e
comparar os resultados, se forem encontrados resultados semelhantes o
sistema está validado. O principal problema aqui foi que às vezes os
resultados estavam certos e outras vezes não, grande parte do problema é a
falta de sincronismo entre os processadores, e/ou problemas na comunicação
serial e/ou erros no acesso a memória.
55
10 – Resultados
Os testes foram realizados a partir de um conjunto de dados já conhecido, e foram os
seguintes, uma função cujos valores são todos iguais a zero, outra com os valores iguais a um, uma
a qual se tem o primeiro valor igual a um e o restante igual a zero e uma última função randômica
na qual os valores são gerados aleatoriamente. Utilizando esses conjuntos de dados é possível obter
uma confirmação positiva do sistema e sendo assim, a sua possível validação.
Foi feita a alteração no número de amostras calculadas para que se fosse possível a análise
do comportamento e desempenho do sistema nos diferentes modelos. Para a mudança no número de
amostras é necessário que seja feita a alteração no firmware do processador Mestre e também na do
Escravo, e então recompilar o código e por fim gravá-lo na EPROM novamente.
No modelo monoprocessado foi usado o mesmo algoritmo de FFT, sendo alterado no
algoritmo apenas para que a tarefa não seja divida como ocorre no modelo dual.
Os resultados obtidos foram a partir dos cálculos da FFT no modelo seqüencial, no modelo
dual com modelo de memória compartilhado e também no modelo distribuído, com amostras
variando de 16 a 1024 amostras conforme mostra a figura 31 e tabela 5.
Tabela 5 – Tempos para o cálculo da FFT
MODELO \ NAMOSTRAS
16
32
64
128
256
512
1024
Monoprocessado
0,17s 0,37s 0,79s 1,69s 3,52s 7,19s 14,79s
Multiprocessado Dual - Distribuído
0,10s 0,22s 0,47s 1,01s 2,12s 4,35s
9,01s
Multiprocessado Dual - Compartilhado 0,10s 0,22s 0,47s 1,01s 2,12s 4,35s
9,01s
Os resultados obtidos variam um pouco, entre todos os modelos testados, de computador
para computador e, às vezes no mesmo computador, por diversos motivos como, por exemplo,
quando está executando outras atividades ou atendendo a uma interrupção, mas sempre variavam
menos que 5%, por essa razão o resultado aqui mostrado é uma média de várias amostras
calculadas.
56
16
Monoprocessado
14
Dual - Distribuído
Tempo(s)
12
Dual - Compartilhado
10
8
6
4
2
0
16
32
64
128
Amostras
256
512
1024
Figura 31 - Gráfico do desempenho entre os modelos de processamento
Como esperado o resultado obtido pelos modelos duais foram superiores, em geral perto de
60 a 70%, ao modelo seqüencial, e também como esperado o modelo dual compartilhado e o
distribuído tiveram o mesmo resultado, pois no modelo compartilhado um processador não invade a
memória do outro em algum momento, devido ao fato de como o algoritmo foi feito, portanto o
resultado é o mesmo e quase não é possível a sua percepção no gráfico, porque uma linha sobrepõe
a outra.
71
70
69
Ganho (%)
68
67
66
65
64
63
62
16
32
64
128
Amostras
256
512
1024
Figura 32 – Gráfico do Speed-UP
57
Com esses dados é possível traçar um gráfico de speed-up, como mostrado na figura 32,
entre os modelos monoprocessado e o dual, a função que resultou no gráfico é bem simples, basta
apenas dividir o tempo levado pelo modelo monoprocessado para o cálculo da FFT pelo tempo
levado pelo sistema dual. Pode-se notar que para 16 amostras temos um ganho em torno de 70% e
para 1024 amostras um ganho de 65%, o que demonstra que quanto maior o número de amostra
menos eficiente é o sistema.
16
Monoprocessado
Dual - REAL
Dual - IDEAL
14
Tempo (s)
12
10
8
6
4
2
0
16
32
64
128
256
512
1024
Amostras
Figura 33 – Gráfico que mostra a diferença entre o tempo real e o ideal
Com a figura 33, é possível perceber uma grande diferença, entre o tempo obtido com o
cálculo nos diversos modelos e o tempo ideal, o ideal seria o tempo onde não ocorrem atrasos de
comunicação, de sinais de controle, de sincronismo ou qualquer outro empecilho que venha a
prejudicar o desempenho do sistema, ou seja, o ganho seria linear e proporcional ao número de
processadores, porém isso não ocorre, pois o tempo que o processador consome pra calcular um
determinado número de amostras não é linear a este, e isto se agrava quando se está trabalhando
com processamento envolvendo mais de um processador, pois se gerar diversos tipos de atrasos
como mencionados acima.
Agora é possível traçar um gráfico, vide figura 34, entre o modelo dual real e o modelo
dual ideal, como no gráfico anterior de speed-up, este é calculado da seguinte maneira, basta dividir
o tempo levado pelo modelo dual ideal para o cálculo da FFT pelo tempo levado pelo sistema dual
real. Nota-se que para 16 amostras o modelo dual real comporta-se aproximadamente a 85% do
modelo dual ideal e para 1024 amostras um comportamento perto de 82%, o que demonstra que
quanto maior o número de amostra mais longe do ideal o sistema se parece.
58
86
Ganho (%)
85
84
83
82
81
80
16
32
64
128
Amostras
256
512
1024
Figura 34 – Gráfico de Speed-UP entre os Sistemas Duais
Para a avaliação do resultado foi utilizado o MatLab, foi analisado um conjunto de 16
amostras, foram repassados esse dados para o sistema aqui projetado e para MatLab, e os resultados
obtidos são demonstrados na tabela 6 e também na figura 35 e figura 36.
Tabela 6 – Resultado do Sistema x MatLab
Númedo da
Amostra
Coeficientes
Enviados
Resultado
Sistema
Resultado
MATLab
1
0,4615
16,5380
16,5385
2
9,6923
18,0840
18,0843
3
3,0000
36,3400
36,3401
4
8,6923
9,7560
9,7561
5
0,3077
5,7177
5,7177
6
-1,6154
9,6061
9,6063
7
0,0000
15,0190
15,0195
8
-6,1538
23,2710
23,2706
9
1,6154
36,0770
36,0769
10
8,0769
23,2710
23,2706
11
-0,3077
15,0190
15,0195
12
3,6154
9,6061
9,6063
13
-7,5385
5,7177
5,7177
14
-0,1538
9,7560
9,7561
15
-7,3077
36,3400
36,3401
16
4,1538
18,0840
18,0843
59
Com isso é possível analisar que o resultado obtido pelo sistema, figura 36, é muito
próximo ao obtido pelo MatLab, figura 35, sendo apenas diferenciado na quarta casa decimal, isso
demonstra que o todo o processo de acesso a memória, sincronismo entre os processados e as
rotinas de cálculo da FFT estão funcionando perfeitamente.
Figura 35 – Tela do MatLab com o resultado com um teste
Figura 36 – Resultado obtido pelo software
60
11 – Conclusão
Computação configurável é comprovadamente importante e viável, geralmente implicando
vantagens econômicas, a principal vantagem da utilização da computação configurável é que o
desempenho obtido é muito parecido com as implementações de soluções em hardware fixo com a
flexibilidade das implementações de soluções em hardware programável.
Entre as principais aplicações que tem se beneficiado com o uso da computação
configurável podemos destacar algumas aplicações como, manipulação de informação digitalizada,
manipulação e processamento de imagens digitais, compactação e compressão de dados e sinais,
criptografia, processamento de sinais, imagens e vídeos e reconhecimento de padrões.
Esperar pelo aumento da capacidade de processamento dos computadores pode não ser
viável, pois a razão de crescimento desta capacidade tem diminuído e chegará ao seu limite, devido
aos limites físicos dos materiais. Uma solução seria pensar em multiprocessamento, que nos últimos
anos vem crescendo muito em uso e em disponibilidade de recursos.
O uso do processamento paralelo e é uma ferramenta extremamente poderosa, possibilitando
o alcance de um alto poder de processamento em sistemas de baixo custo.
O projeto foi divido em várias etapas, a primeira delas foi o embasamento teórico, pois, para
a realização de um projeto desse porte, há a necessidade de se dominar o assunto e a tecnologia
envolvida, e como todos os assuntos envolvidos no projeto eram novos, essa parte do projeto tomou
muito tempo e empenho.
Na seqüência foi definido qual algoritmo FFT seria utilizado, foi um processo bem
demorado também, porque havia a necessidade de se utilizar um algoritmo simples e que fosse
eficiente e rápido para rodar no microcontrolador 8031, e o escolhido foi o butterfly devido o seu
bom desempenho e também pela fácil implementação, visto que o objetivo principal deste projeto
não o algoritmo, já com o algoritmo já definido então foi possível dar inicio a montagem física do
projeto.
Os problemas começaram a aparecer quando a parte do modelo compartilhado de memória
começou a ser desenvolvida, pois, este modelo é muito mais complexo e consumiu muito mais
tempo que o esperado. Outro problema também é quanto ao sincronismo entre os processadores,
que na teoria parece ser fácil de ser resolvido, mas quando é se passa para a parte da
implementação, a situação é totalmente outra.
61
Conforme os problemas eram solucionados, os resultados começaram a aparecer, e todo o
trabalho que se teve no decorrer do ano começa a valer a pena e consequentemente a ser validado, e
assim nota-se a importância de um trabalho como esse, não apenas pelos resultados obtidos, que
comprovam que a computação configurável e o processamento paralelo não são apenas viáveis, mas
como as novas tecnologias a serem utilizadas no dia-a-dia, mas sim pelo aprendizado que se obteve
no decorrer do ano.
O projeto poderia ter algumas melhorias tais como, ao invés de se utilizar uma memória
externa, se usar a própria memória interna do PLD, o que reduziria os custos e facilitaria no
desenvolvimento do projeto, outra melhoria seria a implementação dos dois modelos de memória de
uma vez no PLD, sendo assim a troca de funcionamento poderia ser realizado pelo próprio
software, sem que haja a necessidade da regravação do outro modelo de memória.
O módulo adicional que tem como finalidade agregar mais funções ao projeto caso este seja
finalizado antes do tempo previsto e que neste projeto o módulo adicional seria encarregado de
passar ao processador escravo os coeficientes a serem calculados pelo algoritmo de FFT não foi
implementado pela falta de prazo.
Para o futuro pode-se alterar esse projeto para um número maior de processadores, bem
como o processador em si, usando essa mesma estrutura é possível trabalhar com até quatro
processadores, bastante apenas utilizar os pinos de E/S que estiverem livres e também a lógica
interna ao PLD, caso se necessite um número maior de processadores e preciso alterar o PLD ou
integrar mais de um.
E possível também alterar a quantidade de amostras com que o sistema pode lidar, sendo
esse sistema capaz de trabalhar com até 8192 amostras para isso devesse alterar o algoritmo de FFT,
e se não for o suficiente pode-se também expandir o tamanho da memória de dados, tendo então que
se alterar a lógica do PLD bem como o algoritmo de FFT.
Com tantas mudanças possíveis e caso venham a ser efetuadas, há a possibilidade de se
atender uma gama maior de aplicações tornando assim o projeto muito interessante e viável.
62
Referências Bibliográficas
[CARVALHO, 2002] Carvalho, E. L. S. Reconfiguração Dinâmica e Parcial de Hardware:
Modelos, Classificações e Dispositivos. s.l. 2002.
[CARVALHO, 2003] Carvalho, E. L. S. RSCM: Controlador de Configurações para Sistema de
Hardware Reconfigurável . s.l. 2003.
[CHEN, 2000] Chen, C. Digital Signal Processing: Spectral Computation and Filter Design. s.l.
s.ed. 2000.
[CULLER, 1999] Culler, D. E. Parallel Computer Architecture: A Hardware/Software Approach.
s.l. s.ed. 1999.
[FERLIN, 1998a] Ferlin, E. P. O Processo de Paralelização Automática de Programas
Seqüenciais em Programas Paralelos. Curitiba, 1998.
[FERLIN, 1998b] Ferlin, E. P. Vantagens na Elaboração de Projetos Digitais Utilizando
Dispositivos Lógicos Programáveis. Curitiba, 1998.
[FOURIER, 2004a] Fourier and the Frequency Domain. http://www.spd.eee.strath.ac.uk/
~interact/fourier/fourier.html - 11/03/2004.
[FOURIER, 2004b] As Séries de Fourier - Departamento de Física da Universidade Federal do
Ceará. http://www.fisica.ufc.br/fourier/fourier1.htm - 20/03/2004.
[JACKSON, 1986] Jackson, L. B. – Digital Filters and Signal Processing. s.l. s.ed. 1986.
[KUO, 2001] Kuo, S. M.; Lee, B. H. Real-Time Digital Signal Processing: Implementations,
Applications and Experiments. s.l. s.ed. 2001.
[MARTINS, 2003] Martins, C. A. P. S.; Ordonez, E. D. M.; Corrêa, J. B. T.; Carvalho, M. B.
Computação Reconfigurável: Conceitos, Tendências e Aplicações. s.l. s.ed. 2003.
[MORON, 2004] Moron, C. E.; Saito, J. H.; Abib, S.; Mucheroni, M. L.; Furuya, N.; Battaiola, A.
Parallel
Architecture
Using
DSPs.
http://www.lac.inpe.br/~celso/pad/ufscar.html
-
23/03/2004.
[NICOLOSI, 2000] Nicolosi, D. E. C. Microcontrolador 8051 Detalhado. São Paulo. Érica, 2000.
[OPPENHEIM, 1998] Oppenheim, A. V.; Schafer, R. W.; Buck, J. R. Discrete-Time Signal
Processing. s.l. s.ed. 1998.
[QIAN, 1999] Qian, S. Joint Time-Frequency Analysis: Methods and Application. s.l. s.ed. 1999.
63
[RIVER,
2004]
River,
W.
Re-Configurable
Computing.
http://www.windriver.com/
whitepapers/reconfigurable_computing.html - 11/03/2004.
[SMITH, 2004] Smith, J. O. III Mathematics of the Discrete Fourier Transform. http://ccrmawww.stanford.edu/~jos/mdft/index.html - 21/03/2004.
[VILLASENOR, 2004] Villasenor, J.; Mangione-Smith, W. H. Configurable Computing.
http://xputers.informatik.unikl.de/reconfigurable_computing/ villasenor/0697villasenor.html
- 11/03/2004.
[YADAV, 1996] Yadav, N. S. Design of Dual i486 Processor Card. Department of Computer
Science and Engineering, Indian Institute of Tecnology, Bombay, Índia, 1996.
[ZELENOVSKY, 2004] Zelenovsky, R.; Mendonça, A. Processadores Para o Próximo Milênio.
http://www.clubedohardware.com.br/ milenio1.html - 23/03/2004.
[ZUIM, 2002] Zuim, R. L. Resolução de Problemas de Satisfabilidade Usando Arquiteturas
Reconfiguráveis. s.l. s.ed. 2002.
64