A New GPU-based Approach to the Shortest Path Problem

Hector Ortega-Arranz, Yuri Torres, Diego R. Llanos, Arturo Gonzalez-Escribano
Dept. Informatica, Universidad de Valladolid, Spain
International Conference on High Performance Computing and Simulation (HPCS 2013), 2013


   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},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: