{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T14:49:00Z","timestamp":1779202140834,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T00:00:00Z","timestamp":1731974400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>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.\u00a01 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.<\/jats:p>","DOI":"10.1145\/3676846","type":"journal-article","created":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T11:20:13Z","timestamp":1720005613000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["MST: Topology-Aware Message Aggregation for Exascale Graph Processing of Traversal-Centric Algorithms"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3622-1772","authenticated-orcid":false,"given":"Xinbiao","family":"Gan","sequence":"first","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9486-420X","authenticated-orcid":false,"given":"Tiejun","family":"Li","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-7057-7231","authenticated-orcid":false,"given":"Feng","family":"Xiong","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9035-1538","authenticated-orcid":false,"given":"Bo","family":"Yang","sequence":"additional","affiliation":[{"name":"School of Computer, National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2931-4893","authenticated-orcid":false,"given":"Xinhai","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0349-1100","authenticated-orcid":false,"given":"Chunye","family":"Gong","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0529-0057","authenticated-orcid":false,"given":"Shijie","family":"Li","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4907-306X","authenticated-orcid":false,"given":"Kai","family":"Lu","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4579-4268","authenticated-orcid":false,"given":"Qiao","family":"Li","sequence":"additional","affiliation":[{"name":"Xiamen University, Xiamen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6450-8485","authenticated-orcid":false,"given":"Yiming","family":"Zhang","sequence":"additional","affiliation":[{"name":"Xiamen University, Xiamen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,19]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"2022. National supercomputing Center in Changsha. Retrieved from http:\/\/nscc.hnu.edu.cn\/info\/1013\/1011.htm"},{"key":"e_1_3_3_3_2","unstructured":"2023. Retrieved from https:\/\/en.wikipedia.org\/wiki\/Message_Passing_Interface. (2023)."},{"key":"e_1_3_3_4_2","unstructured":"2023. Retrieved from https:\/\/en.wikipedia.org\/wiki\/SPMD. (2023)."},{"key":"e_1_3_3_5_2","unstructured":"2023. Retrieved from https:\/\/github.com\/anonymous-nicer\/mst\/blob\/main\/graph100.png. (2023)."},{"key":"e_1_3_3_6_2","unstructured":"2023. Retrieved from https:\/\/github.com\/graph500\/graph500\/tree\/newreference\/aml. (2023)."},{"key":"e_1_3_3_7_2","unstructured":"2023. Retrieved from https:\/\/graph500.org\/. (2023)."},{"key":"e_1_3_3_8_2","unstructured":"2023. Retrieved from https:\/\/law.di.unimi.it\/webdata\/eu-2015\/. (2023)."},{"key":"e_1_3_3_9_2","unstructured":"2023. Retrieved from https:\/\/law.di.unimi.it\/webdata\/twitter-2010\/. (2023)."},{"key":"e_1_3_3_10_2","unstructured":"2023. Retrieved from https:\/\/lemurproject.org\/clueweb12\/. (2023)."},{"key":"e_1_3_3_11_2","unstructured":"2023. Retrieved from https:\/\/www.laitimes.com\/en\/article\/85ga_86m5.html. (2023)."},{"key":"e_1_3_3_12_2","unstructured":"2023. Retrieved from https:\/\/www.theregister.com\/2021\/04\/09\/biden_china_supercomputers\/. (2023)."},{"key":"e_1_3_3_13_2","unstructured":"2023. Retrieved from https:\/\/www.top500.org\/resources\/top-systems\/tianhe-2-milkyway-2-national-university-of-defense\/. (2023)."},{"key":"e_1_3_3_14_2","volume-title":"Proceedings of the HiPC 2012","author":"Beamer S.","year":"2012","unstructured":"S. Beamer, K. Asanovic, and D. Patterson. 2012. Direction-optimizing breadth-first search. In Proceedings of the HiPC 2012."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2016.2634535"},{"key":"e_1_3_3_16_2","first-page":"1","article-title":"Powerlyra: Differentiated graph computation and partitioning on skewed graphs","author":"Chen R.","year":"2015","unstructured":"R. Chen, J. Shi, Y. Chen, and H. Chen. 2015. Powerlyra: Differentiated graph computation and partitioning on skewed graphs. European Conference on Computer Systems (2015), 1\u201315.","journal-title":"European Conference on Computer Systems"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00107"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.14778\/2983200.2983202"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.14778\/3476311.3476369"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3100785"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3100785"},{"key":"e_1_3_3_22_2","first-page":"2046","volume-title":"Proceedings of the 2022 IEEE 38th International Conference on Data Engineering","author":"Gan Xinbiao","year":"2022","unstructured":"Xinbiao Gan, Yiming Zhang, Ruigeng Zeng, Jie Liu, Ruibo Wang, Tiejun Li, Li Chen, and Kai Lu. 2022. Xtree: Traversal-based partitioning for extreme-scale graph processing on supercomputers. In Proceedings of the 2022 IEEE 38th International Conference on Data Engineering. IEEE, 2046\u20132059."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2018.05.006"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178506"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-016-1779-7"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/2904483.2904486"},{"key":"e_1_3_3_27_2","volume-title":"Proceedings of the 2016 USENIX Annual Technical Conference","author":"Ju Xiaoen","year":"2016","unstructured":"Xiaoen Ju, Dan Williams, Hani Jamjoom, and Kang G. Shin. 2016. Version traveler: Fast and memory-efficient version switching in graph processing systems. In Proceedings of the 2016 USENIX Annual Technical Conference."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1109\/IPDPS.2012.73","article-title":"PAMI: A parallel active message interface for the blue gene\/Q supercomputer","author":"Kumar S.","year":"2012","unstructured":"S. Kumar, A. Mamidala, Daniel Faraj, B. Smith, M. Blocksome, B. Cernohous, D. Miller, J. Parker, J. Ratterman, P. Heidelberger, D. Chen, and B. Steinmacher-Burow. 2012. PAMI: A parallel active message interface for the blue gene\/Q supercomputer. 2012 IEEE 26th International Parallel and Distributed Processing Symposium (2012), 763\u2013773.","journal-title":"2012 IEEE 26th International Parallel and Distributed Processing Symposium"},{"key":"e_1_3_3_30_2","unstructured":"J. Leskovec Deepayan Chakrabarti J. Kleinberg C. Faloutsos and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. arXiv:0812.4905. Retrieved from https:\/\/arxiv.org\/abs\/0812.4905"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.14778\/3324301.3324306"},{"key":"e_1_3_3_32_2","first-page":"230","article-title":"Scalable Graph500 design with MPI-3 RMA","author":"Li Mingzhe","year":"2014","unstructured":"Mingzhe Li, Xiaoyi Lu, S. Potluri, Khaled Hamidouche, J. Jose, K. Tomko, and D. Panda. 2014. Scalable Graph500 design with MPI-3 RMA. 2014 IEEE International Conference on Cluster Computing (2014), 230\u2013238.","journal-title":"2014 IEEE International Conference on Cluster Computing"},{"key":"e_1_3_3_33_2","volume-title":"USENIX Annual Technical Conference (ATC 17)","author":"Ma Lingxiao","unstructured":"Lingxiao Ma, Han Chen, Jilong Xue, and Yafei Dai. [n. d.]. Garaph: Efficient GPU-accelerated graph processing on a single machine with balanced replication. In USENIX Annual Technical Conference (ATC 17). USENIX Association."},{"key":"e_1_3_3_34_2","volume-title":"Proceedings of the IEEE ICDCS","author":"Mayer Christian","year":"2016","unstructured":"Christian Mayer, Muhammad Adnan Tariq, Chen Li, and Kurt Rothermel. 2016. GrapH: Heterogeneity-aware graph computation with adaptive partitioning. In Proceedings of the IEEE ICDCS."},{"key":"e_1_3_3_35_2","first-page":"408","article-title":"Performance evaluation of supercomputer fugaku using breadth-first search benchmark in Graph500","author":"Nakao Masahiro","year":"2020","unstructured":"Masahiro Nakao, Koji Ueno, Katsuki Fujisawa, Yuetsu Kodama, and M. Sato. 2020. Performance evaluation of supercomputer fugaku using breadth-first search benchmark in Graph500. 2020 IEEE International Conference on Cluster Computing (2020), 408\u2013409.","journal-title":"2020 IEEE International Conference on Cluster Computing"},{"key":"e_1_3_3_36_2","first-page":"25","volume-title":"Proceedings of the EDBT","author":"Nicoara Daniel","year":"2015","unstructured":"Daniel Nicoara, Shahin Kamali, Khuzaima Daudjee, and Lei Chen. 2015. Hermes: Dynamic partitioning for distributed social network graph databases. In Proceedings of the EDBT. 25\u201336."},{"key":"e_1_3_3_37_2","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1109\/IPPS.1998.669923","article-title":"Performance and experience with LAPI-a new high-performance communication library for the IBM RS\/6000 SP","author":"Shah G.","year":"1998","unstructured":"G. Shah, J. Nieplocha, J. Mirza, Chulho Kim, R. Harrison, R. Govindaraju, K. Gildea, Paul DiNicola, and C. A. Bender. 1998. Performance and experience with LAPI-a new high-performance communication library for the IBM RS\/6000 SP. Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing (1998), 260\u2013266.","journal-title":"Proceedings of the 1st Merged International Parallel Processing Symposium and Symposium on Parallel and Distributed Processing"},{"key":"e_1_3_3_38_2","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation","author":"Shi Jiaxin","year":"2016","unstructured":"Jiaxin Shi, Youyang Yao, Rong Chen, Haibo Chen, and Feifei Li. 2016. Fast and concurrent rdf queries with rdma-based distributed graph exploration. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation."},{"key":"e_1_3_3_39_2","first-page":"135","volume-title":"Proceedings of the ACM Sigplan Notices","author":"Shun Julian","year":"2013","unstructured":"Julian Shun and Guy E Blelloch. 2013. Ligra: A lightweight graph processing framework for shared memory. In Proceedings of the ACM Sigplan Notices. ACM, 135\u2013146."},{"key":"e_1_3_3_40_2","first-page":"669","volume-title":"Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation","author":"Xiao Wencong","year":"2017","unstructured":"Wencong Xiao, Jilong Xue, Youshan Miao, Zhen Li, Cheng Chen, Ming Wu, Wei Li, and Lidong Zhou. 2017. Tux2: Distributed graph computation for machine learning. In Proceedings of the 14th USENIX Symposium on Networked Systems Design and Implementation. USENIX Association, 669\u2013682."},{"key":"e_1_3_3_41_2","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation","author":"Zhang Mingxing","year":"2016","unstructured":"Mingxing Zhang, Yongwei Wu, Kang Chen, Xuehai Qian, Xue Li, and Weimin Zheng. 2016. Exploring the hidden dimension in graph processing. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation."},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.3020813"},{"key":"e_1_3_3_43_2","first-page":"301","volume-title":"Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016.","author":"Zhu Xiaowei","year":"2016","unstructured":"Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A computation-centric distributed graph processing system. In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2016, Savannah, GA, USA, November 2-4, 2016.Kimberly Keeton and Timothy Roscoe (Eds.), USENIX Association, 301\u2013316. Retrieved from https:\/\/www.usenix.org\/conference\/osdi16\/technical-sessions\/presentation\/zhu"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676846","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3676846","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:12Z","timestamp":1750295952000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3676846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,19]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3676846"],"URL":"https:\/\/doi.org\/10.1145\/3676846","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,19]]},"assertion":[{"value":"2023-08-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-26","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-19","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}