Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/2610
Registro completo de metadados
Campo DCValorIdioma
dc.creatorAlvino, Luiz Fernando-
dc.date.accessioned2016-02-26T21:32:06Z-
dc.date.available2021-09-30T19:55:52Z-
dc.date.issued2015-
dc.identifier.urihttps://repositorio.ufms.br/handle/123456789/2610-
dc.description.abstractO problema do fluxo máximo em redes é um problema fundamental de teoria dos grafos, com muitas aplicações importantes. Os algoritmos para o fluxo máximo baseados no método push-relabel são conhecidos por serem mais eficientes assintoticamente e terem menor tempo de execução na prática. Vários algoritmos paralelos foram propostos, mas poucos deles tiveram tempos de execução menores do que a implementação hipr de Goldberg, baseada em push-relabel. O objetivo geral desta dissertação é discutir as soluções sequenciais e paralelas para o problema do fluxo máximo em redes. Uma contribuição relevante é que propomos um novo algoritmo paralelo híbrido OpenMP-CUDA que explora a paralelização das heurísticas rotulação global e rotulação gap, além de utilizar o processamento em CPU e GPU adaptativamente para maximizar a eficiência de execução. Os resultados dos testes realizados mostram que esse algoritmo é até 5 vezes mais rápido do que a implementação hipr.pt_BR
dc.description.abstractABSTRACT - The maximum flow problem is a fundamental problem of graph theory with important applications. Max-flow algorithms based on the push-relabel method are known to have better complexity bounds and faster practical execution. Other algorithms were proposed, but few had better execution speed than the best serial implementation, the Goldberg’s hipr. The goal of this dissertation is to discuss the sequential and parallel solutions to the max-flow problem. A significant contribution is that we propose a new parallel hybrid algorithm OpenMP-CUDA that explores the parallelization of heuristics, such as global relabeling and gap relabeling, and use the processing in CPU and GPU adaptively to maximize execution efficiency. The results of the tests show that this algorithm is up to 5 times faster than the hipr implementation.pt_BR
dc.language.isoporpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectAlgorítmos Computacionaispt_BR
dc.subjectComputer Algorithmspt_BR
dc.subjectRedes de Computadorespt_BR
dc.subjectComputer Networkpt_BR
dc.subjectComputaçãopt_BR
dc.subjectComputer Sciencept_BR
dc.titleProblema do fluxo máximo em redes utilizando openMP e CUDApt_BR
dc.typeDissertaçãopt_BR
dc.contributor.advisor1Stefanes, Marco Aurélio-
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
LUIZ FERNANDO ALVINO.pdf490,9 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.