GraphService: Topology-aware Constructor for Large-scale Graph Applications

Citations Over TimeTop 10% of 2024 papers

Abstract

Graph-based services are becoming integrated into everyday life through graph applications and graph learning systems. While traditional graph processing approaches boast excellent throughput with millisecond-level processing time, the construction phase before executing kernel graph operators (e.g., breadth-first search, single-source shortest path) can take up to tens of hours, severely impacting the quality of graph service. Is it feasible to develop a fast graph constructor that can complete the construction process within minutes, or even seconds? This article aims to answer this question. We present GraphService , a flexible and efficient graph constructor for fast graph applications. To facilitate graph applications with better service, we equip GraphService with a hierarchy-aware graph partitioner based on communication topology as well as a graph topology-aware compression by exploiting a huge number of identical-degree vertices within graph topology. Our evaluation, performed on a range of graph operations and datasets, shows that GraphService significantly reduces communication cost by three orders of magnitude to construct a graph. Furthermore, we tailor GraphService for downstream graph tasks and deploy it on a production supercomputer using 79,024 computing nodes, achieving a remarkable graph processing throughput that outperforms the top-ranked supercomputer on the latest Graph500 list, with construction time reduced by orders of magnitude.

Related Papers

• → A Multilevel Parallelization Framework for High-Order Stencil Computations(2009)51 cited
• → Performance Optimization of 3D Lattice Boltzmann Flow Solver on a GPU(2017)41 cited
• → Hierarchical parallelization and optimization of high-order stencil computations on multicore clusters(2012)21 cited
• → Exploiting hierarchical parallelisms for molecular dynamics simulation on multicore clusters(2011)10 cited
• → Parallel computation for Boltzmann equation simulation with Dynamic Discrete Ordinate Method (DDOM)(2011)2 cited