Ioperativa

Universidad Complutense de Madrid FACULTAD DE INFORMÁTICA
INGENIERÍA EN INFORMÁTICA

SISTEMAS INFORMÁTICOS ALGORITMOS PARA GRAFOS Y PROGRAMACIÓN DE PROPÓSITO GENERAL EN CUDA
Curso 2008/2009

Ezequiel Denegri Dirección: Pedro Jesús Martín de la Calle

Guillermo Frontera Sánchez

Antonio Gavilanes Franco

 

 

Sistemas Informáticos  Curso 2008/2009 

Resumen 
Las actualesunidades 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 modelode 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 ala 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 havestudied 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 toevolutionary programming, computer vision and computing performed by a search engine.

Palabras clave: CUDA, General Purpose Computing on Graphics Processing Units, GPGPU, algoritmos sobre grafos, algoritmos evolutivos

i

 

 

Sistemas Informáticos  Curso 2008/2009 

Índice 
Resumen............................................................................................................................................... i  Abstract ................................................................................................................................................ i  Índice .................................................................................................................................................. iii  Autorización....................................................................................................................................... v  1.  2.  Introducción ..............................................................................................................................1  CUDA (Compute Unified Device Architecture) ................................................................. 3  2.1. Modelo de programación ................................................................................................. 3  2.1.1.  Disposición espacial de los hilos............................................................................. 3  2.2.  Modelo de memoria .......................................................................................................... 6  2.2.1.  Memoriaglobal .......................................................................................................... 7  2.2.2.  Memoria compartida ................................................................................................ 7  2.3.  Organización de la ejecución ........................................................................................... 8  2.4.  API de CUDA...