Welcome to the ADMT Publication Server

ARGO: Architecture-Aware Graph Partitioning

DocUID: 2016-008 Full Text: PDF

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

Abstract: The increasing popularity and ubiquity of various large graph datasets has caused renewed interest for graph partitioning. Existing graph partitioners either scale poorly against large graphs or disregard the impact of the underlying hardware topology. A few solutions have shown that the nonuniform network communication costs may affect the performance greatly. However, none of them considers the impact of resource contention on the memory subsystems (e.g., LLC and Memory Controller) of modern multicore clusters. They all neglect the fact that the bandwidth of modern high-speed networks (e.g., Infiniband) has become comparable to that of the memory subsystems. In this paper, we provide an in-depth analysis, both theoretically and experimentally, on the contention issue for distributed workloads. We found that the slowdown caused by the contention can be as high as 11x. We then design an architecture-aware graph partitioner, ARGO , to allow the full use of all cores of multicore machines without suffering from either the contention or the communication heterogeneity issue. Our experimental study showed (1) the effectiveness of ARGO , achieving up to 12x speedups on three classic workloads: Breadth First Search, Single Source Shortest Path, and PageRank; and (2) the scalability of ARGO in terms of both graph size and the number of partitions on two billion-edge real-world graphs.

Keywords: Heterogeneity; Contention; Multicore; Graph Partitioning; Distributed Graph Processing

Published In: 2016 IEEE International Conference on Big Data

Pages: 284-293

Year Published: 2016

Project: Planar,  Paragon,  ARGO Subject Area: Graph Data Management

Publication Type: Conference Paper

Sponsor: NSF CBET-1609120, NSF CBET-1250171

Citation:Text Latex BibTex XML Angen Zheng, Alexandros Labrinidis, Panos K. Chrysanthis, and Jack Lange. ARGO: Architecture-Aware Graph Partitioning. 2016 IEEE International Conference on Big Data. 284-293. 2016.

Similar Publications: