Upload
others
View
13
Download
1
Embed Size (px)
Citation preview
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 requi
do Curso de Engenharia da Comput
Universitário Positivo, pela seguinte banca examinador
Prof. Edson Pedro Ferlin (Orientador)
Prof. Álvaro Cantieri
Prof. Valfredo Pilla Jr
sito parcial à conclusão
ação (Matutino) do Centro
a:
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
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
Figura 31 – Gráfico do desempenho entre os modelos de processamento .....................................57
6
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):
N
TppT
TGP
⋅−+
=)1(
ou
N
pp
GP)1(
1−
+=
(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.
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
0
10
20
30
40
50
60
70
80
90
100
Número de Processadores
Gan
ho
no
Pro
cess
amen
to
1 - p=0%
2 - p=0,1%
3 - p=1%
4 - p=10%
0 20 40 60 80 100
1
2
3
4
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.
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.
Repositório de Configurações
Controlador de Configurações
Aplicação
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
0
)(1
)(n
n
mnWnxN
mX (4)
onde:
NieW /2π−= (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):
)2/(1 mfT ⋅≤ (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.
Figura 12 – Estrutura geral do sistema lógico
Modulo Adicional
Serial Serial
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.
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.
a) b)
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.
Figura 14 – Diagrama em Blocos do Sistema
Porta Serial
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.
Figura 15 – Foto do Projeto Físico
Kit Altera
Kit Altera
Processador Escravo
Processador Mestre
Memória Externa
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
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]
8031
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 do Pino
Função 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:
Memory write strobe Usado quando se conecta RAM externa no chip. Sinaliza que o Mp vai "escrever" na RAM
P3.7 17 RD E/S External Data:
Memory read strobe Usado quando se conecta a RAM externa no 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
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.
Características FPGA - FLEX EPM10K20R
CPLD – MAX EPM7128S
Gates Disponíveis 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
fcnt(MHz) 222,2 147,1
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 -9,385 69 -4,462 133 0,462 197 5,385
6 -9,308 70 -4,385 134 0,538 198 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 -9,000 74 -4,077 138 0,846 202 5,769
11 -8,923 75 -4,000 139 0,923 203 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 -8,538 80 -3,615 144 1,308 208 6,231
17 -8,462 81 -3,538 145 1,385 209 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 -8,154 85 -3,231 149 1,692 213 6,615
22 -8,077 86 -3,154 150 1,769 214 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 -7,538 93 -2,615 157 2,308 221 7,231
30 -7,462 94 -2,538 158 2,385 222 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 -7,077 99 -2,154 163 2,769 227 7,692
36 -7,000 100 -2,077 164 2,846 228 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 -6,692 104 -1,769 168 3,154 232 8,077
41 -6,615 105 -1,692 169 3,231 233 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 -6,231 110 -1,308 174 3,615 238 8,538
47 -6,154 111 -1,231 175 3,692 239 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 -5,846 115 -0,923 179 4,000 243 8,923
52 -5,769 116 -0,846 180 4,077 244 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 -5,385 121 -0,462 185 4,462 249 9,385
58 -5,308 122 -0,385 186 4,538 250 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 -5,000 126 -0,077 190 4,846 254 9,769
63 -4,923 127 0,000 191 4,923 255 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
Envia “Iniciado” pela Serial
Enviar Dados
Gravar Dados na Memória
Iniciar Processador
Escravo
Sincronizar Escravo
Receber Dados
Algoritmo FFT
Receber Dados
Algoritmo FFT
Receber Resultado do Processador
Escravo
Fim
Início
Espera “Iniciado”
Sim
Não
Somar Resultados
Enviar para o Computador
Espera Resultado
Mostra Resultado no Computador
Sim
Não
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 Preço (R$)
Microcontroladores 8031 (2) 12,00
Kit Educacional Altera 570,00
EPROM 64Kbytes (2) 14,00
NVRAM 128Kbytes (2) 48,00
Latch 74LS373 (2) 2,00
Placa 8031/EPROM (2) 24,00
Cabo Serial (2) 8,00
Cristal 11,052MHz (2) 2,00
Capacitores Diversos 2,40
Resistores Diversos 2,40
Componentes Eletrônicos 15,00
TOTAL 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
0
2
4
6
8
10
12
14
16
16 32 64 128 256 512 1024Amostras
Tem
po
(s)
Monoprocessado
Dual - Distribuído
Dual - Compartilhado
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.
62
63
64
65
66
67
68
69
70
71
16 32 64 128 256 512 1024Amostras
Gan
ho
(%
)
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.
0
2
4
6
8
10
12
14
16
16 32 64 128 256 512 1024Amostras
Tem
po
(s)
MonoprocessadoDual - REALDual - IDEAL
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
80
81
82
83
84
85
86
16 32 64 128 256 512 1024Amostras
Gan
ho
(%
)
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://ccrma-
www.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
Anexo I – Fluxogramas
65
Fluxograma geral de funcionamento do sistema
Computador Processador Mestre Processador Escravo
Envia “Iniciado” pela Serial
Enviar Dados
Gravar Dados na Memória
Iniciar Processador
Escravo
Sincronizar Escravo
Receber Dados
Algoritmo FFT
Receber Dados
Algoritmo FFT
Receber Resultado do Processador
Escravo
Fim
Início
Espera “Iniciado”
Sim
Não
Somar Resultados
Enviar para o Computador
Espera Resultado
Mostra Resultado no Computador
Sim
Não
66
Fluxograma do software do computador
Início
Selecionar os Coeficientes
Enviar os Coeficientes pela Serial
Receber e Mostrar o Resultado no Monitor
Fim
Enquanto Recebido !=
“Iniciado”
Não
Sim
Esperar o Cálculo da FFT
Sim
Não
67
Fluxograma do processador Mestre
68
Fluxograma para gravar os dados (Rotina A)
Inicio
Requisão para Gravar
(Porta P3.4)
Dado Captado (Porta P1)
Ativar Escrita na Memória RAM
Selecionar Endereço na RAM
Enquanto Coeficientes <> Fim
Fim
Gravar Dado
Desativar Requisição (Porta P3.4)
Não
Sim
69
Fluxograma para cálculo da FFT (Rotina B)
Inicio
Iniciar Cálculo (Porta P3.5)
Ativa INT0
Desativa Cálculo (Porta P3.5)
Enquanto Coeficientes <> Fim
Seleciona Endereço na RAM
Ativa Escrita
Grava Resultado
Fim
Não
Sim
PLD Envia Dado (Porta P1)
Processa Cálculo
70
Fluxograma para o envio do resultado (Rotina C)
71
Fluxograma do processador Escravo
Início
Receber Dados Para Cálculo
Algoritmo FFT
Enviar Resultado para Mestre
Fim
Esperar Sincronismo
Sim
Não
Esperar Processador
Mestre
Sim
Não
72
Anexo II – Resumo dos DataSheets dos demais Componentes
73
EPROM
Figura 1 – Pinagem da EPROM 27C512
Para se realizar a leitura de um dado na EPROM deve-se primeiro saber qual é o endereço
desejado (A0 a A15) e em segundo os pinos E e G/Vpp devem estar com sinal baixo, feito isso os
dados estarão nos pinos DQ0 a DQ7. Possui 64KB de memória
A programação da EPROM ocorre quando o pino G/Vpp estiver com uma tensão de 13
volts e o pino E estiver em sinal baixo, sendo assim escolhe-se o endereço em qual se deseja gravar
(A0 a A15) e o dado que se deseja gravar entram pelos pinos DQ0 a DQ7.
Quando duas ou mais saídas estão conectadas em paralelo no mesmo barramento a saída
de qualquer dispositivo particular no circuito pode ser lida sem interferência das saídas dos outros
dispositivos. Para ler a saída de um único dispositivo, um sinal baixo é aplicado para os pinos E e
G/Vpp.
Todos os outros dispositivos no circuito devem ter suas saídas desabilitadas aplicando-se
um sinal alto para um destes pinos. O dado de saída é acessado pelos pinos DQ0 até DQ7.
Antes de se programar uma EPROM é necessário zerá-la, e para realizar este processo
deve-se expor a EPROM a raios ultravioletas (comprimento de onda de 2537Å). É recomendado
uma exposição de aproximadamente 21 minutos para uma intensidade de 15 Ws/cm2, depois de
zerada todos os bits ficam em estado lógico alto.
A programação pode ser desabilitada mantendo-se um sinal alto no pino E. Os bits
programados podem ser verificados quando G/Vpp e E estão em nível baixo.
Legenda:
A0–A15 Entrada de Endereços
E Chip Enable
DQ0–DQ7 Entrada (Programação) / Saídas
G/VPP Tensão de Programação (13 Volts)
GND Terra
VCC Tensão de Alimentação (5 Volts)
74
NVRAM
Figura 2 – BQ4013
O BQ4013 é uma RAM não-volátil, ou seja, possui uma alimentação interna que
proporciona que os dados uma vez gravados continuem lá, mesmo quando o circuito for desligado,
de 128Kbytes. Internamente a NVRAM possui uma bateria de lítio, para que quando haja
problemas de tensão no VCC o circuito passe a ser alimentado por essa bateria até que o VCC volte
ao estado normal de tensão.
Para escrever um dado na NVRAM é necessário que os pinos CE e o OE estejam em nível
lógico baixo o pino WE em nível lógico alto, com isso setado deve-se escolher o endereço que se
deseja acessar pelos pinos de A0 a A16 e os dados estaram nos pinos de D0 a D7, e para se ler um
dado os pinos CE e WE devem estar em nível lógico baixo e escolhe-se o endereço que se deseja
acessar pelos pinos de A0 a A16 e os dados estaram nos pinos de D0 a D7.
Legenda:
A0–A16 - Entrada de Endereço DQ0–DQ7 - Saída/Entrada do Dado
CE - Chip Enable OE - Output Enable
WE - Write enable NC - Sem Conexão
VCC - Alimentação VSS - Terra
75
Latch
O latch 74LS373 consiste em oito latches com 3 estados de saída. Os flip-flops ficam
transparentes ao sistema quando o Clock está em nível lógico alto. Quando Clock está em nível
lógico baixo, o dado é guardado. Os flip-flops voltam a ficar transparentes quando o Clock volta ao
nível lógico baixo. Quando Output Control (OE) está em nível lógico alto à saída do barramento
fica em estado de alta impedância. A tabela 1 contém a tabela verdade do latch.
Tabela 1 – Tabela lógica do latch 74LS373
Figura 3 – Pinagem do latch 74LS373
Entradas Saída
OC C† D Q
0 1 1 1
0 1 0 0
0 0 X Q0
1 X X Z
Legenda:
OC – Output-Control C† – Clock.
D – Entrada do Dado Q – Saída do Dado X – Não importa Z – Alta Impedância
76
Anexo III – Listagem dos Códigos
77
Programa do computador //------------------------------------------------------- // Nome: Listagem dos códigos para o software do Computador // Linguagem: C/C++ - Borland Builder //-------------------------------------------------------
//------------------------------------------------------- // Classe Port // Classe necessária para a utilização // da porta serial do computador //------------------------------------------------------- class Port { private: DCB dcbStatus; // contém as configuracoes da porta de comunicacao BOOL fSucesso; // flag para a verificacao de sucesso da ultoma operacao char Porta[5]; int BaudRate,erro; HANDLE hComm; // handle para a porta de comunicacao COMMTIMEOUTS Timeouts; // contém as informações de timeouts da porta de comunicação public: Port(void); Port(char*); ~Port(void); int Ret_erro(); void enviatexto(char); char recebetexto(void); }; Port :: Port(char* setaporta) { strcpy(Porta,setaporta); erro=0; BaudRate = 9600; // Tenta abrir a porta de comunicação... hComm = CreateFile(Porta,GENERIC_READ | GENERIC_WRITE,0,NULL,OPEN_EXISTING,0,NULL); // Se houve um erro, vê o que aconteceu... if(hComm == INVALID_HANDLE_VALUE) { erro=1; } // Le as configurações da porta recém aberta fSucesso = GetCommState(hComm, &dcbStatus); if(!fSucesso) { CloseHandle(hComm); // fecha a porta de comunicação... erro=2; return; } dcbStatus.BaudRate = BaudRate; dcbStatus.ByteSize = 8; dcbStatus.Parity = NOPARITY; dcbStatus.StopBits = ONESTOPBIT; fSucesso = SetCommState(hComm, &dcbStatus); if(!fSucesso) { CloseHandle(hComm); // fecha a porta de comunicação... erro=3; return; } fSucesso = SetCommTimeouts(hComm, &Timeouts); if(!fSucesso) { CloseHandle(hComm); // fecha a porta de comunicação... erro=4; return; } } Port :: ~Port() { if (erro==0) CloseHandle(hComm); }
78
int Port :: Ret_erro() { return(erro); } void Port :: enviatexto(char texto) { char buffer = texto; DWORD charsWritten = 0; erro=0; if ( !WriteFile ( (HANDLE(hComm)) , &buffer , sizeof(char) , &charsWritten , NULL) ) { erro=1; } } char Port :: recebetexto(void) { char buffer; DWORD charsRead = 0; if (! ReadFile ( (HANDLE(hComm)) , &buffer , sizeof(char) , &charsRead , NULL) ) { erro=5; return '0'; } return buffer; } //------------------------------------------------------- // Botão Random // Gerar os coeficientes aleatoriamente //-------------------------------------------------------
char Aux; M_Coe->Clear(); // Memo dos Coeficientes for(int i=0;i<NAmostras;i++) { Randomize();
CoefRI[i] = random(255); // Gerar numero aleatório de 0 a 255 CoefRF[i] = (float) (CoefRI[i] - 127) / 13; // Números entre -10.0 a 10.0 - Parte Real CoefII[i] = 0; // 0 - Parte Imaginária M_Coe->Lines->Add(FormatFloat("0.0000", CoefRF[i])); // Imprime no Memo os Coeficientes Gerados } //------------------------------------------------------- // Botão Abrir // Lê os coeficientes a partir de um arquivo //------------------------------------------------------- unsigned char a; int i; FILE *Coefs; // Arquivo com os Coeficientes M_Coe->Clear(); // Memo dos Coeficientes if(OD->Execute()) { if((Coefs = fopen(OD->FileName.c_str(), "rt")) == NULL) // Testar se Arquivo é Válido { Application->MessageBox("Erro", "Erro ao abrir o Arquivo", 64); } i = 0; a = fgetc(Coefs); while (a != 255) { CoefRI[i] = ((a-48)*13)+127; // Gerar Números entre -10.0 a 10.0
79
CoefII[i] = 0; // 0 - Parte Imaginária fgetc(Coefs); a = fgetc(Coefs); M_Coe->Lines->Add(FormatFloat("0.0", CoefRF[i])); // Imprime no Memo os Coeficientes Lidos i++; } fclose(Coefs); } //------------------------------------------------------- // Botão Iniciar // Envia, byte a byte, os coeficientes gerados ou lidos pela serial a uma // taxa de 9600 bps, calcula o tempo do processamento da FFT e // recebe o resultado, byte a byte, e imprime na tela //------------------------------------------------------- char Aux; int cont=0; AnsiString Resultado; TDateTime Tempo; WORD Hora, Min, Seg, Mseg; TimeSeparator = '-'; Do // Função para receber o “Iniciado” { Aux = Serial->recebetexto(); Resultado = Resultado + Aux; }while(Aux != '\n'); M_Res->Clear(); // Memo do Resultado M_Res->Lines->Add(Resultado.SubString(1,Resultado.Length()-1)); // Imprime o “Iniciado” no Memo Resultado = ""; for(int i=0;i<NAmostras;i++) // Envia os Coeficientes pela Serial { Serial->enviatexto(CoefRI[i]); Serial->enviatexto(CoefII[i]); } Tempo = Now(); // Seta o Tempo Aux = Serial->recebetexto(); Tempo = Now() - Tempo; // Calcula o tempo do Processo de Cálculo DecodeTime(Tempo, Hora, Min, Seg, Mseg); // Decodifica o Tempo em partes L_Tempo->Caption = IntToStr(Seg) + "," + IntToStr(Mseg) +" segundos."; // Imprime o Tempo while(cont <= NAmostras) // Recebe os Resultados { Aux = Serial->recebetexto(); Resultado = Resultado + Aux; if(Aux == '\n') // Compara para receber um valor { if (cont != 0) { Resultado = "Resul. nº " + IntToStr(cont) + ": " + Resultado; } M_Res->Lines->Add(Resultado.SubString(1, Resultado.Length()-1)); Resultado = ""; cont++; Aux = 0; } Application->ProcessMessages(); // Atualiza a Tela }
80
Programa do processador mestre //------------------------------------------------------- // Nome: Listagem dos códigos para o processador mestre // Linguagem: C para 8051 - Keil //------------------------------------------------------- #define WR_RD_RAM INT0 // Porta P3.2 – Escrita / Leitura na memória #define Clear_RAM INT1 // Porta P3.3 – Zerar a memória #define Inc_RAM T0 // Porta P3.4 – Incrementar a memória #define DONE T1 // Porta P3.5 – Bit de comunicação entre os processadores void main(void) { unsigned int i, v1, v2, v3, v4; float CoefR[NAmostras/2]; // Variável para armazenar a parte Real dos coeficientes float CoefI[NAmostras/2]; // Variável para armazenar a parte Imaginária dos coeficientes float Res_Modulo; // Variável para armazenar o Modulo do Resultado Inicializa(); for(i=0;i<NAmostras*2;i++) // Receber os Coeficientes e Grava-los na RAM { P1 = getchar(); I_RAM(); // Pulso para incrementar o endereço da RAM } // Dados Gravados CLR_RAM(); // Zerar Contador da Memoria RAM WR_RD_RAM = 1; // Habilita a Leitura na RAM for(i=0;i<NAmostras/2;i++) // Pedir os Coeficientes para o Microcontrolador Mestre { CoefR[i] = (float) (P1 - 127)/13; // Parte Real I_RAM(); // Pulso para incrementar o endereço da RAM CoefI[i] = (float) (P1 - 127)/41; // Parte Imaginária I_RAM(); // Pulso para incrementar o endereço da RAM } DONE = 1; // Setar Escravo for(i=0;i<NAmostras/2;i++) // Pedir os Coeficientes para Escravo { I_RAM(); // Pulso para incrementar o endereço da RAM I_RAM(); // Pulso para incrementar o endereço da RAM } fft(NAmostras/2, CoefR, CoefI); // Calculo da FFT for(i=0;i<NAmostras/2;i++) { Res_Modulo = sqrt(CoefR[i]*CoefR[i] + CoefI[i]*CoefI[i]); // Calculo do Modulo printf("\n %.4f", Res_Modulo); // Envio do Resultado calculado pelo Processador Mestre } DONE = 1; // Setar Escravo for(i=0;i<NAmostras/2;i++) // Envio do Resultado do Processador Escravo { while(DONE != 0); // Esperar Escravo Enviar 1º byte v1 = P1; DONE = 1; while(DONE != 0); // Esperar Escravo Enviar 2º byte v2 = P1; DONE = 1; while(DONE != 0); // Esperar Escravo Enviar 3º byte v3 = P1; DONE = 1; while(DONE != 0); // Esperar Escravo Enviar 4º byte v4 = P1; DONE = 1; Res_Modulo = (v4 << 12) | (v3 << 8) | (v2 << 4) | v1; // União dos 4 bytes inteiros em 1 float printf("\n %.4f", Res_Modulo); // Envio do Resultado enviado pelo Processador Escravo } printf("\n");
81
i = getchar(); // Fim do Processo } //------------------------------------------------------- // Função Delay // Função para realizar atraso //-------------------------------------------------------
void Delay(void) { unsigned int k; for(k=0;k<10;k++); } //------------------------------------------------------- // Função CLR_RAM // Função para Zerar a Memória //------------------------------------------------------- void CLR_RAM() { Clear_RAM = 0; Delay(); Clear_RAM = 1; Delay(); } //------------------------------------------------------- // Função I_RAM // Função para Incrementar a Memória //------------------------------------------------------- void I_RAM() { Inc_RAM = 1; Delay(); Inc_RAM = 0; Delay(); } //------------------------------------------------------- // Função Inicializa //------------------------------------------------------- void Inicializa() { WR_RD_RAM = 0; Inc_RAM = 0; Clear_RAM = 1; DONE = 0; // Habilitar interrupção serial com taxa de transmissão de // 9600 bps – modo 1 com crystal de 11.0592MHz SCON = 0x50; TMOD = 0x21; TH1 = 0xfd; TR1 = 1;
TI = 1; IE = 0x90; CLR_RAM(); // Zerar a memória putchar(12); // Limpar a Tela printf("Iniciado\n"); } //------------------------------------------------------- // Função Reversão de Bit // Processo Necessário para o Cálculo de FFT //------------------------------------------------------- unsigned int BitRev(unsigned int Valor, unsigned int NumBits) { unsigned int i, ValorRev=0; for (i=0;i<NumBits;i++) {
82
ValorRev <<= 1; // shift com 1 para esquerda ValorRev = (ValorRev ) | (Valor & 1); // Seta LSB do ValorRev com o LSB do Valor Valor >>= 1; // shift com 1 para direita } return ValorRev; } //--------------------------------------- // Funcão necessária para descobrir potência de 2 // exemplo: valor 8 precisa de 3 bits (2^3=8) //--------------------------------------- unsigned int GetNumBits(unsigned int Valor) { int i; for (i=1;i<=32;i++) { if (Valor & (1<<i)) return i; } return 0; } //----------------------------------- // Função para Cálculo da FFT // CoefR -> parte Real // CoefI -> parte Imaginária // NumAmostras -> Numero de Amostras //----------------------------------- void FFT(float *CoefR, float *CoefI, unsigned int NumAmostras) {
unsigned int i,M; unsigned int Col = 1; unsigned int NumAm2 = NumAmostras / 2; unsigned int NumNo = 0, IndexNo; unsigned int NumBits =0; double dExpValue,dTmpReal, dTmpImag, dCos, dSin, dArg;
// Formula do calculo Xl(k) = X(l-1)(k) + W^P * X(l-1)(k + N/2^l) // Index do k com n bits = Colunas NxN da Matrix com N=2^n // Col = Coluna l // No = No k // N = Número de Amostras // Distancia entre 2 Nós N/2^l = N<<l // p shift de M = (n-l) para direita, entao Reversão dos Bits NumBits = GetNumBits(NumAmostras);
for (Col=1;Col<=NumBits;Col++) { do { for (i=1;i<=NumAm2;i++) {
M = (NumNo>>(NumBits - Col)); dExpValue = (double) BitRev(M,NumBits); // ---> Feito o Cálculo Complexo dArg = TWO_PI * dExpValue / NumAmostras; dCos = cos (dArg); dSin = sin (dArg); dTmpReal = CoefR[NumNo+NumAm2] * dCos + CoefI[NumNo+NumAm2] * dSin; dTmpImag = CoefI[NumNo+NumAm2] * dCos - CoefR[NumNo+NumAm2] * dSin; CoefR[NumNo+NumAm2] = CoefR[NumNo] - dTmpReal; CoefI[NumNo+NumAm2] = CoefI[NumNo] - dTmpImag; CoefR[NumNo] = CoefR[NumNo] + dTmpReal; CoefI[NumNo] = CoefI[NumNo] + dTmpImag; // --> Fim do Cálculo Complexo NumNo++;
} NumNo += NumAm2; }while (NumNo < NumAmostras); NumAm2/=2; NumNo=0; }
// Reversão dos Bits for (NumNo=0;NumNo<NumAmostras;NumNo++) { IndexNo = BitRev(NumNo, NumBits);
83
if (IndexNo > NumNo) {
dTmpReal = CoefR[NumNo]; dTmpImag = CoefI[NumNo]; CoefR[NumNo] = CoefR[IndexNo]; CoefI[NumNo] = CoefI[IndexNo]; CoefR[IndexNo] = (float)dTmpReal; CoefI[IndexNo] = (float)dTmpImag;
} }
}
84
Programa do processador escravo //------------------------------------------------------- // Nome: Listagem dos códigos para o processador escravo // Linguagem: C para 8051 - Keil //------------------------------------------------------- #define Dados INT0 // Porta P3.2 – Controle do barramento interno da PLD #define CBUS INT1 // Porta P3.3 – Auxiliar para setar a Variável DONE #define Prox_Val T0 // Porta P3.4 – Avisa quando o próximo coeficiente está pronto #define DONE T1 // Porta P3.5 – Bit de comunicação entre os Processadores
void main(void) { unsigned int i, v1, v2 ,v3 ,v4; float Resultado; // Variavel para armazenar o Modulo float CoefR[NAmostras/2]; // Variavel para armazenar a parte Real dos coeficientes float CoefI[NAmostras/2]; // Variavel para armazenar a parte Imaginária dos coeficientes Bus(); Prox_Val = 0; Dados = 1; while (DONE != 1); // Espera Processador Mestre Sinalizar for(i=0;i<NAmostras/2;i++) // Gravar os Coeficientes { CoefR[i] = (float) P1; // Parte Real while (Prox_Val != 1); // Espera o Proximo Coeficiente Delay(); CoefI[i] = (float) P1; // Parte Imaginária while (Prox_Val != 1); // Espera o Proximo Coeficiente Delay(); } Bus(); fft(NAmostras/2, CoefR, CoefI); // Calculo da FFT Dados = 0; for(i=0;i<NAmostras/2;i++) { while(DONE != 1); // Espera Processador Mestre Sinalizar Resultado = (float) sqrt(CoefR[i]*CoefR[i] + CoefI[i]*CoefI[i]); // Modulo do Resultado v1 = Resultado && 0x000F; // 1º byte do float Resultado v2 = (Resultado && 0x00F0) >> 4; // 2º byte do float Resultado v3 = (Resultado && 0x0F00) >> 8; // 3º byte do float Resultado v4 = (Resultado && 0xF000) >> 12; // 4º byte do float Resultado P1 = v1; // Envio do 1º byte Bus(); P1 = v2; // Envio do 2º byte Bus(); P1 = v3; // Envio do 3º byte Bus(); P1 = v4; // Envio do 4º byte Bus(); } // Fim do Processo }
//------------------------------------------------------- // Função Delay // Função para realizar atraso //-------------------------------------------------------
void Delay(void) { unsigned int k; for(k=0;k<10;k++); }
85
//------------------------------------------------------- // Função Reversão de Bit // Processo Necessário para o Cálculo de FFT //------------------------------------------------------- unsigned int BitRev(unsigned int Valor, unsigned int NumBits) { unsigned int i, ValorRev=0; for (i=0;i<NumBits;i++) { ValorRev <<= 1; // shift com 1 para esquerda ValorRev = (ValorRev ) | (Valor & 1); // Seta LSB do ValorRev com o LSB do Valor Valor >>= 1; // shift com 1 para direita } return ValorRev; } //--------------------------------------- // Funcão necessária para descobrir potência de 2 // exemplo: valor 8 precisa de 3 bits (2^3=8) //--------------------------------------- unsigned int GetNumBits(unsigned int Valor) { int i; for (i=1;i<=32;i++) { if (Valor & (1<<i)) return i; } return 0; } //----------------------------------- // Função para Cálculo da FFT // CoefR -> parte Real // CoefI -> parte Imaginária // NumAmostras -> Numero de Amostras //----------------------------------- void FFT(float *CoefR, float *CoefI, unsigned int NumAmostras) {
unsigned int i,M; unsigned int Col = 1; unsigned int NumAm2 = NumAmostras / 2; unsigned int NumNo = 0, IndexNo; unsigned int NumBits =0; double dExpValue,dTmpReal, dTmpImag, dCos, dSin, dArg;
// Formula do calculo Xl(k) = X(l-1)(k) + W^P * X(l-1)(k + N/2^l) // Index do k com n bits = Colunas NxN da Matrix com N=2^n // Col = Coluna l // No = No k // N = Número de Amostras // Distancia entre 2 Nós N/2^l = N<<l // p shift de M = (n-l) para direita, entao Reversão dos Bits NumBits = GetNumBits(NumAmostras);
for (Col=1;Col<=NumBits;Col++) { do { for (i=1;i<=NumAm2;i++) {
M = (NumNo>>(NumBits - Col)); dExpValue = (double) BitRev(M,NumBits); // ---> Feito o Cálculo Complexo dArg = TWO_PI * dExpValue / NumAmostras; dCos = cos (dArg); dSin = sin (dArg); dTmpReal = CoefR[NumNo+NumAm2] * dCos + CoefI[NumNo+NumAm2] * dSin; dTmpImag = CoefI[NumNo+NumAm2] * dCos - CoefR[NumNo+NumAm2] * dSin; CoefR[NumNo+NumAm2] = CoefR[NumNo] - dTmpReal; CoefI[NumNo+NumAm2] = CoefI[NumNo] - dTmpImag; CoefR[NumNo] = CoefR[NumNo] + dTmpReal; CoefI[NumNo] = CoefI[NumNo] + dTmpImag; // --> Fim do Cálculo Complexo
86
NumNo++; } NumNo += NumAm2; }while (NumNo < NumAmostras); NumAm2/=2; NumNo=0; }
// Reversão dos Bits for (NumNo=0;NumNo<NumAmostras;NumNo++) { IndexNo = BitRev(NumNo, NumBits); if (IndexNo > NumNo) {
dTmpReal = CoefR[NumNo]; dTmpImag = CoefI[NumNo]; CoefR[NumNo] = CoefR[IndexNo]; CoefI[NumNo] = CoefI[IndexNo]; CoefR[IndexNo] = (float)dTmpReal; CoefI[IndexNo] = (float)dTmpImag;
} }
}
87
Listagem dos módulos AHDL //------------------------------------------------------- // Nome: Listagem dos códigos para o PLD // Linguagem: AHDL - Quartus //-------------------------------------------------------
//------------------------------------------------------- // Entidade Counter // Seta o Endereço na Memória RAM //------------------------------------------------------- entity counter is generic(n: natural :=11); port( clear: in std_logic; count: in std_logic; Q: out std_logic_vector(n-1 downto 0) ); end counter; architecture behv of counter is signal Pre_Q: std_logic_vector(n-1 downto 0); begin process(count, clear) begin if (clear = '0') then Pre_Q <= Pre_Q - Pre_Q; elsif (count = '1' and count'event) then Pre_Q <= Pre_Q + 1; end if; end process; Q <= Pre_Q; end behv; //------------------------------------------------------- // Entidade Tristate8 // Bloco Tristate de 8 Bits //------------------------------------------------------- entity tristate8 is port( d_in: in std_logic_vector(7 downto 0); en: in std_logic; d_out: out std_logic_vector(7 downto 0) ); end tristate8; architecture behv of tristate8 is begin process(d_in, en) begin if en='1' then d_out <= d_in; else -- array can be created simply by using vector d_out <= "ZZZZZZZZ"; end if; end process; end behv;
88
//------------------------------------------------------- // Entidade Tristate12 // Bloco Tristate de 12 Bits //------------------------------------------------------- entity tristate12 is port( d_in: in std_logic_vector(10 downto 0); en: in std_logic; d_out: out std_logic_vector(10 downto 0) ); end tristate12; architecture behv of tristate12 is begin process(d_in, en) begin if en='1' then d_out <= d_in; else -- array can be created simply by using vector d_out <= "ZZZZZZZZZZZ"; end if; end process; end behv; //------------------------------------------------------- // Entidade Cont_RAM // Controla o Acesso a RAM //------------------------------------------------------- entity Cont_RAM is generic( Tam_Mem: integer:=11 ); port( EndIN: in std_logic_vector(Tam_Mem-1 downto 0); WRIN: in std_logic; EN: in std_logic; WROUT: out std_logic; EndOUT: out std_logic_vector(Tam_Mem-1 downto 0); Dado1_in: in std_logic_vector(7 downto 0); Dado2_in: in std_logic_vector(7 downto 0); Dado1_out: out std_logic_vector(7 downto 0); Dado2_out: out std_logic_vector(7 downto 0) ); end Cont_RAM; architecture behv of Cont_RAM is signal AUX1: std_logic_vector(7 downto 0); signal AUX2: std_logic_vector(7 downto 0); begin EndOUT <= EndIN; process(WRIN, Dado1_in, Dado2_in, EN) begin if (EN = '1') then if (WRIN = '1') then
89
WROUT <= '1'; Dado1_out <= Dado2_in; else WROUT <= '0'; Dado2_out <= Dado1_in; end if; else Dado1_out <= "ZZZZZZZZ"; Dado2_out <= "ZZZZZZZZ"; end if; end process; end behv; //------------------------------------------------------- // Entidade ClearRAM // Seta para a posição zero da RAM //------------------------------------------------------- entity ClearRAM is port( bit_in: in std_logic; bit_out: out std_logic ); end ClearRAM; architecture behv of ClearRAM is begin process(bit_in) begin if (bit_in'event) then bit_out <= '0'; bit_out <= '1'; end if; end process; end behv;
90