Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

Locality-Based Relaxation: An Efficient Method for GPU-Based Computation of Shortest Paths

Abstract : This paper presents a novel parallel algorithm for solving the Single-Source Shortest Path (SSSP) problem on GPUs. The proposed algorithm is based on the idea of locality-based relaxation, where instead of updating just the distance of a single vertex v, we update the distances of v’s neighboring vertices up to k steps. The proposed algorithm also implements a communication-efficient method (in the CUDA programming model) that minimizes the number of kernel launches, the number of atomic operations and the frequency of CPU-GPU communication without any need for thread synchronization. This is a significant contribution as most existing methods often minimize one at the expense of another. Our experimental results demonstrate that our approach outperforms most existing methods on real-world road networks of up to 6.3 million vertices and 15 million arcs (on weaker GPUs).
Document type :
Conference papers
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download

https://hal.inria.fr/hal-01760642
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, April 6, 2018 - 3:08:05 PM
Last modification on : Tuesday, January 11, 2022 - 3:40:04 PM

File

440117_1_En_5_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Mohsen Safari, Ali Ebnenasir. Locality-Based Relaxation: An Efficient Method for GPU-Based Computation of Shortest Paths. 2nd International Conference on Topics in Theoretical Computer Science (TTCS), Sep 2017, Tehran, Iran. pp.41-56, ⟨10.1007/978-3-319-68953-1_5⟩. ⟨hal-01760642⟩

Share

Metrics

Record views

62

Files downloads

214