Use este identificador para citar ou linkar para este item:
https://repositorio.ufms.br/handle/123456789/2610
Registro completo de metadados
Campo DC | Valor | Idioma |
---|---|---|
dc.creator | Alvino, Luiz Fernando | - |
dc.date.accessioned | 2016-02-26T21:32:06Z | - |
dc.date.available | 2021-09-30T19:55:52Z | - |
dc.date.issued | 2015 | - |
dc.identifier.uri | https://repositorio.ufms.br/handle/123456789/2610 | - |
dc.description.abstract | O 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.abstract | ABSTRACT - 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.iso | por | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Algorítmos Computacionais | pt_BR |
dc.subject | Computer Algorithms | pt_BR |
dc.subject | Redes de Computadores | pt_BR |
dc.subject | Computer Network | pt_BR |
dc.subject | Computação | pt_BR |
dc.subject | Computer Science | pt_BR |
dc.title | Problema do fluxo máximo em redes utilizando openMP e CUDA | pt_BR |
dc.type | Dissertação | pt_BR |
dc.contributor.advisor1 | Stefanes, 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 | Tamanho | Formato | |
---|---|---|---|---|
LUIZ FERNANDO ALVINO.pdf | 490,9 kB | Adobe PDF | ![]() Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.