Soluciones CUDA al problema del camino más corto desde un solo origen

Pedro J. Martín de la Calle, Roberto Torres, Antonio Gavilanes Franco

ANACAP 2008: Aplicaciones de Nuevas Arquitecturas de Consumo y Altas Prestaciones .

Abstract:
Las GPUs han evolucionado hasta convertirse en máquinas altamente paralelizables con una capacidad de cómputo enorme. Además, actualmente pueden conseguirse a bajo precio, por lo que constituyen un ardware del que disponen casi todos los ordenadores corrientes. Aunque los algoritmos de búsqueda sobre grafos pueden paralelizarse, se han diseñado pocos algoritmos paralelos para esta tarea, ya que no existía a mano hardware real de este tipo. En este trabajo presentamos una serie de algoritmos que resuelven en GPU el problema del camino más corto desde un solo origen para grafos de gran tamaño, usando CUDA en su implementación. Probamos la corrección de todos ellos, mostrando además que la propuesta de [10] es incorrecta. En cuanto a ejecución, hemos obtenido tiempos que son hasta 15 veces mejores que sus correspondientes en CPU para grafos dispersos representados mediante listas de adyacencia, con 8 millones de vértices y 56 millones de arcos; y hasta 35 veces mejores para grafos densos representados por matrices de adyacencia, con 3 mil vértices y 1 millón y medio de arcos.

Donwload: Download link pdf download bibTexbibtex Publisher URLurl