UNIVERSIDADE POSITIVO NÚCLEO DE CIÊNCIAS EXATAS E

UNIVERSIDADE POSITIVO
NÚCLEO DE CIÊNCIAS EXATAS E TECNOLÓGICAS
ENGENHARIA ELÉTRICA
Cleverson Leandro Ávila
Rodrigo Duarte
SOLUCIONANDO O PROBLEMA DO CAIXEIRO VIAJANTE
ATRAVÉS DA COMPUTAÇÃO RECONFIGURÁVEL
Curitiba, 2008
Cleverson Leandro Ávila
Rodrigo Duarte
SOLUCIONANDO O PROBLEMA DO CAIXEIRO VIAJANTE
ATRAVÉS DE COMPUTAÇÃO RECONFIGURÁVEL
Monografia apresentada ao Curso de
Engenharia Elétrica da Universidade Positivo,
para obtenção de avaliação da disciplina de Trabalho de Conclusão de Curso (TCC)
Orientador: Profº André Macário Barros.
Curitiba, 2008
Dedicamos esta monografia a todos os professores que contribuíram em nossa formação escolar desde o nosso ensino
básico até a graduação de Engenharia Elétrica.
iii
AGRADECIMENTOS
Primeiramente, agradeço a Deus por ter me dado a oportunidade de estar aqui. Aos meus pais, Osvaldo de Jesus Ávila e
Elizabeth de Almeida Ávila, e à minha namorada Caroline
Rodrigues da Silva, agradeço todo o amor, carinho, compreensão e respeito.
Cleverson Leandro Ávila
Agradeço aos meus pais, Elédio Duarte e Rosana Aparecida
Balena Duarte, a toda a minha família e amigos por todo o
amor, carinho e compreensão.
Rodrigo Duarte
Agradecemos ao Profº André Macário Barros pelo grande apoio, dedicação e companherismo.
iv
“Procurem deixar este mundo um pouco melhor do que o encontraram e, quando chegar a hora de morrer, poderão morrer felizes sentindo que pelo menos não desperdiçaram o
tempo e que procuraram fazer o melhor possível.”
Baden Powell
v
RESUMO
O Problema do Caixeiro Viajante, conhecido como TSP (Travelling Salesman
Problem), é a obtenção da menor rota entre “N” cidades finalizada no ponto de origem. O
TSP por ser um problema combinatorial de difícil resolução, tornou-se muito popular no meio
acadêmico, devido a sua ampla aplicabilidade em várias áreas.Várias formas de implementálo computacionalmente foram criadas, por exemplo, utilizando algoritmos genéticos e redes
neurais. Um computador convencional consegue calcular em um tempo satisfatório apenas
um pequeno número de cidades. Já um sistema baseado em computação reconfigurável (CR)
onde o paralelismo pode ser explorado, pode resolver problemas combinatoriais com uma
maior velocidade, quando se trata de um número maior de cidades. Por isso, neste trabalho foi
utilizada a estrutura F+V (Fixo + Variável) e utilizando um método determinístico baseado no
Algoritmo Johnson-Trotter, na qual um computador convencional é a interface entre o usuário
e o sistema CR. O usuário entrará com as coordenadas de “N” instâncias em um programa
desenvolvido em Borland C++ Builder e este, através de comunicação paralela, enviará informações para uma placa que contém o FPGA (Field Programmable Gate Arrays), componente principal da parte V, que fará todos os cálculos necessários e transmitirá a resposta, a
menor rota, novamente para o computador.
Palavras-chave: TSP, algoritmo Jonhson-Trotter, FPGA, Computação Reconfigurável.
vi
ABSTRACT
The TSP (Travelling Salesman Problem), is the attainment of the smaller route
among “N” cities and that finishes at the origin point. The TSP, because it is a combinatorial
problem difficult to solve, has became very popular into the academic environment, due to its
great applicability in several areas. Several ways to implement it through computers were
developed, for example, using genetic algorithms and neural networks. An ordinary computer
can calculate within a satisfactory time only a small number of cities. But a reconfigurable
computing system (RC) where the parallelism can be explored, is able to solve combinatorial
problems in less time, when we talk about a larger number of cities. Therefore, in this study it
was used the structure F+V (Fixed + Variable), and using a determining method based on
Algorithm Johnson-Trotter, in which an ordinary computer will be the interface between the
user and system (RC). The user will enter the coordinates of “N” cities in a software program
developed in Borland C++ Builder, and this one, through parallel communication, will send
information to the FPGA (Field Programmable Gate Arrays), a main component of the V
part, that will do all the necessary calculations and will transmit the answer, the smaller
route, back to the computer.
Key-words: TSP, Algorithm Johnson-Trotter, FPGA, Reconfigurable Computing.
vii
LISTA DE FIGURAS
Figura 1 – Diagrama em Blocos Simplificado. ....................................................................... 2
Figura 2 – Diagrama em blocos do sistema “F+V” com a parte variável expandida................ 5
Figura 3 – Exemplo de um arquivo *.tsp................................................................................ 6
Figura 4 – Layout do AC ....................................................................................................... 9
Figura 5 – Esquemático FPGA............................................................................................. 16
Figura 6 – Programa de Interface com o Usuário.................................................................. 18
Figura 7 – Placa de comunicação paralela. ........................................................................... 20
Figura 8 – Gráfico do Tempo de processamento entre o AC e F+V...................................... 23
LISTA DE TABELA
Tabela 1 – Exemplo de Matriz de Distâncias para 4 cidades................................................... 7
Tabela 2 – Cronograma........................................................................................................ 11
Tabela 3 – Custos do projeto................................................................................................ 12
Tabela 4 – Tempo de processamento entre o AC e do F+V .................................................. 22
viii
LISTA DE ABREVIATURAS/SIGLAS
AC – Algoritmo Canônico;
AG – Algoritmos Genéticos;
ASIC – Application Specific Integrated Circuit;
CP – Computação Paralela;
CR – Computação Reconfigurável;
F+V – Fixo + Variável;
FLS – Fast Local Search;
FPGA – Field-Programmable Logic Arrays;
JT – Algoritmo de Johnson-Trotter;
LE – Logical elements;
MD – Matriz de distâncias;
PC – Personal Computer;
PSO – Paticle Swarm Optimization;
RNA – Redes Neurais Artificiais;
TSP - Travelling Salesman Problem
LCD - Liquid Crystal Display
ix
SUMÁRIO
1 INTRODUÇÃO ..........................................................................................................................................1
1.1
PROBLEMA ......................................................................................................................................1
1.2
JUSTIFICATIVA .................................................................................................................................2
1.3
OBJETIVOS ......................................................................................................................................2
2
REVISÃO DA LITERATURA.............................................................................................................4
3
ESPECIFICAÇÕES TÉCNICAS PRELIMINARES ..........................................................................5
3.1
VISÃO GERAL DO PROJETO ...............................................................................................................5
3.2
DESCRIÇÃO FUNCIONAL DOS BLOCOS ...............................................................................................6
3.2.1
Bloco 1: Programa em Borland no PC.........................................................................................6
3.2.2
Bloco 2: Interface paralela ..........................................................................................................7
3.2.3
Bloco 3: FPGA e sub-blocos.......................................................................................................7
3.3
DIMENSIONAMENTO E MEMORIAL DE CÁLCULO .................................................................................8
3.4
PROGRAMAÇÃO ...............................................................................................................................9
3.4.1
Descrição geral ...........................................................................................................................9
3.4.2
Planejamento............................................................................................................................10
4
METODOLOGIA...............................................................................................................................13
4.1.1
Fase 1.......................................................................................................................................13
4.1.2
Fase 2.......................................................................................................................................13
4.1.3
Fase 3.......................................................................................................................................14
4.2
CONTRIBUIÇÃO ..............................................................................................................................14
5
IMPLEMENTAÇÃO..........................................................................................................................15
5.1
DESCRIÇÃO DA MONTAGEM ..................................................................................................15
5.2
TESTES, MEDIÇÕES E CONFIGURAÇÕES ...............................................................................16
5.3
CÓDIGO S FONTE S ......................................................................................................................17
5.3.1
Código Fonte do Programa 1 ....................................................................................................17
5.3.2
Código Fonte do Programa 2 ....................................................................................................18
5.3.3
Código Fonte BCD_to_7seg .....................................................................................................19
5.4
PLACAS DE CIRCUITO IMPRESSO (PCI)..................................................................................20
6
RESULTADOS...................................................................................................................................22
6.1
ANÁLISE DE RESULTADOS......................................................................................................23
7
CONCLUSÕES ..................................................................................................................................24
7.1
TRABALHOS FUTUROS ............................................................................................................24
REFERÊNCIAS ............................................................................................................................................26
x
1
1 INTRODUÇÃO
Os computadores convencionais, devido à sua grande flexibilidade, podem ser utilizados em diversas tarefas, mas para aplicações específicas, estes dispositivos podem não
alcançar um desempenho desejado. Para as aplicações que necessitam de alta capacidade de
processamento, os ASICs (Application Specific Itegrated Circuit) são chips dedicados à estas
tarefas, desenvolvidos para ter alto desempenho em aplicações que exigem grande processamento, mas esta tecnologia é uma opção mais cara e inflexível, comparada aos microcomputadores.
A CR (Computação Reconfigurável) (SKLIAROVA e FERRARI, 2003) surgiu
para integrar o alto desempenho dos ASICs e a flexibilidade dos computadores de uso geral.
A CR baseia-se em uma arquitetura “F+V” (ESTRIN, 1960) que, hoje em dia, é implementada utilizando-se placas contendo um ou mais FPGAs (Field-Programmable Logic Arrays)
para representar a parte V (Variável) e um computador de uso geral para representar a parte F
(Fixa). Neste sistema, o processador de uso geral executa as partes que não são facilmente
implementadas em hardware, e o FPGA executa as partes que exigem maior processamento e
que se beneficiam de alguma forma com a implementação em hardware. Pelas suas características, a CR é também aplicada na resolução de problemas matemáticos combinatoriais que,
a depender do seu grau de magnitude, consomem muito tempo quando processados em computadores convencionais.
1.1
PROBLEMA
Como reduzir o tempo de processamento de problemas combinatoriais utilizando
a CR como ferramenta de apoio, quando comparado ao tempo de processamento de um computador de uso geral, executando o mesmo problema.
2
1.2
JUSTIFICATIVA
A área da CP (Computação Paralela), antes do surgimento da Computação Reconfigurável, era uma área de pesquisa, a qual requeria uma sala com vários computadores para
executar um dado problema. Com o surgimento da CR (Computação Reconfigurável), foi
possível paralelizar tais algoritmos da CP, utilizando apenas uma placa com FPGA e um
computador convencional. Isso gera uma necessidade de aprofundamento em pesquisas.
1.3
OBJETIVOS
O objetivo principal deste estudo foi desenvolver e implementar uma arquitetura
do tipo "F+V" para resolver o TSP (Travelling Salesman Problem) (DANTZIG E FULKERSON, 1954), de acordo com a figura 1.
Figura 1 – Diagrama em Blocos Simplificado.
Fonte própria
Os objetivos específicos foram:
a)
Desenvolver um software que resolva o problema proposto inteiramente no
PC, através do algoritmo JT (Johnson-Trotter) (SEDGEWICK, 1977) para
servir de AC (algoritmo canônico);
b) Desenvolver o software da parte “F” do sistema “F+V”;
3
c)
Desenvolver o programa que foi executado na parte “V” da arquitetura
“F+V”, baseada em um FPGA com no mínimo 33000 LE (Logical Elements),
da família EP2 da Altera;
d) Comparar os resultados do AC (Algoritmo Canônico), que executa o JT apenas no computador convencional, e do “F+V” e verificar o speedup (razão entre tempo obtido na arquitetura proposta, sobre o tempo de execução do AC,
num computador convencional).
4
2
REVISÃO DA LITERATURA
Em Lopes e Coelho (2005) foi proposto um novo método para a resolução do
TSP, utilizando PSO (Particle Swarm Optimization) e FLS (Fast Local Search). O método
mostrou ter bons resultados computacionais, comparado ao PSO puro (sem FLS).
Em Skliarova e Ferrari (2002) foi proposto a resolução do TSP utilizando AG
(Algoritmos Genéticos) (GOLDBERG, 1989). Neste método utilizou-se CR, sendo que, por
tomar muito tempo de processamento, parte do AG (parte dedicada à operação de crossover)
foi implementada em um FPGA, com o intuito de aumentar o desempenho do sistema.
Os dois trabalhos citados anteriormente evidenciam a necessidade de técnicas alternativas para a resolução do TSP, quando este tem seu número de cidades aumentado.
Em Ankush Varma e Jayadeva (2002) foi apresentado um novo sistema de rede
neural para solucionar o TSP. O modelo proposto é baseado em FPGAs. Para demonstrar a
eficiência deste método, o projeto foi comparado ao modelo computacional Hopfield Neural
Network e mostrou-se superior, no quesito velocidade de processamento. A utilização das
RNA (Redes Neurais Artificiais) vem novamente a reforçar a necessidade de métodos alternativos para a resolução de instâncias de valor alto para o TSP. Uma das linhas de ação futuras a
serem obtidas com os resultados desta pesquisa-piloto é empregar tais métodos alternativos. O
emprego do método JT, em contrapartida, tem o intuito de simplificar o processo nesta primeira fase (neste ano) da pesquisa. Uma vez com o sistema desenvolvido de forma flexível,
será possível a inserção de funções na linguagem C que implementem os métodos aqui mencionados.
5
3
3.1
ESPECIFICAÇÕES TÉCNICAS PRELIMINARES
VISÃO GERAL DO PROJETO
O projeto está dividido em duas partes, a criação do AC (Algoritmo Canônico) e a
implementação do sistema “F+V” (“Fixo + Variável). O AC é um programa criado em Borland C++ Builder 5, que será executado exclusivamente num PC (Personal Computer). Este
programa abre um arquivo contendo informações das instâncias, gera uma MD (Matriz de
Distâncias), executa o JT (Algoritmo Johnson-Trotter) e disponibiliza ao usuário a menor rota.
No sistema “F+V”, um programa criado em Borland abre um arquivo, coleta as
informações das instâncias e gera a MD, a qual é transferida por comunicação paralela à placa
DE2 da Altera (placa externa que contém o FPGA) que, por sua vez, executa o algoritmo JT e
transfere para o PC a menor rota para que seja disponibilizada ao usuário. O diagrama em
blocos que ilustra este sistema é mostrado na figura 2.
Figura 2 – Diagrama em blocos do sistema “F+V” com a parte variável expandida.
Fonte própria.
6
3.2
DESCRIÇÃO FUNCIONAL DOS BLOCOS
Esta seção visa explicar o diagrama em blocos proposto na figura 2.
3.2.1 Bloco 1: Programa em Borland no PC
Interface com o usuário, apresenta a seleção de arquivos, o status do programa e
disponibiliza os resultados finais. O programa abre um arquivo escolhido pelo usuário (arquivo compatível com a tsplib – ELIB, 2008) e coleta as principais informações deste arquivo: a
quantidade de instâncias e posição, em coordenadas cartesianas, de cada cidade. A figura 3
mostra um exemplo de um arquivo que contém as informações necessárias para executar corretamente o programa. O campo “NAME” indica o nome do arquivo; o campo “DIMENSION:” informa a quantidade de instâncias; abaixo do campo “NODE_COORD_SECTION”
estão disponíveis as informações relativas às cidades, por exemplo: cidade 1, x=5, y=6; cidade
2, x=15, y=2. O próximo passo é a criação da MD (Matriz de Distâncias), exemplificada na
tabela 1 (tabela gerada a partir do programa exemplo da figura 3).
Figura 3 – Exemplo de um arquivo *.tsp .
Fonte própria.
7
Tabela 1 – Exemplo de Matriz de Distâncias para 4 cidades.
n\n
1
2
3
4
1
0
11
5
5
2
11
0
12
8
3
5
12
0
4
4
5
8
4
0
Fonte própria.
Por exemplo, para obter o valor de distância entre as cidades 2 e 3 (valor igual a
12, conforme a tabela 1), utiliza-se a fórmula da distância euclideana (1):
d = (int) ( x 2 − x3 ) 2 + ( y 2 − y 3 ) 2
(1)
3.2.2 Bloco 2: Interface paralela
Comunicação paralela entre PC e a placa DE2. Transfere a MD, do PC para o
FPGA e a melhor rota, do FPGA para o PC.
3.2.3 Bloco 3: FPGA e sub-blocos
As ferramentas Quartus II, SOPC Builder (Altera,2008) gera componentes em
VHDL, como o processador, memória, barramentos de entrada e saída entre outros. O NIOS
II IDE (Altera, 2008) permite escrever um programa em “C” para rodar no processador gerado pelo SOPC Builder. O sub-bloco do processador virtual NIOS II armazenará o algoritmo
8
JT, responsável pela geração das combinações de rotas, e também o algoritmo que encontra a
melhor rota.
3.3
DIMENSIONAMENTO E MEMORIAL DE CÁLCULO
Os programas serão desenvolvidos em Borland C++ Builder 5 por causa da sua
facilidade de operação; pela disponibilidade gratuita da ferramenta na universidade; e por
suportar AnsiC, o que facilitará na passagem do programa do PC para o do NIOS II.
A placa DE2 foi escolhida por possuir toda a estrutura necessária para testes
(LEDs, switchs, LCD (Liquid Crystal Display), porta para comunicação serial, memórias SRAM, SDRAM e flash); por dar suporte ao processador virtual NIOS II e por conter o FPGA
Cyclone II EP2C35, o qual possui 33216 LEs e 35 multiplicadores embarcados1, o que permite descrever hardwares mais complexos.
Será utilizada a interface paralela por disponibilizar as informações com maior velocidade. A porta USB não foi escolhida porque, para implementar no FPGA a comunicação
USB, teria que ser feita compra do módulo pronto, agregando assim, custo ao projeto. O módulo paralelo para o FPGA é disponível gratuitamente.
O TSP foi escolhido por ser o problema com várias possíveis aplicações na engenharia elétrica, como por exemplo, na escolha de rotas na fabricação de placas de circuito
impresso e por ser um problema simples de ser implementado em C comparado a outros problemas combinatoriais, como o Problema da Satisfação.
1
Dados retirados do data sheet da família de dispositivos Cyclone II
9
3.4
PROGRAMAÇÃO
3.4.1 Descrição geral
Abaixo seguem os principais passos que o AC deve desempenhar:
Início
Ler arquivo de instâncias até a string “DIMENSION:”;
Capturar número de cidades (n);
Ler arquivo de instâncias até a string “NODE_COORD_SECTION”;
Capturar identificação da cidade e suas coordenadas x y até a string “EOF”;
Loop para preenchimento da MD (tamanho nXn)
Calcula distância entre dois pontos e coloca resultado na MD;
Executar algoritmo JT
Gerar uma combinação (rota);
Comparar a distância total da rota atual com a menor distância obtida;
Se a rota atual for menor, guardar valor de distância e a rota atual;
Expor na tela a melhor seqüência de cidades (rota) com distância total;
Fim;
No sistema “F+V”, depois que o PC gera a MD, ele a envia pela porta serial para
o FPGA, que executa o algoritmo JT e envia para o PC a melhor rota para que seja disponibilizada para o usuário. A figura 4 apresenta um layout da tela de interface para o usuário.
Figura 4 – Layout do AC
10
Fonte prórpia.
Os ambientes de programação utilizados são:
•
Borland C++ Builder 5;
•
Quartus II 8.0;
•
SOPC Builder;
•
NIOS II IDE 8.0;
As linguagens de programação utilizadas são: C e VHDL.
3.4.2 Planejamento
O cronograma seguido para execução do projeto esta apresentado na tabela 2. As tarefas foram executadas por todos os integrantes da equipe.
11
Tabela 2 – Cronograma.
Cronograma
Data
Descrição de Tarefas
20 a 03.03.2008
Elaboração da proposta de TCC
07 a 24.03.2008
Correção e entrega da proposta TCC versão definitiva
25 a 30.03.2008
Estudo de artigos para formular a revisão literaria
30 a 05.04.2008
Estudo da arquitetura "F+V", Algoritmo JT, FPGAs.
06 a 15.04.2008
Elaboração do software AC em Borland.
16 a 22.04.2008
Elaboração dos capítulos 1 e 2 do TCC.
22.04.2008
Entrega dos capítulos 1 e 2 do TCC.
22 a 09.05.2008
Elaboração do TCC em formato de PPT.
09.05.2008
Apresentação do PPT.
10 a 14.05.2008
Conclusão do Software AC.
15 a 26.05.2008
Elaboração do capítulo 3 do TCC.
26.05.2008
Entrega dos capítulos 1, 2 e 3 do TCC.
27 a 02.06.2008
Elaboração do TCC em formato de PPT.
02.06.2008
Apresentação do PPT.
03 a 22.06.2008
Ensaios práticos do projeto.
23.06.2008
Apresentação do software AC.
23 a 31.07.2008
Testes da estrutura "F+V".
01 a 18.08.2008
19 a 31.08.2008
Implementação da arquitetura "F+V" proposta.
Testes de comparação de tempo de processamento entre a AC e
o "F+V"
01 a 29.09.2008
Elaboração do capítulo 4.
29.09.2008
Entrega dos capítulos 1, 2, 3 e 4 do TCC.
30 a 06.10.2008
Elaboração do Artigo.
06.10.2008
Entrega do Artigo
07 a 27.10.2008
Conclusão da Monografia
28 a 05.11.2008
Preparação do Painel
06 a 10.11.2008
Elaboração da Apresentação final
10.11.2008
Apresentação final
01.12.2008
Entrega da Monografia e Artigo versões finais
Fonte própria.
12
Os custos para a execução do projeto estão apresentados na tabela 3.
Tabela 3 – Custos do projeto.
Quantidade
1
1
45
63
90
3
120
3
150
3
120
30
3
Fonte própria.
Planejamento Financeiro
Descrição
Valor unitário
Valor total
Placa Altera DE2
R$
1.150,25 R$ 1.150,25
Placa de Comunicação Paralela
R$
100,00
R$
100,00
Impressões da 1ª fase
R$
0,10
R$
4,50
Impressões da 2ª fase
R$
0,10
R$
6,30
Impressões da 3ª fase
R$
0,10
R$
9,00
Encadernação
R$
2,50
R$
7,50
Impressões da 4ª fase
R$
0,10
R$
12,00
Encadernação
R$
2,50
R$
7,50
Impressões da 5ª fase
R$
0,10
R$
15,00
Encadernação
R$
2,50
R$
7,50
Impressões da 6ª fase
R$
0,10
R$
12,00
Impressões coloridas
R$
1,20
R$
36,00
Encadernação c/ capa dura
R$
15,00
R$
45,00
TOTAL
R$ 1.412,55
13
4
METODOLOGIA
Este projeto, por ser uma pesquisa experimental, consiste principalmente na coleta
e no confrontamento de dados, tais como valores de tempo de processamento gerados pelo
algoritmo canônico e pelo sistema “F+V” desenvolvido.
A metodologia aplicada pode ser dividida em fases, para a melhor administração
do trabalho.
4.1.1 Fase 1
Esta fase consiste no desenvolvimento do AC em Borland C++ Builder 5. Este
programa deve possibilitar que o usuário selecione o arquivo que é utilizado. O programa deve abrir este arquivo; ler a quantidade de instâncias e a posição de cada cidade; guardar estas
informações; gerar a matriz de distâncias; executar o algoritmo JT; encontrar a melhor rota
dentre as combinações geradas pelo JT e; disponibilizar para o usuário a seqüência de cidades
que possui a melhor rota.
4.1.2 Fase 2
A fase 2 consiste em implementar o algoritmo desenvolvido na fase 1, exclusivamente dentro da placa DE2, através das ferramentas SOPC Builder e NIOS II IDE.
14
4.1.3 Fase 3
Nesta etapa, o principal foco é o desenvolvimento do sistema “F+V” proposto, ou
seja, implementar o programa que será executado no PC (interface com o usuário; coleta de
dados e geração da matriz de distâncias); a comunicação paralela entre PC e placa DE2; a
implementação do que será executado no FPGA (o processador virtual NIOS II e, dentro deste, o algoritmo JT); e, finalmente, executar o algoritmo canônico e o sistema “F+V”, com a
finalidade de comparar o tempo de processamento dos dois sistemas.
4.2
CONTRIBUIÇÃO
Esta pesquisa contribuirá para o grupo de pesquisas da Universidade Positivo,
pois foi criada uma estrutura que permitirá a implementação de algoritmos com heurísticas no
local do algoritmo JT.
A pesquisa visa também conseguir uma arquitetura do tipo “F+V” que será útil
em diversas aplicações que necessitam de uma grande capacidade de processamento tal como,
por exemplo, no reconhecimento de impressões digitais, processamento de imagens e processamento de áudio.
A contribuição para a comunidade científica dos resultados desta pesquisa é a de
oferecer mais uma arquitetura do tipo “F+V”, simplificada, que sirva para outros problemas
combinatoriais, além de oferecer uma estrutura flexível e simplificada na qual poderá ser utilizada para configurar outros códigos para diferentes aplicações, comportando tanto métodos
determinísticos quanto heurísticos.
15
5
5.1
IMPLEMENTAÇÃO
DESCRIÇÃO DA MONTAGEM
O projeto foi desenvolvido em pequenos passos os quais, em cada ponto importante do projeto, foram desenvolvidos programas testes. O primeiro passo foi desenvolver o
Algoritmo Canônico, o qual possibilitava a leitura de um arquivo texto, gerava todas as seqüências de rotas e, dentre estas, indicava na tela a melhor.
Em seguida, a atenção foi direcionada à placa DE2 e o FPGA. Foram desenvolvidos alguns programas testes que possibilitaram o aprendizado desta ferramenta e dos softwares NIOS II IDE e SOPC Builder. Nesta estapa, um grande tempo (3 meses) do projeto foi
perdido em busca de tutoriais e materiais relacionados à placa didática e aos softwares NIOS
II IDE e SOPC Builder, já que os materiais disponibilizados pela Terasic (empresa desenvolvedora da placa DE2) que foram entregues junto à placa DE2 estavam desatualisados em relação à versão do Quartus II utilizada (versão 8). Na tentativa de encontrar tutoriais mais recentes, foram feitas pesquisas na internet e no site da Altera, mas são poucos os materiais disponíveis sobre estes softwares. Os primeiros sistemas desenvolvidos utilizando estas ferramentas
foram simples programas para acender LEDs através de chaves. Mas este simples programa
foi a base para desenvolver todo o software que é executado internamente no processador
Nios desenvolvido para o FPGA. Durante este processo, foram encontrados alguns problemas
relacionados à porta de comunicação serial, problemas gerados, principalente, pela dificuldade de encontrar materiais de referência para esta ferramenta, e também pelo material (tutoriais) disponibilizado estar desatualizado. Assim, foi optado pela utilização da comunicação
pela porta paralela.
Após os testes realizados na placa, foi feito a conexão entre o PC e a placa DE2.
Para isto, algumas adaptações foram nescessárias, já que o FPGA utilizado possui uma tensão
de trabalho de 3.3V, enquanto a porta paralela do PC, trabalha em 5V. para esta adaptação,
fez-se necessário a utilização de um buffer (74LS245N) que separasse as duas portas.
Além da placa para adaptação dos níveis de tensão e dos componentes providos
pela placa DE2, não foi utilizado nenhum outro dispositivo auxiliar.
16
O hardware desenvolvido para o FPGA (figura 5), conta com processador Nios,
uma memória on-chip de 40Kbytes e 8 entradas/saídas paralelas: rst; clk; dados_in; valor_out;
i1; j1; sin_d_p; sin_p_p. Também foi implementado um conversor BCD para display de 7
segmentos para a visualização de valor_out, i1 e j1. Os pinos de dados_in e de valor_out são
utilizados para a troca de dados com o PC, sendo que valor_out também está ligado a um display de 7 segmentos para a melhor visualização dos valores trafegados. Os pinos i1 e j1 também são ligados a displays para facilitar o encontro de erros no software do Nios. O sinal
sin_d_p é um sinal de sincronismo gerado pelo PC para o FPGA e o sinal sin_p_p é a resposta
do FPGA para o PC. A descrição dos softwares desenvolvidos pode ser encontrada no capítulo 4.3.
Figura 5 – Esquemático FPGA
Fonte própria.
5.2
TESTES, MEDIÇÕES E CONFIGURAÇÕES
O hardware, como comentado anteriormente, é composto pela placa DE2 e pelo
circuito de acoplamento (circuito para adaptação dos sinais). Após a escolha do buffer a ser
utilizado na comunicação paralela entre o PC e a placa DE2, foram realizados teste para veri-
17
ficar se o mesmo transmitiria em altas freqüências sem perdas de bits. Foram verificados através do osciloscópio em uma freqüência de 1 KHz.
Para o software, a cada novo passo, era realizado um pequeno programa para testes de novas funcionalidades. Na implementação da comunicação paralela, foi criado um protocolo de sinalização no qual, um elemento só recebe o dado após ser sinalizado de que há um
dado a ser recebido, criando um sistema assíncrono.
O projeto não possui uma limitação em relação ä quantidade de cidades, mas um
número superior a 20 cidades pode passar do tempo de processamento limite (o processamento pode demorar demais), mas pode facilmente ter sua funcionalidade modificada para aumentar este número e otimizar o tempo de processamento.
5.3
CÓDIGOS FONTES
No projeto, foram desenvolvidos 2 programas em C (Programa 1 e Programa 2) e
um em VHDL (BCD_to_7seg).
5.3.1 Código Fonte do Programa 1
O Programa 1 é o programa executado no PC, cuja característica principal é a interface com o usuário e pode ser visualizada através da figura 6. Todo o código fonte pode ser
visto no Apêndice 1. Seu funcionamento parte da abertura de um documento, escolhido pelo
usuário, que contém as informações sobre as cidades. Clicando-se no ícone “Abrir”, é executada a função “ler_dados” que irá ler os dados do documento selecionado, mostrar seu conteúdo na tela e montar uma tabela contendo as informações das cidades. Em seguida, clicando
no ícone iniciar (“Play”), são executadas seqüêncialmente as seguintes funções: gera_matriz;
envia_dados; recebe_dados; w_seq; gráfico.
18
A função gera_matriz cria a matriz de distâncias partindo do cálculo da distância
entre dois pontos e utilizando a parte inteira da resposta. A função envia_dados envia a matriz
de distâncias para a placa DE2 pela porta paralela. A cada envio de dados, pela porta de controle envia-se um nível lógico alto (1) para o sincronismo com o FPGA e, em seguida, é gerado um delay de 1ms para dar tempo para a placa didática receber, acomodar os dados e ficar
pronto para receber outro dado. Terminando o envio, é executada a função recebe_dados.
Quando o FPGA for enviar dados para o PC, ele envia um sinal para o PC saber que pode
“pedir” os dados. Com todos os dados recebidos, é executada a função w_seq que escreve a
seqüência de cidades na tela e, através da função gráfico, o gráfico é desenhado na tela.
Figura 6 – Programa de Interface com o Usuário.
Fonte própria
5.3.2 Código Fonte do Programa 2
Este programa é executado no Nios, dentro do FPGA. Seu código fonte pode ser
visualizado no Apêndice 2. Ele tem a função de receber dados vindos de PC, executar o algoritmo JT e enviar para o PC a seqüência de cidades que forma a melhor rota.
19
O programa permanece em estado de reset (enviado pelo PC) até ser informado
que há dados para serem recebidos (sinal rst igual a zero). Quando o sinal “sin_d_p” igual a
“1”, significa que há um novo dado a ser recebido. O programa pega o dado e o acomoda na
memória, primeiramente recebendo o número de cidades, depois montando uma matriz de
distâncias. Depois é executado o Algoritmo JT e, quando finalizado, envia a seqüência de
cidades para o PC.
5.3.3 Código Fonte BCD_to_7seg
Este código em VHDL é um simples programa para receber um valor em hexadecimal e converter num valor que pode ser visualizado num display de 7 segmentos. O código
pode ser visualizado abaixo:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
library ieee;
use ieee.std_logic_1164.all;
entity BCD_to_7seg is
Port(
bcd : in bit_vector(0 to 3);
on_off : in bit;
seg : out bit_vector (0 to 6));
end;
Architecture conversor of BCD_to_7seg is
Begin
abc : process(bcd,on_off)
begin
if on_off='0' then
seg<="1111111";
else
case bcd is
when "0001"=>seg<="1001111";
when "0010"=>seg<="0010010";
when "0011"=>seg<="0000110";
when "0100"=>seg<="1001100";
when "0101"=>seg<="0100100";
when "0110"=>seg<="0100000";
when "0111"=>seg<="0001111";
when "1000"=>seg<="0000000";
when "1001"=>seg<="0001100";
when "1010"=>seg<="0001000";
when "1011"=>seg<="1100000";
when "1100"=>seg<="0110001";
when "1101"=>seg<="1000010";
when "1110"=>seg<="0110000";
when "1111"=>seg<="0111000";
20
33
when others=>seg<="0000001";
34
end case;
35
end if;
36
end process;
37 end architecture;
5.4
PLACAS DE CIRCUITO IMPRESSO (PCI)
Como se trata de um projeto de pesquisa, este foi desenvolvido em placas didáticas e em protoboard, visando à aquisição de resultados. O único hardware desenvolvido foi
uma interface, apresentada na figura 7, interligando o PC a DE2, devido às diferenças de níveis de tensão e para a proteção da placa didática e da porta paralela do PC.
Figura 7 – Placa de comunicação paralela.
Fonte própria.
Para os sinais que seguem no sentido porta paralela-FPGA, foi utilizado o circuito
buffer (74LS245N), com todas as suas entradas em PULL DOWN, alimentado com 4.3V. Esta
tensão é gerada por um regulador de tensão (CI 7805), em série com um diodo N4004. Quando há um nível lógico alto na porta paralela, na saída do CI, devido a uma queda de tensão
21
interna, obteve-se os 3.3V necessários como nível lógico para o FPGA. O diagrama de circuito eletrônico pode ser visto no Apêndice 3. O caminho de volta do FPGA-porta paralela, foi
utilizado um circuito DRIVE de 5V para cada sinal de volta, formado por saturação e cortes de
transistores BC 548.
22
6
RESULTADOS
Os intervalos de tempo obtidos são os tempos que, tanto o sistema “F+V”, quanto
o AC levam para processar os dados, desde a criação da Matriz de Distâncias até a captação
da melhor rota.
O tempo gasto para a troca de dados entre PC e DE2 pode ser desconsiderado já
que cresce linearmente na proporção de 1ms por dado enviado e não afeta (para o número de
instâncias testadas) significativamente a contagem de tempo de processamento.
A Tabela 4 e o Figura 8 a seguir demonstram como foi o comportamento dos sistemas.
Tabela 4 – Tempo de processamento entre o AC e do F+V
Tempo de Processamento (s)
Nº de Cidades
4
5
6
7
8
9
10
11
Fonte própria.
F+V
Combinações Possíveis
0
0
0
0
0
0
0
0
2
0
14
0
1 149
3 1706
24
120
720
5040
40320
362880
3628800
39916800
AC
23
Figura 8 – Gráfico do Tempo de processamento entre o AC e F+V
Tempo em segundos
Tempo de Processamento entre o AC e o Sistema F+V
150
140
130
120
110
100
90
80
70
60
50
40
30
20
10
0
AC
F+V
1
2
3
4
5
6
7
8
Número de Cidades
Fonte própria.
6.1
ANÁLISE DE RESULTADOS
Na Tabela 4 em conjunto com a Figura 8 pode-se verificar, em vermelho e verde,
a relação entre número de instâncias e tempo de processamento para os dados coletados através do sistema “F+V” proposto e o AC. Ainda com um pequeno número de cidades, o sistema
proposto, comparado com um AC, não consegue obter resultados satisfatórios.
No capítulo 5.2 - TRABALHOS FUTUROS estão disponíveis algumas propostas
que têm a possibilidade de reverter este quadro.
24
7
CONCLUSÕES
Pelo gráfico apresentado no capítulo de resultados concluiu-se que não foi atingido o objetivo inicial que era desenvolver e implementar uma arquitetura do tipo F+V para
resolver o TSP em tempos de processamento satisfatórios.
Mesmo em contato com a Altera através de chamados de suporte desde Julho deste ano, não foi obtido um auxilio adequado quanto ao fornecimento de tutoriais atualizados.
Também por esses motivo foi gasto um certo tempo em estudos de detalhes do funcionamento
da ferrameta NIOS II IDE.
Por outro lado, mesmo sem ter atingido o objetivo principal, o conhecimento adquirido e fornecido ao curso de Engenharia Elétrica da Universidade Positivo, foi de grande
valor. Apartir deste ponto, outras equipes ou professores poderão utilizar esta pesquisa como
base para futuros projetos com FPGAs.
Com os resultados obtidos com a arquitetura de um processador NIOS II, o tempo
de processamento se tornou inviável apartir de 12 cidades, é extremamente alto ao se comparar ao sistema AC.
Vale comentar que as possibilidades oferecidas pelo sistema desenvolvido, são
muito grandes. O sistema criado, em conjunto com o FPGA utilizado, permite a paralelização
do processamento dos dados (Computação Paralela), a utilização de sistemas de aceleração
como o C2H (C to Hardware) ou, até mesmo, a implementação de algoritmos que utilizam
métodos herísticos para a solução de problemas combinatoriais, como Algoritmos Genéticos e
Redes Neurais.
7.1
TRABALHOS FUTUROS
Como comentado anteriormente, o sistema desenvolvido permite a utilização de
Computação Paralela, ou seja, utilizar mais de um núcleo de processador, assim, o trabalho de
processamento seria dividido em partes iguais, entre estes núcleos. O sistema desenvolvido
ocupou 1700 elementos lógicos do FPGA, e o chip utilizado (EP2C35 – Cyclone 2) possui
25
33000 elementos lógicos, ou seja, pode-se implementar uma quantidade de até 14 núcleos de
processadores (deixando reservado uma certa quantidade de elementos lógicos para dispositivos auxiliares).
Outra forma de aproveitar o sistema criado é utilizá-lo como uma cápsula para a
inserção de métodos heurísticos, ou seja, utilizar o mesmo processador Nios criado, a mesma
forma de comunicação e a mesma freqüência de trabalho, mas retirar o algoritmo JT (determinístico) e colocar em seu lugar, por exemplo, um Algoritmo Genético (heurístico).
26
REFERÊNCIAS
ALTERA, FPGA, CPLD, and ASIC.Disponível em <http://www.altera.com/>. Acesso em 28 mai.
2008.
DANTZIG, G.; FULKERSON, R.; JOHNSON, S. Solution of a Large-Scale Travelling-Salesman
Problem. California: The Rand Corporation, Santa Monica, 1954.
ELIB, TSP data. Disponível em < http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html >.Acesso
em 15 jun. 2008.
LOPES, Heitor S.; COELHO, Leandro S. Particle Swarm Optimization with Fast Local Search
for the Blind Traveling Salesman Problem. Potugal: Department of Electronics and Telecommunications University of Aveiro, 2002.
SEDGEWICK, Robert. Permutation Implementation Methods. Rhode Island: Computing Surveys,
1977.
GOLDBERG, D. Genetic Algoritms in Search, Optimization, and Machine Learning. Reading:Addison-Wesley Publishing Company, Inc, 1989.
SKLIAROVA, Iouliia; FERRARI, Antônio B. FPGA-Based Implementation of Genetic Algorithm
for the Traveling salesmas Problem and Its Industrial Application. Potugal: Department of Electronics and Telecommunications University of Aveiro, 2002.
SKLIAROVA, Iouliia; FERRARI, Antônio B. Introdução à Computação Reconfigurável. Potugal:
Revista do DETUA, 2003.
VARMA, A.; Jayadeva, J. A Novel Digital Neural Network for the Travelling Salesman Problem.
In: INTERNATIONAL CONFERENCE ON NEURAL INFORMATION PROCESSING – ICONIP’
02, 9., 2002. Singapura, o DETUA, 2002.