research-article

ShenTu: processing multi-trillion edge graphs on millions of cores in seconds

Authors:

Xiongchao Tang,

Torsten Hoefler,

Jingfang XuAuthors Info & Claims

SC '18: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis

Article No.: 56, Pages 1 - 11

Published: 11 November 2018 Publication History

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 specialization, supernode routing, on-chip sorting, and degree-aware messaging, which together enable its unprecedented performance and scalability. It can traverse a record-size 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 webpages directly at the fine-grained page level.

References

[1]

D. A. Benson, I. Karsch-Mizrachi, D. J. Lipman, J. Ostell, and D. L. Wheeler, "Genbank," Nucleic acids research, 2005.

[2]

H. Mustafa, I. Schilken, M. Karasikov, C. Eickhoff, G. Ratsch, and A. Kahles, "Dynamic compression schemes for graph coloring," bioRxiv, 2018.

[3]

B. Pakkenberg and H. Gundersen, "Total number of neurons and glial cells in human brain nuclei estimated by the disector and the fractionator," Journal of microscopy, 1988.

[4]

A. Lumsdaine, D. Gregor, B. Hendrickson, and J. Berry, "Challenges in parallel graph processing," Parallel Processing Letters, 2007.

[5]

M. Faloutsos, P. Faloutsos, and C. Faloutsos, "On power-law relationships of the internet topology," in SIGCOMM, ACM, 1999.

Digital Library

[6]

J. Shun and G. E. Blelloch, "Ligra: a lightweight graph processing framework for shared memory," in ACM SIGPLAN Notices, ACM, 2013.

Digital Library

[7]

X. Zhu, W. Chen, W. Zheng, and X. Ma, "Gemini: A computation-centric distributed graph processing system," in OSDI, USENIX, 2016.

Digital Library

[8]

X. Wu, V. Kumar, J. R. Quinlan, J. Ghosh, Q. Yang, H. Motoda, G. J. McLachlan, A. Ng, B. Liu, S. Y. Philip, Z.-H. Zhou, M. Steinbach, D. J. Hand, and D. Steinberg, "Top 10 algorithms in data mining," Knowledge and information systems, 2008.

Digital Library

[9]

G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski, "Pregel: a system for large-scale graph processing," in SIGMOD, ACM, 2010.

Digital Library

[10]

A. Ching, S. Edunov, M. Kabiljo, D. Logothetis, and S. Muthukrishnan, "One trillion edges: Graph processing at facebook-scale," VLDB, 2015.

Digital Library

[11]

M. Wu, F. Yang, J. Xue, W. Xiao, Y. Miao, L. Wei, H. Lin, Y. Dai, and L. Zhou, "Gram: scaling graph computation to the trillions," in SoCC, ACM, 2015.

Digital Library

[12]

Harshvardhan, A. Fidel, N. M. Amato, and L. Rauchwerger, "An algorithmic approach to communication reduction in parallel graph algorithms," in PACT, IEEE, 2015.

Digital Library

[13]

A. Roy, L. Bindschaedler, J. Malicevic, and W. Zwaenepoel, "Chaos: Scale-out graph processing from secondary storage," in SOSP, 2015.

Digital Library

[14]

P. Kumar and H. H. Huang, "G-store: high-performance graph store for trillion-edge processing," in SC, IEEE Press, 2016.

Digital Library

[15]

H. Liu and H. H. Huang, "Graphene: Fine-grained io management for graph computing," in FAST, USENIX Association, 2017.

Digital Library

[16]

S. Maass, C. Min, S. Kashyap, W. Kang, M. Kumar, and T. Kim, "Mosaic: Processing a trillion-edge graph on a single machine," in Proceedings of the Twelfth European Conference on Computer Systems, pp. 527--543, ACM, 2017.

Digital Library

[17]

D. Nguyen, A. Lenharth, and K. Pingali, "A lightweight infrastructure for graph analytics," in SOSP, SOSP, ACM, 2013.

Digital Library

[18]

K. Zhang, R. Chen, and H. Chen, "Numa-aware graph-structured analytics," in ACM SIGPLAN Notices, ACM, 2015.

Digital Library

[19]

N. Sundaram, N. Satish, M. M. A. Patwary, S. R. Dulloor, M. J. Anderson, S. G. Vadlamudi, D. Das, and P. Dubey, "Graphmat: High performance graph analytics made productive," VLDB, 2015.

Digital Library

[20]

A. Kyrola, G. E. Blelloch, and C. Guestrin, "Graphchi: Large-scale graph computation on just a pc.," in OSDI, 2012.

Digital Library

[21]

A. Roy, I. Mihailovic, and W. Zwaenepoel, "X-stream: edge-centric graph processing using streaming partitions," in SOSP, ACM, 2013.

Digital Library

[22]

