ShenTu: Processing Multi-Trillion Edge Graphs on Millions of Cores in Seconds

Authors: Heng Lin (Tsinghua University, Fma Technology), Xiaowei Zhu (Tsinghua University, Qatar Computing Research Institute), Bowen Yu (Tsinghua University), Xiongchao Tang (Tsinghua University, Qatar Computing Research Institute), Wei Xue (Tsinghua University), Wenguang Chen (Tsinghua University), Lufei Zhang (State Key Laboratory of Mathematical Engineering and Advanced Computing), Torsten Hoefler (ETH Zurich), Xiaosong Ma (Qatar Computing Research Institute), Xin Liu (National Research Centre of Parallel Computer Engineering and Technology), Weimin Zheng (Tsinghua University), Jingfang Xu (Beijing Sogou Technology Development Company)

Abstract: Graphs are an important abstraction used in many scientific fields. With the magnitude of graph-structured data constantly increasing, effective data analytics requires efficient and scalable graph processing systems. Although HPC systems have long been used for scientific computing, people have only recently started to assess their potential for graph processing, a workload with inherent load imbalance, lack of locality, and access irregularity. We propose ShenTu, the first general-purpose graph processing framework that can efficiently utilize an entire petascale system to process multi-trillion edge graphs in seconds. ShenTu embodies four key innovations: hardware specializing, supernode routing, on-chip sorting, and degree-aware messaging, which together enable its unprecedented performance and scalability. It can traverse an unprecedented 70-trillion-edge graph in seconds. Furthermore, ShenTu enables the processing of a spam detection problem on a 12-trillion edge Internet graph, making it possible to identify trustworthy and spam web pages directly at the fine-grained page level.




Back to Technical Papers Archive Listing