Fast approximate distance queries in unweighted graphs using bounded asynchrony

Adam Fidel, Francisco Coral Sabido, Colton Riedel, Nancy Marie Amato, Lawrence Rauchwerger

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

Abstract

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.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Revised Papers
EditorsChen Ding, John Criswell, Peng Wu
PublisherSpringer-Verlag
Pages40-54
Number of pages15
ISBN (Print)9783319527086
DOIs
StatePublished - Jan 1 2017
Externally publishedYes
Event29th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2016 - Rochester, United States
Duration: Sep 28 2016Sep 30 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10136 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference29th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2016
CountryUnited States
CityRochester
Period9/28/169/30/16

Fingerprint

Query
Graph in graph theory
Synchronization
Asynchronous Algorithms
Global Synchronization
Breadth
Parallel algorithms
Parallel Algorithms
High Performance
Paradigm
Model

Keywords

  • Approximate algorithms
  • Asynchronous
  • Breadth-first search
  • Distance query
  • Distributed memory
  • Parallel graph algorithms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Fidel, A., Sabido, F. C., Riedel, C., Amato, N. M., & Rauchwerger, L. (2017). Fast approximate distance queries in unweighted graphs using bounded asynchrony. In C. Ding, J. Criswell, & P. Wu (Eds.), Languages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Revised Papers (pp. 40-54). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10136 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-52709-3_4

Fast approximate distance queries in unweighted graphs using bounded asynchrony. / Fidel, Adam; Sabido, Francisco Coral; Riedel, Colton; Amato, Nancy Marie; Rauchwerger, Lawrence.

Languages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Revised Papers. ed. / Chen Ding; John Criswell; Peng Wu. Springer-Verlag, 2017. p. 40-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10136 LNCS).

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

Fidel, A, Sabido, FC, Riedel, C, Amato, NM & Rauchwerger, L 2017, Fast approximate distance queries in unweighted graphs using bounded asynchrony. in C Ding, J Criswell & P Wu (eds), Languages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Revised Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10136 LNCS, Springer-Verlag, pp. 40-54, 29th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2016, Rochester, United States, 9/28/16. https://doi.org/10.1007/978-3-319-52709-3_4
Fidel A, Sabido FC, Riedel C, Amato NM, Rauchwerger L. Fast approximate distance queries in unweighted graphs using bounded asynchrony. In Ding C, Criswell J, Wu P, editors, Languages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Revised Papers. Springer-Verlag. 2017. p. 40-54. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-52709-3_4
Fidel, Adam ; Sabido, Francisco Coral ; Riedel, Colton ; Amato, Nancy Marie ; Rauchwerger, Lawrence. / Fast approximate distance queries in unweighted graphs using bounded asynchrony. Languages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Revised Papers. editor / Chen Ding ; John Criswell ; Peng Wu. Springer-Verlag, 2017. pp. 40-54 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{db59bb6d1c46454695346751c4d0c251,
title = "Fast approximate distance queries in unweighted graphs using bounded asynchrony",
abstract = "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.",
keywords = "Approximate algorithms, Asynchronous, Breadth-first search, Distance query, Distributed memory, Parallel graph algorithms",
author = "Adam Fidel and Sabido, {Francisco Coral} and Colton Riedel and Amato, {Nancy Marie} and Lawrence Rauchwerger",
year = "2017",
month = "1",
day = "1",
doi = "10.1007/978-3-319-52709-3_4",
language = "English (US)",
isbn = "9783319527086",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "40--54",
editor = "Chen Ding and John Criswell and Peng Wu",
booktitle = "Languages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Revised Papers",

}

TY - GEN

T1 - Fast approximate distance queries in unweighted graphs using bounded asynchrony

AU - Fidel, Adam

AU - Sabido, Francisco Coral

AU - Riedel, Colton

AU - Amato, Nancy Marie

AU - Rauchwerger, Lawrence

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

KW - Approximate algorithms

KW - Asynchronous

KW - Breadth-first search

KW - Distance query

KW - Distributed memory

KW - Parallel graph algorithms

UR - http://www.scopus.com/inward/record.url?scp=85011422305&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85011422305&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-52709-3_4

DO - 10.1007/978-3-319-52709-3_4

M3 - Conference contribution

AN - SCOPUS:85011422305

SN - 9783319527086

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 40

EP - 54

BT - Languages and Compilers for Parallel Computing - 29th International Workshop, LCPC 2016, Revised Papers

A2 - Ding, Chen

A2 - Criswell, John

A2 - Wu, Peng

PB - Springer-Verlag

ER -