D. Zheng, D. Mhembere, R. Burns, J. Vogelstein, C. E. Priebe, and A. S. Szalay, "Flashgraph: Processing billion-node graphs on an array of commodity ssds," in FAST, 2015.

Digital Library

[23]

X. Zhu, W. Han, and W. Chen, "Gridgraph: Large scale graph processing on a single machine using 2-level hierarchical partitioning," in USENIX ATC, 2015.

Digital Library

[24]

Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein, "Distributed graphlab: a framework for machine learning and data mining in the cloud," VLDB, 2012.

Digital Library

[25]

J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, "Powergraph: Distributed graph-parallel computation on natural graphs.," in OSDI, 2012.

Digital Library

[26]

R. Chen, J. Shi, Y. Chen, and H. Chen, "Powerlyra: Differentiated graph computation and partitioning on skewed graphs," in Proceedings of the Tenth European Conference on Computer Systems, ACM, 2015.

Digital Library

[27]

S. Hong, S. Depner, T. Manhardt, J. Van Der Lugt, M. Verstraaten, and H. Chafi, "Pgx.d: A fast distributed graph processing engine," in SC, ACM, 2015.

Digital Library

[28]

D. Gregor and A. Lumsdaine, "The parallel bgl: A generic library for distributed graph computations," POOSC, 2005.

[29]

F. Checconi and F. Petrini, "Traversing trillions of edges in real time: Graph exploration on large-scale parallel machines," IPDPS, 2014.

Digital Library

[30]

H. Lin, X. Tang, B. Yu, Y. Zhuo, W. Chen, J. Zhai, W. Yin, and W. Zheng, "Scalable graph traversal on sunway taihulight with ten million cores," in IPDPS, IEEE, 2017.

[31]

K. Ueno, T. Suzumura, N. Maruyama, K. Fujisawa, and S. Matsuoka, "Extreme scale breadth-first search on supercomputers," in Big Data, IEEE, 2016.

[32]

C. Burstedde, O. Ghattas, M. Gurnis, T. Isaac, G. Stadler, T. Warburton, and L. Wilcox, "Extreme-scale amr," in SC, IEEE, 2010.

Digital Library

[33]

M. Bernaschi, M. Bisson, T. Endo, S. Matsuoka, and M. Fatica, "Petaflop biofluidics simulations on a two million-core system," in SC, 2011.

Digital Library

[34]

J. Chhugani, C. Kim, H. Shukla, J. Park, P. Dubey, J. Shalf, and H. D. Simon, "Billion-particle simd-friendly two-point correlation on large-scale hpc cluster systems," in SC, IEEE Computer Society Press, 2012.

Digital Library

[35]

T. Muranushi, H. Hotta, J. Makino, S. Nishizawa, H. Tomita, K. Nitadori, M. Iwasawa, N. Hosono, Y. Maruyama, H. Inoue, H. Yashiro, and Y. Nakamura, "Simulations of below-ground dynamics of fungi: 1.184 pflops attained by automated generation and autotuning of temporal blocking codes," in SC, 2016.

Digital Library

[36]

H. Fu, J. Liao, J. Yang, L. Wang, Z. Song, X. Huang, C. Yang, W. Xue, F. Liu, F. Qiao, W. Zhao, X. Yin, C. Hou, C. Zhang, W. Ge, J. Zhang, Y. Wang, C. Zhou, and G. Yang, "The Sunway TaihuLight supercomputer: system and applications," Science China Information Sciences, vol. 072001, 2016.

[37]

W. Zhang, J. Lin, W. Xu, H. Fu, and G. Yang, "Scstore: managing scientific computing packages for hybrid system with containers," Tsinghua Science and Technology, vol. 22, no. 6, pp. 675--681, 2017.

[38]

J. E. Gonzalez, R. S. Xin, A. Dave, D. Crankshaw, M. J. Franklin, and I. Stoica, "GraphX : Graph Processing in a Distributed Dataflow Framework," in OSDI '14, 2014.

Digital Library

[39]

S. Beamer, K. Asanovic, and D. Patterson, "Searching for a Parent Instead of Fighting Over Children: A Fast Breadth-First Search Implementation for Graph500," Tech Report UCB/EECS-2011-117, 2011.

[40]

M. Besta, M. Podstawski, L. Groner, E. Solomonik, and T. Hoefler, "To push or to pull: On reducing communication and synchronization in graph computations," in HPDC'17, ACM, 2017.

Digital Library

[41]

G. Karypis and V. Kumar, "A fast and high quality multilevel scheme for partitioning irregular graphs," SIAM SISC, 1998.

Digital Library

[42]

S. Beamer, A. Buluc, K. Asanovic, and D. Patterson, "Distributed memory breadth-first search revisited: Enabling bottom-up search," IPDPSW, 2013.

Digital Library

[43]

