Welcome to the ADMT Publication Server

Planar: Parallel Lightweight Architecture-Aware Adaptive Graph Repartitioning

DocUID: 2016-002 Full Text: PDF

Author: Angen Zheng, Alexandros Labrinidis, Panos K. Chrysanthis

Abstract: Graph partitioning is an essential preprocessing step in distributed graph computation and scientific simulations. Existing well-studied graph partitioners are designed for static graphs, but real-world graphs, such as social networks and Web networks, keep changing dynamically. In fact, the communication and computation patterns of some graph algorithms may vary significantly, even across their different computation phases. This means that the optimal partitioning changes over time, requiring the graph to be repartitioned periodically to maintain good performance. However, the state-of-the-art graph (re)partitioners are known for their poor scalability against massive graphs. Furthermore, they usually assume a homogeneous and contention-free computing environment, which is no longer true in modern high performance computing infrastructures. In this paper, we introduce Planar, a parallel lightweight graph repartitioner, which does not require full knowledge of the graph and incrementally adapts the partitioning to changes while considering the heterogeneity and contentiousness of the underlying computing infrastructure. Using a diverse collection of datasets, we showed that, in comparison with the de-facto standard and two state-of-the-art streaming graph partitioning heuristics, Planar improved the quality of graph partitionings by up to 68%, 46%, and 69%, respectively. Furthermore, our experiments with an MPI implementation of Breadth First Search and Single Source Shortest Path showed that Planar achieved up to 10x speedups against the state-of-the-art streaming and multi-level graph (re)partitioners. Finally, we scaled Planar up to a graph with 3.6 billion edges.

Keywords: Heterogeneity, Contention, Graph Partitioning

Published In: 32nd IEEE International Conference on Data Engineering

Pages: pp. 121-132

Year Published: 2016

Project: Planar,  Paragon,  AragonLB Subject Area: Scientific Data Management, Graph Data Management

Publication Type: Conference Paper

Sponsor: NSF OIA-1028162, NSF CBET-1250171

Citation:Text Latex BibTex XML Angen Zheng, Alexandros Labrinidis, and Panos K. Chrysanthis. Planar: Parallel Lightweight Architecture-Aware Adaptive Graph Repartitioning. 32nd IEEE International Conference on Data Engineering. pp. 121-132. 2016.