Paper Info
Title
PHAST: Hardware-Accelerated Shortest Path Trees
Abstract
We present a novel algorithm to solve the nonnegative single-source shortest path problem on road networks and other graphs with low highway dimension. After a quick preprocessing phase, we can compute all distances from a given source in the graph with essentially a linear sweep over all vertices. Because this sweep is independent of the source, we are able to reorder vertices in advance to exploit locality. Moreover, our algorithm takes advantage of features of modern CPU architectures, such as SSE and multi-core. Compared to Dijkstra's algorithm, our method needs fewer operations, has better locality, and is better able to exploit parallelism at multi-core and instruction levels. We gain additional speedup when implementing our algorithm on a GPU, where our algorithm is up to three orders of magnitude faster than Dijkstra's algorithm on a high-end CPU. This makes applications based on all-pairs shortest-paths practical for continental-sized road networks. Several algorithms, such as computing the graph diameter, exact arc flags, or centrality measures (exact reaches or betweenness), can be greatly accelerated by our method.
Year
DOI
Venue
2013
10.1109/IPDPS.2011.89
Journal of Parallel and Distributed Computing
Keywords
DocType
Volume
road network,modern cpu architecture,graph diameter,exact reach,linear sweep,continental-sized road network,hardware-accelerated shortest path trees,exact arc flag,novel algorithm,high-end cpu,better locality,graph theory,indexing terms,dijkstra algorithm,instruction sets,dijkstra s algorithm,all pairs shortest path,parallel processing,shortest path,registers,shortest path tree,hardware accelerator
Journal
73
Issue
ISSN
Citations 
7
0743-7315
57
PageRank 
References 
Authors
1.92
30
4
Name
Order
Citations
PageRank
Daniel Delling12049108.90
Andrew V. Goldberg25883676.30
Andreas Nowatzyk355290.34
Renato F. Werneck4174384.33