Aplicación de las GPU`S en la solución del problema de flujo máximo

Abstract

En los últimos años, el ámbito de la computación gráca ha sido uno de los principales objetos de estudio gracias al avance tecnológico llevado a cabo en los dispositivos dedicados a ello. Las GPUs modernas han visto potenciada su utilidad con la llegada de plataformas como CUDA que permiten escribir programas de propósito general en este tipo de procesadores paralelos. Entre los problemas a los que más se ha recurrido están todos aquellos relacionados con grafos, debido a su utilidad en numerosos campos de la vida real. Este trabajo se centra en la resolución del problema de hallar el ujo máximo de un grafo utilizando CUDA. Para ello, se estudian diferentes algoritmos existentes en la actualidad y se implementa una versión paralela de uno de ellos, el algoritmo de push-relabel. Se han realizado pruebas para medir el rendimiento de nuestra implementación sobre tres tipos diferentes de grafos, ADG, RMFGEN y Washington-RLG que son los típicamente utilizados para los problemas de ujo máximo. Las pruebas muestran cómo nuestra implementación es, en media, 20 veces más rápida que la implementación secuencial. [ABSTRACT] In the last few years, graphics computation has been one of the most important research elds thanks to the advances in GPU hardware. The evolution of these devices has given researchers access to low cost hardware to solve general-purpose problems. Frameworks like CUDA have been developed in order to help programmers to write code for the GPU exposing the device as an array of SIMD multi-core processors. Recently, researchers have focused on solving graph problems in this new platform due to its wide range of applications. This document focuses in the resolution of the maximum ow problem using CUDA. We present some of the faster algorithms to date and implement the parallel version of one of them, the push-relabel algorithm. We use three of the most common type of graphs for the maximum ow problem in our evaluations, ADG's, RMFGEN's and Washington-RLG's. Experimental results show that our implementation achieves 20x speedup when compared with the sequential version of the algorithm.