MST: Topology-Aware Message Aggregation for Exascale Graph Processing of Traversal-Centric Algorithms

Citations Over TimeTop 17% of 2024 papers

Abstract

This article presents MST, a communication-efficient message library for fast graph traversal on exascale clusters. The key idea is to follow the multi-level network topology to perform topology-aware message aggregation, where small messages are gathered and scattered at each level of domain. To facilitate message aggregation, we equip MST with flexible buffer management including active buffer switching and dynamic buffer expansion. We implement MST on the newest-generation Tianhe supercomputer and evaluated its performance using various traversal-centric algorithms on both synthetic trillion-scale graphs and real-world big graphs. The results show that MST-based graph traversal is orders of magnitude faster than that based on Active Messages Library (AML). For the Graph500-BFS benchmark, MST-based Tianhe (with 77.2 K nodes) outperforms the Fugaku supercomputer (with 148.5 K nodes) by 18.53%, while Fugaku is ranked No. 1 in the latest Graph500-BFS ranking (June 2023). MST also greatly improves graph processing performance on other commercial large-scale computing systems at the National Supercomputing Center in Changsha (NSCC) and WuzhenLight.

Related Papers

• → Basic Definitions and Network Traversal Algorithms(2013)8 cited
• → Exploring graph traversal algorithms in graph-based molecular generation(2021)1 cited
• → Topological Sort and Graph Traversals(2016)2 cited
• → Exploring graph traversal algorithms in graph-based molecular generation(2021)
• → Exploring graph traversal algorithms in graph-based molecular generation(2021)