Felix, qui, quod amat, defendere fortiter audet
Home -> Publications
Home
  Publications
    
all years
    2018
    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.

Lukas Gianinazzi, Pavel Kalvoda, Alessandro De Palma, Maciej Besta, Torsten Hoefler:

 Communication-Avoiding Parallel Minimum Cuts and Connected Components

(Feb. 2018, Accepted at The ACM Conference Principles and Practice of Parallel Programming 2018 (PPoPP'18) )

Abstract

We present novel scalable parallel algorithms for finding global minimum cuts and connected components, which are important and fundamental problems in graph processing. To take advantage of future massively parallel architectures, our algorithms are communication-avoiding: they reduce the costs of communication across the network and the cache hierarchy. The fundamental technique underlying our work is the randomized sparsification of a graph: removing a fraction of graph edges, deriving a solution for such a sparsified graph, and using the result to obtain a solution for the original input. We design and implement sparsification with O(1) synchronization steps. Our global minimum cut algorithm decreases communication costs and computation compared to the state-of-the-art, while our connected components algorithm incurs few cache misses and synchronization steps. We validate our approach by evaluating MPI implementations of the algorithms on a petascale supercomputer. We also provide an approximate variant of the minimum cut algorithm and show that it approximates the exact solutions well while using a fraction of cores in a fraction of time.

Documents

download article:


Recorded talk (best effort)

 

BibTeX

@inproceedings{,
  author={Lukas Gianinazzi and Pavel Kalvoda and Alessandro De Palma and Maciej Besta and Torsten Hoefler},
  title={{Communication-Avoiding Parallel Minimum Cuts and Connected Components}},
  year={2018},
  month={Feb.},
  note={Accepted at The ACM Conference Principles and Practice of Parallel Programming 2018 (PPoPP'18)},
  source={http://www.unixer.de/~htor/publications/},
}

serving: 54.198.104.202:48046© Torsten Hoefler