Welcome to the ADMT Publication Server

PARAGON: Parallel Architecture-Aware Graph Partition Refinement Algorithm

DocUID: 2016-001 Full Text: PDF

Author: Angen Zheng, Alexandros Labrinidis, Patrick H. Pisciuneri, Panos K. Chrysanthis, Peyman Givi

Abstract: With the explosion of large, dynamic graph datasets from various fields, graph partitioning and repartitioning are becoming more and more critical to the performance of many graph-based Big Data applications, such as social analysis, web search, and recommender systems. However, well-studied graph (re)partitioners usually assume a homogeneous and contention-free computing environment, which contradicts the increasing communication heterogeneity and shared resource contention in modern, multicore high performance computing clusters. To bridge this gap, we introduce PARAGON, a parallel architecture-aware graph partition refinement algorithm, which mitigates the mismatch by modifying a given decomposition according to the nonuniform network communication costs and the contentiousness of the underlying hardware topology. To further reduce the overhead of the refinement, we also make PARAGON itself architecture-aware. Our experiments with a diverse collection of datasets showed that on average PARAGON improved the quality of graph decompositions computed by the de-facto standard (hashing partitioning) and two state-of-the-art streaming graph partitioning heuristics (deterministic greedy and linear deterministic greedy) by 43%, 17%, and 36%, respectively. Furthermore, our experiments with an MPI implementation of Breadth First Search and Single Source Shortest Path showed that, in comparison to the state-of-the-art streaming and multi-level graph (re)partitioners, PARAGON achieved up to 5.9x speedups. Finally, we demonstrated the scalability of PARAGON by scaling it up to a graph with 3.6 billion edges using only 3 machines (60 physical cores).

Keywords: Heterogeneity, Contention, Graph Partitioning

Published In: 19th International Conference on Extending Database Technology

Pages: pp. 365-376

Year Published: 2016

Project: 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, Patrick H. Pisciuneri, Panos K. Chrysanthis, and Peyman Givi. PARAGON: Parallel Architecture-Aware Graph Partition Refinement Algorithm. 19th International Conference on Extending Database Technology. pp. 365-376. 2016.

Similar Publications: