TY - GEN
T1 - To 4,000 Compute Nodes and Beyond: Network-aware Vertex Placement in Large-scale Graph Processing Systems
AU - Awara, Karim
AU - Jamjoom, Hani
AU - Kalnis, Panos
N1 - KAUST Repository Item: Exported on 2021-07-13
PY - 2013/8/27
Y1 - 2013/8/27
N2 - The explosive growth of "big data" is giving rise to a new breed of large scale graph systems, such as Pregel. This poster describes our ongoing work in characterizing and minimizing the communication cost of Bulk Synchronous Parallel (BSP) graph mining systems, like Pregel, when scaling to 4,096 compute nodes. Existing implementations generally assume a fixed communication cost. This is sufficient in small deployments as the BSP programming model (i.e., overlapping computation and communication) masks small variations in the underlying network. In large scale deployments, such variations can dominate the overall runtime characteristics. In this poster, we first quantify the impact of network communication on the total compute time of a Pregel system. We then propose an efficient vertex placement strategy that subsamples highly connected vertices and applies the Reverse Cuthill-McKee (RCM) algorithm to efficiently partition the input graph and place partitions closer to each other based on their expected communication patterns. We finally describe a vertex replication strategy to further reduce communication overhead. © 2013 Authors.
AB - The explosive growth of "big data" is giving rise to a new breed of large scale graph systems, such as Pregel. This poster describes our ongoing work in characterizing and minimizing the communication cost of Bulk Synchronous Parallel (BSP) graph mining systems, like Pregel, when scaling to 4,096 compute nodes. Existing implementations generally assume a fixed communication cost. This is sufficient in small deployments as the BSP programming model (i.e., overlapping computation and communication) masks small variations in the underlying network. In large scale deployments, such variations can dominate the overall runtime characteristics. In this poster, we first quantify the impact of network communication on the total compute time of a Pregel system. We then propose an efficient vertex placement strategy that subsamples highly connected vertices and applies the Reverse Cuthill-McKee (RCM) algorithm to efficiently partition the input graph and place partitions closer to each other based on their expected communication patterns. We finally describe a vertex replication strategy to further reduce communication overhead. © 2013 Authors.
UR - http://hdl.handle.net/10754/669946
UR - https://dl.acm.org/doi/10.1145/2534169.2491726
UR - http://www.scopus.com/inward/record.url?scp=84891585872&partnerID=8YFLogxK
U2 - 10.1145/2534169.2491726
DO - 10.1145/2534169.2491726
M3 - Conference contribution
SN - 9781450320566
SP - 501
EP - 502
BT - ACM SIGCOMM COMPUTER COMMUNICATION REVIEW
PB - Association for Computing Machinery (ACM)
ER -