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: ARGO, Paragon, Planar Subject Area: Graph Data Management
Publication Type: Conference Paper
Sponsor: NSF CBET-1250171, NSF CBET-1609120
Similar Publications: