Use este identificador para citar ou linkar para este item:
https://repositorio.ufpa.br/jspui/handle/2011/7428
Tipo: | Dissertação |
Data do documento: | 6-Mar-2015 |
Autor(es): | TADAIESKY, Vincent Willian Araújo |
Primeiro(a) Orientador(a): | SANTANA, Ádamo Lima de |
Título: | Avaliação de técnicas de paralelização de algoritmos bioinspirados utilizando computação GPU: um estudo de casos para otimização de roteamento em redes ópticas |
Citar como: | TADAIESKY, Vincent Willian Araújo. Avaliação de técnicas de paralelização de algoritmos bioinspirados utilizando computação GPU: um estudo de casos para otimização de roteamento em redes ópticas. Orientador: Ádamo Lima de Santana. 2015. 80 f. Dissertação (Mestrado em Engenharia Elétrica ) - Instituto de Tecnologia, Universidade Federal do Pará, Belém, 2015. Disponível em: http://repositorio.ufpa.br/jspui/handle/2011/7428. Acesso em:. |
Resumo: | A aplicação em logística de distribuição é diversa, a exemplo do planejamento de transporte e entrega de mercadorias ou no roteamento de dados em redes de telecomunicações. Dado a amplitude e capilaridade desses problemas, trabalhos vêm sendo desenvolvidos visando reduzir os gastos para o funcionamento de redes dessa magnitude, sobretudo no que tange à demanda de energia elétrica. Sendo assim, o presente trabalho apresenta uma proposta de método de resolução de problemas de roteamento com alto grau de demanda. O método proposto é baseado em algoritmos bioinspirados, que aliados a outros métodos, garantem a integridade das soluções obtidas, além de sua proximidade ao ótimo. Entretanto, tais algoritmos se tornam computacionalmente custosos à medida que a complexidade da aplicação em questão aumenta e, portanto, ambientes multiprocessados, como plataformas de computação em GPU, vêm sendo largamente utilizados para aumentar a performance dos mesmos. Sendo assim, este trabalho visa realizar testes sobre as técnicas de paralelização desses algoritmos mais difundidas, com o objetivo de avaliar qual estratégia tem melhor relação com cada algoritmo testado para o problema descrito acima. Os algoritmos que auxiliaram nos testes foram Algoritmos Genéticos e Otimização por Enxame de Partículas, que são altamente difundidos. Os resultados mostram que a estratégia de paralelização a ser utilizada depende tanto da plataforma em que está sendo implementada, quanto do problema a ser tratado. |
Abstract: | The applications on distribution logistics are diverse, such as the transportation planning and delivery of goods or in telecommunication networks data routing. Given the breadth and capillarity of these problems, studies have been developed to reduce network operating costs of this magnitude, especially regarding the demand for electricity. Therefore, this work proposes a method of resolution of routing problems with high demand. The proposed method is based on bio-inspired algorithms, which combined with other methods, ensure the integrity of the solutions, as well as its proximity to optimum. Nevertheless, such algorithms becomes computationally expensive as the application complexity in question grows and, therefore, multiprocessor environment, like GPU Computing platforms, has being widely used to increase bio-inspired algorithms performance. Thus, this work aims perform tests about the widespread parallelization techniques of these algorithms, intending to make an evaluation of which strategies has better relation with each tested algorithm. In order to do this, the routing problem in WDW optics networks with high demand level was used as a case study, in which it is needed define which are the better routes to demands sent simultaneously. The algorithms that assisted the tests were Genetic Algorithms and Swarm Particle Optimization, which are highly disseminated. The results show that the parallelization strategy to be used depends as much on the platform in which has been implemented, as the problem to be treaty. |
Palavras-chave: | Algoritmos bioinspirados CUDA - Arquitetura de dispositivo unificado de computador Computação de unidade de processamento gráfico Roteamento Bio-inspired algorithms CUDA - Computer unified device architecture Graphics processing unit computing Routing |
CNPq: | CNPQ::ENGENHARIAS::ENGENHARIA ELETRICA::TELECOMUNICACOES CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::SISTEMAS DE COMPUTACAO |
País: | Brasil |
Instituição: | Universidade Federal do Pará |
Sigla da Instituição: | UFPA |
Instituto: | Instituto de Tecnologia |
Programa: | Programa de Pós-Graduação em Engenharia Elétrica |
Tipo de Acesso: | Acesso Aberto |
Aparece nas coleções: | Dissertações em Engenharia Elétrica (Mestrado) - PPGEE/ITEC |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
Dissertacao_AvaliacaoTecnicasParalelizacao.pdf | 1,5 MB | Adobe PDF | Visualizar/Abrir |
Este item está licenciado sob uma Licença Creative Commons