Fast Approximate Distance Queries in Unweighted Graphs Using Bounded Asynchrony
Conference Paper
-
- Overview
-
- Research
-
- Identity
-
- Additional Document Info
-
- Other
-
- View All
-
Overview
abstract
-
© Springer International Publishing AG 2017. We introduce a new parallel algorithm for approximate breadth-first ordering of an unweighted graph by using bounded asynchrony to parametrically control both the performance and error of the algorithm. This work is based on the k-level asynchronous (KLA) paradigm that trades expensive global synchronizations in the levelsynchronous model for local synchronizations in the asynchronous model, which may result in redundant work. Instead of correcting errors introduced by asynchrony and redoing work as in KLA, in this work we control the amount of work that is redone and thus the amount of error allowed, leading to higher performance at the expense of a loss of precision. Results of an implementation of this algorithm are presented on up to 32,768 cores, showing 2.27x improvement over the exact KLA algorithm and 3.8x improvement over the level-synchronous version with minimal error on several graph inputs.
name of conference
-
Languages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Rochester, NY, USA, September 28-30, 2016, Revised Papers
published proceedings
-
LANGUAGES AND COMPILERS FOR PARALLEL COMPUTING, LCPC 2016
author list (cited authors)
-
Fidel, A., Sabido, F. C., Riedel, C., Amato, N. M., & Rauchwerger, L
citation count
complete list of authors
-
Fidel, Adam||Sabido, Francisco Coral||Riedel, Colton||Amato, Nancy M||Rauchwerger, Lawrence
editor list (cited editors)
-
Ding, C., Criswell, J., & Wu, P.
publication date
publisher
published in
Research
keywords
-
Approximate Algorithms
-
Asynchronous
-
Breadth-first Search
-
Distance Query
-
Distributed Memory
-
Parallel Graph Algorithms
Identity
Digital Object Identifier (DOI)
International Standard Book Number (ISBN) 13
Additional Document Info
start page
end page
volume
Other
URL
-
https://doi.org/10.1007/978-3-319-52709-3