MST: Topology-Aware Message Aggregation for Exascale Graph Processing of Traversal-Centric Algorithms
ACM Transactions on Architecture and Code Optimization · 31.12.2024 · 21 (4) · 1-22
DOI: 10.1145/3676846 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Architecture and Code Optimization, online erschienen am 19.11.2024. Verfasst von Xinbiao Gan und 9 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref) und nennt 42 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Gan, X., Li, T., Xiong, F., Yang, B., Chen, X., Gong, C., Li, S., Lu, K., Li, Q., & Zhang, Y. (2024). MST: Topology-Aware Message Aggregation for Exascale Graph Processing of Traversal-Centric Algorithms. ACM Transactions on Architecture and Code Optimization, 21(4), 1-22. https://doi.org/10.1145/3676846
Vancouver
Gan X, Li T, Xiong F, Yang B, Chen X, Gong C, et al. MST: Topology-Aware Message Aggregation for Exascale Graph Processing of Traversal-Centric Algorithms. ACM Transactions on Architecture and Code Optimization. 2024;21(4):1-22. doi:10.1145/3676846
BibTeX
@article{Gan2024,
author = {Gan, Xinbiao and Li, Tiejun and Xiong, Feng and Yang, Bo and Chen, Xinhai and Gong, Chunye and Li, Shijie and Lu, Kai and Li, Qiao and Zhang, Yiming},
title = {MST: Topology-Aware Message Aggregation for Exascale Graph Processing of Traversal-Centric Algorithms},
journal = {ACM Transactions on Architecture and Code Optimization},
year = {2024},
volume = {21},
number = {4},
pages = {1--22},
doi = {10.1145/3676846}
}
EUVIMED