Problema do fluxo máximo em redes utilizando openMP e CUDA

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.

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.