Advanced shortest paths algorithms on a massively-multithreaded architecture

Joseph R. Crobak, Jonathan W. Berry, Kamesh Madduri, David A. Bader

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

22 Scopus citations

Abstract

We present a study of multithreaded implementations of Thorup 's algorithm, for solving the Single Source Shortest Path (SSSP) problem for undirected graphs. Our implementations leverage the fledgling Multithreaded Graph Library (MTGL) to perform operations such as finding connected components and extracting induced subgraphs. To achieve good parallel performance from this algorithm, we deviate from several theoretically optimal algorithmic steps. In this paper, we present simplifications that perform better in practice, and we describe details of the multithreaded implementation that were, necessary for scalability, We study synthetic graphs that model unstructured networks, such as social networks and economic transaction networks. Most of the recent progress in shortest path algorithms relies on structure that these networks do not have. In this work, we take a step back and explore the synergy between an elegant theoretical algorithm and an elegant computer architecture. Finally, we conclude with a prediction that this work will become relevant to shortest path computation on structured networks.

Original languageEnglish (US)
Title of host publicationProceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM
DOIs
StatePublished - 2007
Externally publishedYes
Event21st International Parallel and Distributed Processing Symposium, IPDPS 2007 - Long Beach, CA, United States
Duration: Mar 26 2007Mar 30 2007

Publication series

NameProceedings - 21st International Parallel and Distributed Processing Symposium, IPDPS 2007; Abstracts and CD-ROM

Other

Other21st International Parallel and Distributed Processing Symposium, IPDPS 2007
Country/TerritoryUnited States
CityLong Beach, CA
Period3/26/073/30/07

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Advanced shortest paths algorithms on a massively-multithreaded architecture'. Together they form a unique fingerprint.

Cite this