DSMR: A parallel algorithm for Single-Source Shortest Path problem

Saeed Maleki, Donald Nguyen, Andrew Lenharth, María Garzarán, David Padua, Keshav Pingali

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The Single Source Shortest Path (SSSP) problem consists in finding the shortest paths from a vertex (the source vertex) to all other vertices in a graph. SSSP has numerous applications. For some algorithms and applications, it is useful to solve the SSSP problem in parallel. This is the case of Betweenness Centrality which solves the SSSP problem for multiple source vertices in large graphs. In this paper, we introduce the Dijkstra Strip Mined Relaxation (DSMR) algorithm, an efficient parallel SSSP algorithm for shared and distributed-memory systems. We also introduce a set of preprocessing optimization techniques that significantly reduce the communication overhead without increasing the total amount of work dramatically. Our results show that, DSMR is faster than the best previous algorithm, parallel Δ-Stepping, by up-to 7:38×.

Original languageEnglish (US)
Title of host publicationProceedings of the 2016 International Conference on Supercomputing, ICS 2016
PublisherAssociation for Computing Machinery
ISBN (Electronic)9781450343619
DOIs
StatePublished - Jun 1 2016
Event30th International Conference on Supercomputing, ICS 2016 - Istanbul, Turkey
Duration: Jun 1 2016Jun 3 2016

Publication series

NameProceedings of the International Conference on Supercomputing
Volume01-03-June-2016

Other

Other30th International Conference on Supercomputing, ICS 2016
Country/TerritoryTurkey
CityIstanbul
Period6/1/166/3/16

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'DSMR: A parallel algorithm for Single-Source Shortest Path problem'. Together they form a unique fingerprint.

Cite this