KLA: A new algorithmic paradigm for parallel graph computations

Harshvardhan, Adam Fidel, Nancy M. Amato, Lawrence Rauchwerger

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

Abstract

This paper proposes a new algorithmic paradigm - k-level asynchronous (KLA) - that bridges level-synchronous and asynchronous paradigms for processing graphs. The KLA paradigm enables the level of asynchrony in parallel graph algorithms to be parametrically varied from none (level-synchronous) to full (asynchronous). The motivation is to improve execution times through an appropriate trade-off between the use of fewer, but more expensive global synchronizations, as in level-synchronous algorithms, and more, but less expensive local synchronizations (and perhaps also redundant work), as in asynchronous algorithms. We show how common patterns in graph algorithms can be expressed in the KLA pardigm and provide techniques for determining k, the number of asynchronous steps allowed between global synchronizations. Results of an implementation of KLA in the STAPL Graph Library show excellent scalability on up to 96K cores and improvements of 10x or more over level-synchronous and asynchronous versions for graph algorithms such as breadth-first search, PageRank, k-core decomposition and others on certain classes of real-world graphs.

Original languageEnglish (US)
Title of host publicationPACT 2014 - Proceedings of the 23rd International Conference on Parallel Architectures and Compilation Techniques
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages27-38
Number of pages12
ISBN (Print)9781450328098
DOIs
StatePublished - Jan 1 2014
Externally publishedYes
Event23rd International Conference on Parallel Architectures and Compilation Techniques, PACT 2014 - Edmonton, AB, Canada
Duration: Aug 24 2014Aug 27 2014

Publication series

NameParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
ISSN (Print)1089-795X

Other

Other23rd International Conference on Parallel Architectures and Compilation Techniques, PACT 2014
CountryCanada
CityEdmonton, AB
Period8/24/148/27/14

Keywords

  • asynchronous graph algorithms
  • big data
  • distributed computing
  • graph analytics
  • parallel algorithms

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'KLA: A new algorithmic paradigm for parallel graph computations'. Together they form a unique fingerprint.

  • Cite this

    Harshvardhan, Fidel, A., Amato, N. M., & Rauchwerger, L. (2014). KLA: A new algorithmic paradigm for parallel graph computations. In PACT 2014 - Proceedings of the 23rd International Conference on Parallel Architectures and Compilation Techniques (pp. 27-38). (Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1145/2628071.2628091