Detalhes bibliográficos
Ano de defesa: |
2015 |
Autor(a) principal: |
Alvino, Luiz Fernando |
Orientador(a): |
Stefanes, Marco Aurélio |
Banca de defesa: |
Não Informado pela instituição |
Tipo de documento: |
Dissertação
|
Tipo de acesso: |
Acesso aberto |
Idioma: |
por |
Instituição de defesa: |
Não Informado pela instituição
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: |
|
Link de acesso: |
https://repositorio.ufms.br/handle/123456789/2610
|
Resumo: |
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. |