A hierarchical approach to reducing communication in parallel graph algorithms

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

Abstract

Large-scale graph computing has become critical due to the ever-increasing size of data. However, distributed graph computations are limited in their scalability and performance due to the heavy communication inherent in such computations. This is exacerbated in scale-free networks, such as social and web graphs, which contain hub vertices that have large degrees and therefore send a large number of messages over the network. Furthermore, many graph algorithms and computations send the same data to each of the neighbors of a vertex. Our proposed approach recognizes this, and reduces communication performed by the algorithm without change to user-code, through a hierarchical machine model imposed upon the input graph. The hierarchical model takes advantage of locale information of the neighboring vertices to reduce communication, both in message volume and total number of bytes sent. It is also able to better exploit the machine hierarchy to further reduce the communication costs, by aggregating traffic between different levels of the machine hierarchy. Results of an implementation in the STAPL GL shows improved scalability and performance over the traditional level-synchronous approach, with 2.5 × - 8× improvement for a variety of graph algorithms at 12, 000+ cores.

Original languageEnglish (US)
Title of host publication20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015 - Proceedings
PublisherAssociation for Computing Machinery
Pages285-286
Number of pages2
ISBN (Electronic)9781450332057
DOIs
StatePublished - Jan 24 2015
Externally publishedYes
Event20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015 - San Francisco, United States
Duration: Feb 7 2015Feb 11 2015

Publication series

NameProceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP
Volume2015-January

Conference

Conference20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015
CountryUnited States
CitySan Francisco
Period2/7/152/11/15

Keywords

  • Big Data
  • Distributed computing
  • Graph analytics
  • Parallel graph processing

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'A hierarchical approach to reducing communication in parallel graph algorithms'. Together they form a unique fingerprint.

  • Cite this

    Harshvardhan, Amato, N. M., & Rauchwerger, L. (2015). A hierarchical approach to reducing communication in parallel graph algorithms. In 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2015 - Proceedings (pp. 285-286). (Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP; Vol. 2015-January). Association for Computing Machinery. https://doi.org/10.1145/2688500.2700994