%0 Conference Proceedings
%T Locality-Based Relaxation: An Efficient Method for GPU-Based Computation of Shortest Paths
%+ University of Zanjan (ZNU)
%+ Michigan Technological University (MTU)
%A Safari, Mohsen
%A Ebnenasir, Ali
%Z Part 2: Algorithms and Complexity
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 2nd International Conference on Topics in Theoretical Computer Science (TTCS)
%C Tehran, Iran
%Y Mohammad Reza Mousavi
%Y Jiří Sgall
%I Springer International Publishing
%3 Topics in Theoretical Computer Science
%V LNCS-10608
%P 41-56
%8 2017-09-12
%D 2017
%R 10.1007/978-3-319-68953-1_5
%Z Computer Science [cs]Conference papers
%X 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).
%G English
%Z TC 1
%Z WG 1.8
%2 https://inria.hal.science/hal-01760642/document
%2 https://inria.hal.science/hal-01760642/file/440117_1_En_5_Chapter.pdf
%L hal-01760642
%U https://inria.hal.science/hal-01760642
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-8
%~ IFIP-TTCS
%~ IFIP-LNCS-10608