A hierarchical approach to reducing communication in parallel graph algorithms

Harshvardhan; Nancy M. Amato; Lawrence Rauchwerger

doi:10.1145/2688500.2700994

A hierarchical approach to reducing communication in parallel graph algorithms

Harshvardhan, Nancy M. Amato, Lawrence Rauchwerger

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP 2015
Publisher	Association for Computing Machinery (ACM)
Pages	285-286
Number of pages	2
ISBN (Print)	9781450332057
DOIs	https://doi.org/10.1145/2688500.2700994
State	Published - 2015
Externally published	Yes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUS-C1-016-04
Acknowledgements: We would like to thank our anonymous reviewers. This research is supported in part by NSF awards CCF 0702765, CNS-0551685, CCF-0833199, CCF-1439145, CCF-1423111, CCF-0830753, IIS-0917266, by DOE awards DE-AC02-06CH11357, DE-NA0002376, B575363, by Samsung, IBM, Intel, and by Award KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST). This research used resources of the National Energy
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

Access to Document

10.1145/2688500.2700994

Cite this

@inproceedings{05dcb050cf624d51b23c64c275e6b863,

title = "A hierarchical approach to reducing communication in parallel graph algorithms",

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.",

author = "Harshvardhan and Amato, {Nancy M.} and Lawrence Rauchwerger",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledged KAUST grant number(s): KUS-C1-016-04 Acknowledgements: We would like to thank our anonymous reviewers. This research is supported in part by NSF awards CCF 0702765, CNS-0551685, CCF-0833199, CCF-1439145, CCF-1423111, CCF-0830753, IIS-0917266, by DOE awards DE-AC02-06CH11357, DE-NA0002376, B575363, by Samsung, IBM, Intel, and by Award KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST). This research used resources of the National Energy This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2015",

doi = "10.1145/2688500.2700994",

language = "English (US)",

isbn = "9781450332057",

pages = "285--286",

booktitle = "Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP 2015",

publisher = "Association for Computing Machinery (ACM)",

address = "United States",

}

A hierarchical approach to reducing communication in parallel graph algorithms. / Harshvardhan; Amato, Nancy M.; Rauchwerger, Lawrence.
Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP 2015. Association for Computing Machinery (ACM), 2015. p. 285-286.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A hierarchical approach to reducing communication in parallel graph algorithms

AU - Harshvardhan,

AU - Amato, Nancy M.

AU - Rauchwerger, Lawrence

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledged KAUST grant number(s): KUS-C1-016-04 Acknowledgements: We would like to thank our anonymous reviewers. This research is supported in part by NSF awards CCF 0702765, CNS-0551685, CCF-0833199, CCF-1439145, CCF-1423111, CCF-0830753, IIS-0917266, by DOE awards DE-AC02-06CH11357, DE-NA0002376, B575363, by Samsung, IBM, Intel, and by Award KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST). This research used resources of the National Energy This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2015

Y1 - 2015

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

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

UR - http://hdl.handle.net/10754/597283

UR - http://dl.acm.org/citation.cfm?doid=2688500.2700994

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

U2 - 10.1145/2688500.2700994

DO - 10.1145/2688500.2700994

M3 - Conference contribution

SN - 9781450332057

SP - 285

EP - 286

BT - Proceedings of the 20th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - PPoPP 2015

PB - Association for Computing Machinery (ACM)

ER -

A hierarchical approach to reducing communication in parallel graph algorithms

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this