Home Publications all years 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 theses techreports presentations edited volumes conferences Awards Research Teaching BLOG Miscellaneous Full CV [pdf]
Events
Past Events

Publications of Torsten Hoefler
Copyright Notice:
The documents distributed by this server have been provided by the
contributing authors as a means to ensure timely dissemination of
scholarly and technical work on a noncommercial basis. Copyright and all
rights therein are maintained by the authors or by other copyright
holders, notwithstanding that they have offered their works here
electronically. It is understood that all persons copying this
information will adhere to the terms and constraints invoked by each
author's copyright. These works may not be reposted without the explicit
permission of the copyright holder.
E. Solomonik, M. Besta, F. Vella, T. 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:   BibTeX  @inproceedings{, author={E. Solomonik and M. Besta and F. Vella and T. 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/}, } 

