Experimental Evaluation of GPU Solutions to the Single Source Shortest Path Problem

Abstract: Originally designed for computer graphics, the modern graphics processing unit (GPU) has now become a potential powerhouse for parallel calculations through the use of platforms such as CUDA and OpenCL. This paper presents an experimental evaluation of GPU- and CPU-parallel as well as CPU-sequential implementations for solving the single source shortest path problem. The algorithms tested are versions of Dijkstra’s algorithm, the Bellman-Ford algorithm, and Delta-Stepping, from the Boost Graph Library, Parallel Boost Graph Library, Gunrock and LoneStarGPU. Testing the implementations on large graphs modeled on road networks over USA, results indicate that the sequential Boost implementation of Dijkstra’s algorithm gives the best performance if memory transfer time to and from GPU is taken into account. The paper also presents a discussion on possible reasons for this result.