Algoritmos para grafos y programación de propósito general en CUDA

Abstract

Las actuales unidades de procesamiento gráfico de NVIDIA disponen de una interfaz de programación que permite utilizarlas para tareas de propósito general (GPGPU). El objetivo de este trabajo es acelerar la ejecución de algoritmos clásicos de la teoría de grafos utilizando la interfaz de programación CUDA. Para ello, hemos estudiado la formulación y posterior codificación de estos algoritmos en el modelo de programación paralela de CUDA. En particular, los algoritmos estudiados son la búsqueda de los caminos mínimos desde un único origen, la búsqueda del árbol de recubrimiento mínimo y la búsqueda de todos los caminos mínimos entre pares de vértices. También hemos estudiado algunos algoritmos no relacionados con la teoría de grafos, haciendo una breve exposición de aplicaciones de la GPGPU a la programación evolutiva, la visión por computador y al cómputo requerido por un motor de búsqueda. [ABSTRACT] Current graphics processing units manufactured by NVIDIA provide a programming interface that allows them to perform general purpose computation. The aim of this work is to speed up some classic algorithms in graph theory using CUDA programming interface. To this end, we have studied sequential formulations of these algorithms and their related code using CUDA parallel programming model. Specifically, we have studied algorithms for the single source shortest path search, the minimum spanning tree search and the all vertex pairs shortest path search. We have also studied several other algorithms not related to graph theory as an overview of GPGPU applications to evolutionary programming, computer vision and computing performed by a search engine.