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 TamanhoFormato 
Dissertacao_AvaliacaoTecnicasParalelizacao.pdf1,5 MBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons