A New GPU-based Approach to the Shortest Path Problem
Dept. Informatica, Universidad de Valladolid, Spain
International Conference on High Performance Computing and Simulation (HPCS 2013), 2013
@article{ortega2013new,
title={A New GPU-based Approach to the Shortest Path Problem},
author={Ortega-Arranz, Hector and Torres, Yuri and Llanos, Diego R and Gonzalez-Escribano, Arturo},
year={2013}
}
The Single-Source Shortest Path (SSSP) problem arises in many different fields. In this paper we present a GPUbased version of the Crauser et al. SSSP algorithm. Our work significantly speeds up the computation of the SSSP, not only with respect to the CPU-based version, but also to other state-of-the-art GPU implementation based on Dijkstra, due to Martin et al. Both GPU implementations have been evaluated using the last Nvidia architecture (Kepler). Our experimental results show that the new GPU-Crauser algorithm leads to speed-ups from 13x to 220x with respect to the CPU version and a performance gain of up to 17% with respect the GPU-Martin algorithm.
July 16, 2013 by hgpu