Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-06T15:00:35Z
No. of bitstreams: 2
Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2014-10-06T15:58:27Z (GMT) No. of bitstreams: 2
Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-10-06T15:58:27Z (GMT). No. of bitstreams: 2
Dissertação - Gustavo Siqueira Vinhal - 2013.pdf: 543638 bytes, checksum: 0cfeff261acd147877fc67035e17c1fb (MD5)
license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5)
Previous issue date: 2013-08-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Many relevant problems to NP-Hard class are present in the real world. Among them we
can mention the problems of network design (PNDs) that involve electricity distribution,
vehicle traffic, and others. There are not algorithms which provide a exact solution for
these types of problems with an acceptable computation time. Over the years, research
has been developed used evolutionary algorithms (EAs) to provide an efficient solution
with a acceptable computation time for these problems. In addition, appropriate data
structures may further improve the performance of EAs to PNDs. The node-depth-degree
(NDDE) representation have show significant results for PNDs. The application of EAs
in hardware can improve the performance of the algorithm. In this sense, this work
presents the implementation of a EA in Nios II processor of a FPGA board to solving
the PND minimum spanning tree with degree constraint. The results demonstrate that the
implementation of EAs in hardware brings significant results with better performance,
due to the power of parallelism present in the FPGA. / Diversos problemas pertinentes a classe NP-Difícil estão presentes no mundo real. Dentre
eles pode-se citar os problemas de projeto de redes (PPRs) que envolvem distribuição de
energia elétrica, tráfego de veículos, entre outros. Não existem algoritmos que forneçam
uma solução exata para esses tipos de problemas com um tempo de computação aceitável.
Ao longo dos anos pesquisas estão sendo desenvolvidas utilizado algoritmos evolutivos
(EAs) para fornecer uma solução eficiente com tempo de computção aceitável para tais
problemas. Além disso, estruturas de dados adequadas podem melhorar ainda mais o desempenho
dos EAs para PPRs. A representação nó-profundidade-grau (NDDE) apresenta
resultados significativos para PPRs. A aplicação de EAs em hardware pode melhorar o
desempenho do algoritmo. Nesse sentido, este trabalho apresenta a implementação de um
EA no processador Nios II de uma placa FPGA para solução do PPR da árvore geradora
mínima com restrição de grau. Os resultados demonstram que a implementação de EAs
em hardware traz resultados significativos com melhor desempenho, devido ao poder de
paralelismo presente no FPGA.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tede/3291 |
| Date | 19 August 2013 |
| Creators | Vinhal, Gustavo Siqueira |
| Contributors | Soares, Telma Woerle de Lima, Soares, Telma Woerle de Lima, Soares, Anderson da Silva, Gabriel, Paulo Henrique Ribeiro |
| Publisher | Universidade Federal de Goiás, Programa de Pós-graduação em Ciência da Computação (INF), UFG, Brasil, Instituto de Informática - INF (RG) |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | http://creativecommons.org/licenses/by-nc-nd/4.0/, info:eu-repo/semantics/openAccess |
| Relation | -3303550325223384799, 600, 600, 600, 600, -7712266734633644768, 8930092515683771531, 2075167498588264571 |
Page generated in 0.0024 seconds