TY - GEN
T1 - Scaling Betweenness Centrality using Communication-Efficient Sparse Matrix Multiplication
AU - Solomonik, Edgar
AU - Besta, MacIej
AU - Vella, Flavio
AU - Hoefler, Torsten
N1 - Funding Information:
This research is part of the Blue Waters sustained-petascale computing project, which is supported by the National Science Foundation (awards OCI-0725070 and ACI-1238993) and the state of Illinois. Blue Waters is a joint effort of the University of Illinois at Urbana-Champaign and its National Center for Supercomputing Applications. We thank Hussein Harake, Colin McMurtrie, and the whole CSCS team granting access to the Piz Dora machine and for their excellent technical support. Maciej Besta was supported by Google European Doctoral Fellowship and Edgar Solomonik was supported by an ETH Zurich Postdoctoral Fellowship.
Publisher Copyright:
© 2017 ACM.
PY - 2017
Y1 - 2017
N2 - Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Centrality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p1/3 less communication on p processors than the best known alternatives, for graphs with n vertices and average degree k=n/p2/3. We formulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.
AB - Betweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths leading through it. We propose Maximal Frontier Betweenness Centrality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p1/3 less communication on p processors than the best known alternatives, for graphs with n vertices and average degree k=n/p2/3. We formulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.
KW - Betweenness centrality
KW - communication cost
KW - parallel algorithm
KW - sparse matrix multiplication
UR - http://www.scopus.com/inward/record.url?scp=85142212257&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85142212257&partnerID=8YFLogxK
U2 - 10.1145/3126908.3126971
DO - 10.1145/3126908.3126971
M3 - Conference contribution
AN - SCOPUS:85040162024
T3 - International Conference for High Performance Computing, Networking, Storage and Analysis, SC
BT - SC 2017 - International Conference for High Performance Computing, Networking, Storage and Analysis
PB - IEEE Computer Society
T2 - 2017 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2017
Y2 - 12 November 2017 through 17 November 2017
ER -