P. Erdős and A. Rényi, "On the existence of a factor of degree one of a connected random graph," Acta Mathematica Hungarica, 2005.

[44]

H. Kwak, C. Lee, H. Park, and S. Moon, "What is twitter, a social network or a news media?," in WWW, ACM, 2010.

Digital Library

[45]

P. Boldi and S. Vigna, "The webgraph framework i: compression techniques," in WWW, ACM, 2004.

Digital Library

[46]

W. Han, X. Zhu, Z. Zhu, W. Chen, W. Zheng, and J. Lu, "Weibo, and a tale of two worlds," in ASONAM 2015, ACM, 2015.

Digital Library

[47]

The lemur project: Clueweb12 web graph., "http://www.lemurproject.org/clueweb12/webgraph.php/."

[48]

WDC - Hyperlink Graphs, "http://webdatacommons.org/hyperlinkgraph/," 2018.

[49]

J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos, "Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication," in ECML-PKDD'05, Springer, 2005.

[50]

D. Chakrabarti, Y. Zhan, and C. Faloutsos, "R-mat: A recursive model for graph mining," in SIAM DM'04, SIAM, 2004.

[51]

Z. Gyöngyi, H. Garcia-Molina, and J. Pedersen, "Combating web spam with trustrank," in VLDB, VLDB Endowment, 2004.

Digital Library

[52]

T. Hoefler, T. Schneider, and A. Lumsdaine, "Multistage Switches are not Crossbars: Effects of Static Routing in High-Performance Networks," in Cluster'08, IEEE, Oct. 2008.

[53]

J. Dean and S. Ghemawat, "Mapreduce: simplified data processing on large clusters," Communications of the ACM, 2008.

Digital Library

[54]

K. Avrachenkov, N. Litvak, D. Nemirovsky, and N. Osipova, "Monte carlo methods in pagerank computation: When one iteration is sufficient," SIAM NA, vol. 45, no. 2, pp. 890--904, 2007.

Digital Library

[55]

Search engine optimization marketing spending, "https://www.statista.com/statistics/269410/advertising-expenditure-for-seo-marketing/," 2018.

Cited By

Ji XYang BZhang TMa XZhu XWang XEl-Sayed NZhai JLiu WXue WMerchant AWeatherspoon H(2019)Automatic, application-aware I/O forwarding resource allocationProceedings of the 17th USENIX Conference on File and Storage Technologies10.5555/3323298.3323323(265-279)Online publication date: 25-Feb-2019
https://dl.acm.org/doi/10.5555/3323298.3323323
Yang BJi XMa XWang XZhang TZhu XEl-Sayed NLan HYang YZhai JLiu WXue WLorch JYu M(2019)End-to-end I/O monitoring on a leading supercomputerProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323267(379-394)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323267

ShenTu: processing multi-trillion edge graphs on millions of cores in seconds

Recommendations

ShenTu: processing multi-trillion edge graphs on millions of cores in seconds
SC '18: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis

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 ...
On the adjacent vertex distinguishing edge colourings of graphs

A k-adjacent vertex distinguishing edge colouring or a k-avd-colouring of a graph G is a proper k-edge colouring of G such that no pair of adjacent vertices meets the same set of colours. The avd-chromatic number, denoted by χ'a(G), is the minimum ...
On the vertex-arboricity of K5-minor-free graphs of diameter 2

An induced forest k-partition of a graph G is a k-partition (V"1,V"2,...,V"k) of the vertex set of G such that, for each i with 1@?i@?k, the subgraph induced by V"i is a forest. The vertex-arboricity of a graph G is the minimum k such that G has an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '18: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis

November 2018

932 pages

Sponsors

SIGHPC: ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing

In-Cooperation

IEEE CS

Publisher

IEEE Press

Publication History

Published: 11 November 2018

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SC18

Sponsor:

SIGHPC

SC18: The International Conference for High Performance Computing, Networking, Storage and Analysis

November 11 - 16, 2018

Texas, Dallas

Acceptance Rates

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
377
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ji XYang BZhang TMa XZhu XWang XEl-Sayed NZhai JLiu WXue WMerchant AWeatherspoon H(2019)Automatic, application-aware I/O forwarding resource allocationProceedings of the 17th USENIX Conference on File and Storage Technologies10.5555/3323298.3323323(265-279)Online publication date: 25-Feb-2019
https://dl.acm.org/doi/10.5555/3323298.3323323
Yang BJi XMa XWang XZhang TZhu XEl-Sayed NLan HYang YZhai JLiu WXue WLorch JYu M(2019)End-to-end I/O monitoring on a leading supercomputerProceedings of the 16th USENIX Conference on Networked Systems Design and Implementation10.5555/3323234.3323267(379-394)Online publication date: 26-Feb-2019
https://dl.acm.org/doi/10.5555/3323234.3323267

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents