Home Publications edited volumes Awards Research Teaching BLOG Miscellaneous Full CV [pdf] blog
Events
Past Events

Publications of Torsten Hoefler
Edgar Solomonik, Maciej Besta, F. Vella, Torsten Hoefler:
  Scaling Betweenness Centrality using CommunicationEfficient Sparse Matrix Multiplication
(Nov. 2017, Accepted at The International Conference for High Performance Computing, Networking, Storage and Analysis (SC'17) )
AbstractBetweenness 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 p 1/3 less communication on p processors than the best known alternatives, for
graphs with n vertices and average degree k = n/p 2/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 im
plementation outperforms the wellknown CombBLAS library by
up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems.
Documentsdownload article: download slides:   BibTeX  @inproceedings{, author={Edgar Solomonik and Maciej Besta and F. Vella and Torsten Hoefler}, title={{Scaling Betweenness Centrality using CommunicationEfficient Sparse Matrix Multiplication}}, year={2017}, month={Nov.}, note={Accepted at The International Conference for High Performance Computing, Networking, Storage and Analysis (SC'17)}, source={http://www.unixer.de/~htor/publications/}, } 

