Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA
Đã lưu trong:
| Tác giả chính: | |
|---|---|
| Ngày xuất bản: | 2013 |
| Định dạng: | Master thesis |
| Ngôn ngữ: | por |
| Nguồn: | Repositório Institucional da UFG |
| Download full: | http://repositorio.bc.ufg.br/tede/handle/tede/3291 |
Tóm tắt: | 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. |
| _version_ | 1871426380947783680 |
|---|---|
| author | Vinhal, Gustavo Siqueira |
| author_browse | Vinhal, Gustavo Siqueira |
| author_facet | Vinhal, Gustavo Siqueira |
| author_role | author |
| bitstream.checksum.fl_str_mv | bd3efa91386c1718a7f26a329fdcb468 4afdbb8c545fd630ea7db775da747b2f 1e0094e9d8adcf16b18effef4ce7ed83 9da0b6dfac957114c6a7714714b86306 0cfeff261acd147877fc67035e17c1fb 80ff23a5fea2abd70464f3aa2557cbaf 7beb22ea85025053c7d100c05aa4b119 |
| bitstream.checksumAlgorithm.fl_str_mv | MD5 MD5 MD5 MD5 MD5 MD5 MD5 |
| bitstream.url.fl_str_mv | http://repositorio.bc.ufg.br/tede/bitstreams/b82b6000-a6fd-4fce-ba16-0167649bff91/download http://repositorio.bc.ufg.br/tede/bitstreams/9163055f-a38f-4f09-ac1a-af3cf48ce18e/download http://repositorio.bc.ufg.br/tede/bitstreams/71f077e1-b400-4737-a066-6595bdeb8466/download http://repositorio.bc.ufg.br/tede/bitstreams/16d23368-adf4-4062-ada0-c524c7f0a321/download http://repositorio.bc.ufg.br/tede/bitstreams/348e0348-1daa-47f1-9a79-2cd8ad55bcec/download http://repositorio.bc.ufg.br/tede/bitstreams/e7dfa72b-e0c8-4bd2-a8f9-d6567a60013a/download http://repositorio.bc.ufg.br/tede/bitstreams/ff83a65d-5e1f-4616-82d6-6cb916c351b6/download |
| collection | Repositório Institucional da UFG |
| contributor_str_mv | Soares, Telma Woerle de Lima Soares, Telma Woerle de Lima Soares, Anderson da Silva Gabriel, Paulo Henrique Ribeiro |
| dc.contributor.advisor1.fl_str_mv | Soares, Telma Woerle de Lima |
| dc.contributor.advisor1Lattes.fl_str_mv | http://lattes.cnpq.br/6296363436468330 |
| dc.contributor.author.fl_str_mv | Vinhal, Gustavo Siqueira |
| dc.contributor.referee1.fl_str_mv | Soares, Telma Woerle de Lima |
| dc.contributor.referee2.fl_str_mv | Soares, Anderson da Silva |
| dc.contributor.referee3.fl_str_mv | Gabriel, Paulo Henrique Ribeiro |
| dc.date.accessioned.fl_str_mv | 2014-10-06T15:58:27Z |
| dc.date.issued.fl_str_mv | 2013-08-19 |
| dc.format.none.fl_str_mv | application/pdf |
| dc.identifier.citation.fl_str_mv | VINHAL, Gustavo Siqueira. Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA. 2013. 72 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2013. |
| dc.identifier.uri.fl_str_mv | http://repositorio.bc.ufg.br/tede/handle/tede/3291 |
| dc.language.iso.fl_str_mv | por |
| dc.publisher.country.fl_str_mv | Brasil |
| dc.publisher.department.fl_str_mv | Instituto de Informática - INF (RG) |
| dc.publisher.initials.fl_str_mv | UFG |
| dc.publisher.none.fl_str_mv | Universidade Federal de Goiás |
| dc.publisher.program.fl_str_mv | Programa de Pós-graduação em Ciência da Computação (INF) |
| dc.relation.cnpq.fl_str_mv | 8930092515683771531 |
| dc.relation.confidence.fl_str_mv | 600 600 600 600 |
| dc.relation.department.fl_str_mv | -7712266734633644768 |
| dc.relation.program.fl_str_mv | -3303550325223384799 |
| dc.relation.sponsorship.fl_str_mv | 2075167498588264571 |
| dc.rights.driver.fl_str_mv | http://creativecommons.org/licenses/by-nc-nd/4.0/ info:eu-repo/semantics/openAccess |
| dc.source.none.fl_str_mv | reponame:Repositório Institucional da UFG instname:Universidade Federal de Goiás (UFG) instacron:UFG |
| dc.subject.cnpq.fl_str_mv | CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO |
| dc.subject.eng.fl_str_mv | Network design Minimum spanning tree Evolutionary algorithms Node- depth-degree FPGA |
| dc.subject.por.fl_str_mv | Projeto de rede Árvore geradora mínima Algoritmos evolutivos Nó-profundidade-grau FPGA |
| dc.title.alternative.eng.fl_str_mv | Implementation of a evolutionary algorithm utilizing the representation node-depth-degree in Nios II processor of FPGA |
| dc.title.por.fl_str_mv | Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA |
| dc.type.driver.fl_str_mv | info:eu-repo/semantics/masterThesis |
| dc.type.status.fl_str_mv | info:eu-repo/semantics/publishedVersion |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | UFG-2_8176ce583dacbfec60cc7aa48bbb8d96 |
| identifier_str_mv | VINHAL, Gustavo Siqueira. Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA. 2013. 72 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2013. |
| instacron_str | UFG |
| institution | UFG |
| instname_str | Universidade Federal de Goiás (UFG) |
| language | por |
| network_acronym_str | UFG-2 |
| network_name_str | Repositório Institucional da UFG |
| oai_identifier_str | oai:repositorio.bc.ufg.br:tede/3291 |
| publishDate | 2013 |
| publishDateSort | 2013 |
| publisher.none.fl_str_mv | Universidade Federal de Goiás |
| reponame_str | Repositório Institucional da UFG |
| repository.mail.fl_str_mv | grt.bc@ufg.br |
| repository.name.fl_str_mv | Repositório Institucional da UFG - Universidade Federal de Goiás (UFG) |
| repository_id_str | oai:repositorio.bc.ufg.br:tede/1234 |
| rights_invalid_str_mv | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
| spelling | Soares, Telma Woerle de Limahttp://lattes.cnpq.br/6296363436468330Soares, Telma Woerle de LimaSoares, Anderson da SilvaGabriel, Paulo Henrique RibeiroVinhal, Gustavo Siqueira2014-10-06T15:58:27Z2013-08-19VINHAL, Gustavo Siqueira. Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA. 2013. 72 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2013.http://repositorio.bc.ufg.br/tede/handle/tede/3291Many 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.Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESapplication/pdfhttp://repositorio.bc.ufg.br/tede/retrieve/9765/Disserta%c3%a7%c3%a3o%20-%20Gustavo%20Siqueira%20Vinhal%20-%202013.pdf.jpgporUniversidade Federal de GoiásPrograma de Pós-graduação em Ciência da Computação (INF)UFGBrasilInstituto de Informática - INF (RG)http://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/openAccessProjeto de redeÁrvore geradora mínimaAlgoritmos evolutivosNó-profundidade-grauFPGANetwork designMinimum spanning treeEvolutionary algorithmsNode- depth-degreeFPGACIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAOImplementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGAImplementation of a evolutionary algorithm utilizing the representation node-depth-degree in Nios II processor of FPGAinfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/masterThesis-3303550325223384799600600600600-771226673463364476889300925156837715312075167498588264571reponame:Repositório Institucional da UFGinstname:Universidade Federal de Goiás (UFG)instacron:UFGLICENSElicense.txtlicense.txttext/plain; charset=utf-82165http://repositorio.bc.ufg.br/tede/bitstreams/b82b6000-a6fd-4fce-ba16-0167649bff91/downloadbd3efa91386c1718a7f26a329fdcb468MD51CC-LICENSElicense_urllicense_urltext/plain; charset=utf-849http://repositorio.bc.ufg.br/tede/bitstreams/9163055f-a38f-4f09-ac1a-af3cf48ce18e/download4afdbb8c545fd630ea7db775da747b2fMD52license_textlicense_texttext/html; charset=utf-822302http://repositorio.bc.ufg.br/tede/bitstreams/71f077e1-b400-4737-a066-6595bdeb8466/download1e0094e9d8adcf16b18effef4ce7ed83MD53license_rdflicense_rdfapplication/rdf+xml; charset=utf-823148http://repositorio.bc.ufg.br/tede/bitstreams/16d23368-adf4-4062-ada0-c524c7f0a321/download9da0b6dfac957114c6a7714714b86306MD54ORIGINALDissertação - Gustavo Siqueira Vinhal - 2013.pdfDissertação - Gustavo Siqueira Vinhal - 2013.pdfapplication/pdf543638http://repositorio.bc.ufg.br/tede/bitstreams/348e0348-1daa-47f1-9a79-2cd8ad55bcec/download0cfeff261acd147877fc67035e17c1fbMD55TEXTDissertação - Gustavo Siqueira Vinhal - 2013.pdf.txtDissertação - Gustavo Siqueira Vinhal - 2013.pdf.txtExtracted Texttext/plain122280http://repositorio.bc.ufg.br/tede/bitstreams/e7dfa72b-e0c8-4bd2-a8f9-d6567a60013a/download80ff23a5fea2abd70464f3aa2557cbafMD56THUMBNAILDissertação - Gustavo Siqueira Vinhal - 2013.pdf.jpgDissertação - Gustavo Siqueira Vinhal - 2013.pdf.jpgGenerated Thumbnailimage/jpeg3854http://repositorio.bc.ufg.br/tede/bitstreams/ff83a65d-5e1f-4616-82d6-6cb916c351b6/download7beb22ea85025053c7d100c05aa4b119MD57tede/32912014-10-09 03:03:35.537http://creativecommons.org/licenses/by-nc-nd/4.0/Acesso Abertoopen.accessoai:repositorio.bc.ufg.br:tede/3291http://repositorio.bc.ufg.br/tedeRepositório InstitucionalPUBhttps://repositorio.bc.ufg.br/tedeserver/oai/requestgrt.bc@ufg.bropendoar:oai:repositorio.bc.ufg.br:tede/12342014-10-09T06:03:35Repositório Institucional da UFG - Universidade Federal de Goiás (UFG)Tk9UQTogQ09MT1FVRSBBUVVJIEEgU1VBIFBSw5NQUklBIExJQ0VOw4dBCkVzdGEgbGljZW7Dp2EgZGUgZXhlbXBsbyDDqSBmb3JuZWNpZGEgYXBlbmFzIHBhcmEgZmlucyBpbmZvcm1hdGl2b3MuCgpMSUNFTsOHQSBERSBESVNUUklCVUnDh8ODTyBOw4NPLUVYQ0xVU0lWQQoKQ29tIGEgYXByZXNlbnRhw6fDo28gZGVzdGEgbGljZW7Dp2EsIHZvY8OqIChvIGF1dG9yIChlcykgb3UgbyB0aXR1bGFyIGRvcyBkaXJlaXRvcyBkZSBhdXRvcikgY29uY2VkZSDDoCBVbml2ZXJzaWRhZGUgClhYWCAoU2lnbGEgZGEgVW5pdmVyc2lkYWRlKSBvIGRpcmVpdG8gbsOjby1leGNsdXNpdm8gZGUgcmVwcm9kdXppciwgIHRyYWR1emlyIChjb25mb3JtZSBkZWZpbmlkbyBhYmFpeG8pLCBlL291IApkaXN0cmlidWlyIGEgc3VhIHRlc2Ugb3UgZGlzc2VydGHDp8OjbyAoaW5jbHVpbmRvIG8gcmVzdW1vKSBwb3IgdG9kbyBvIG11bmRvIG5vIGZvcm1hdG8gaW1wcmVzc28gZSBlbGV0csO0bmljbyBlIAplbSBxdWFscXVlciBtZWlvLCBpbmNsdWluZG8gb3MgZm9ybWF0b3Mgw6F1ZGlvIG91IHbDrWRlby4KClZvY8OqIGNvbmNvcmRhIHF1ZSBhIFNpZ2xhIGRlIFVuaXZlcnNpZGFkZSBwb2RlLCBzZW0gYWx0ZXJhciBvIGNvbnRlw7pkbywgdHJhbnNwb3IgYSBzdWEgdGVzZSBvdSBkaXNzZXJ0YcOnw6NvIApwYXJhIHF1YWxxdWVyIG1laW8gb3UgZm9ybWF0byBwYXJhIGZpbnMgZGUgcHJlc2VydmHDp8Ojby4KClZvY8OqIHRhbWLDqW0gY29uY29yZGEgcXVlIGEgU2lnbGEgZGUgVW5pdmVyc2lkYWRlIHBvZGUgbWFudGVyIG1haXMgZGUgdW1hIGPDs3BpYSBhIHN1YSB0ZXNlIG91IApkaXNzZXJ0YcOnw6NvIHBhcmEgZmlucyBkZSBzZWd1cmFuw6dhLCBiYWNrLXVwIGUgcHJlc2VydmHDp8Ojby4KClZvY8OqIGRlY2xhcmEgcXVlIGEgc3VhIHRlc2Ugb3UgZGlzc2VydGHDp8OjbyDDqSBvcmlnaW5hbCBlIHF1ZSB2b2PDqiB0ZW0gbyBwb2RlciBkZSBjb25jZWRlciBvcyBkaXJlaXRvcyBjb250aWRvcyAKbmVzdGEgbGljZW7Dp2EuIFZvY8OqIHRhbWLDqW0gZGVjbGFyYSBxdWUgbyBkZXDDs3NpdG8gZGEgc3VhIHRlc2Ugb3UgZGlzc2VydGHDp8OjbyBuw6NvLCBxdWUgc2VqYSBkZSBzZXUgCmNvbmhlY2ltZW50bywgaW5mcmluZ2UgZGlyZWl0b3MgYXV0b3JhaXMgZGUgbmluZ3XDqW0uCgpDYXNvIGEgc3VhIHRlc2Ugb3UgZGlzc2VydGHDp8OjbyBjb250ZW5oYSBtYXRlcmlhbCBxdWUgdm9jw6ogbsOjbyBwb3NzdWkgYSB0aXR1bGFyaWRhZGUgZG9zIGRpcmVpdG9zIGF1dG9yYWlzLCB2b2PDqiAKZGVjbGFyYSBxdWUgb2J0ZXZlIGEgcGVybWlzc8OjbyBpcnJlc3RyaXRhIGRvIGRldGVudG9yIGRvcyBkaXJlaXRvcyBhdXRvcmFpcyBwYXJhIGNvbmNlZGVyIMOgIFNpZ2xhIGRlIFVuaXZlcnNpZGFkZSAKb3MgZGlyZWl0b3MgYXByZXNlbnRhZG9zIG5lc3RhIGxpY2Vuw6dhLCBlIHF1ZSBlc3NlIG1hdGVyaWFsIGRlIHByb3ByaWVkYWRlIGRlIHRlcmNlaXJvcyBlc3TDoSBjbGFyYW1lbnRlIAppZGVudGlmaWNhZG8gZSByZWNvbmhlY2lkbyBubyB0ZXh0byBvdSBubyBjb250ZcO6ZG8gZGEgdGVzZSBvdSBkaXNzZXJ0YcOnw6NvIG9yYSBkZXBvc2l0YWRhLgoKQ0FTTyBBIFRFU0UgT1UgRElTU0VSVEHDh8ODTyBPUkEgREVQT1NJVEFEQSBURU5IQSBTSURPIFJFU1VMVEFETyBERSBVTSBQQVRST0PDjU5JTyBPVSAKQVBPSU8gREUgVU1BIEFHw4pOQ0lBIERFIEZPTUVOVE8gT1UgT1VUUk8gT1JHQU5JU01PIFFVRSBOw4NPIFNFSkEgQSBTSUdMQSBERSAKVU5JVkVSU0lEQURFLCBWT0PDiiBERUNMQVJBIFFVRSBSRVNQRUlUT1UgVE9ET1MgRSBRVUFJU1FVRVIgRElSRUlUT1MgREUgUkVWSVPDg08gQ09NTyAKVEFNQsOJTSBBUyBERU1BSVMgT0JSSUdBw4fDlUVTIEVYSUdJREFTIFBPUiBDT05UUkFUTyBPVSBBQ09SRE8uCgpBIFNpZ2xhIGRlIFVuaXZlcnNpZGFkZSBzZSBjb21wcm9tZXRlIGEgaWRlbnRpZmljYXIgY2xhcmFtZW50ZSBvIHNldSBub21lIChzKSBvdSBvKHMpIG5vbWUocykgZG8ocykgCmRldGVudG9yKGVzKSBkb3MgZGlyZWl0b3MgYXV0b3JhaXMgZGEgdGVzZSBvdSBkaXNzZXJ0YcOnw6NvLCBlIG7Do28gZmFyw6EgcXVhbHF1ZXIgYWx0ZXJhw6fDo28sIGFsw6ltIGRhcXVlbGFzIApjb25jZWRpZGFzIHBvciBlc3RhIGxpY2Vuw6dhLgo= |
| spellingShingle | Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA Vinhal, Gustavo Siqueira Projeto de rede Árvore geradora mínima Algoritmos evolutivos Nó-profundidade-grau FPGA Network design Minimum spanning tree Evolutionary algorithms Node- depth-degree FPGA CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO |
| status_str | publishedVersion |
| title | Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA |
| title_full | Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA |
| title_fullStr | Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA |
| title_full_unstemmed | Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA |
| title_short | Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA |
| title_sort | Implementação de um algoritmo evolutivo utilizando a representação nó-profundidade-grau no processador Nios II do FPGA |
| topic | Projeto de rede Árvore geradora mínima Algoritmos evolutivos Nó-profundidade-grau FPGA Network design Minimum spanning tree Evolutionary algorithms Node- depth-degree FPGA CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO |
| url | http://repositorio.bc.ufg.br/tede/handle/tede/3291 |