Omnia vincit amor
Home -> Publications
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.

M. Besta, M. Podstawski, L. Groner, E. Solomonik, T. Hoefler:

 To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations

(In Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing (HPDC'17), presented in Washington, DC, USA, ACM, Jun. 2017)

Abstract

We reduce the cost of communication and synchronization in graph processing by analyzing the fastest way to process graphs: pushing the updates to a shared state or pulling the updates to a private state. We investigate the applicability of this push-pull dichotomy to various algorithms and its impact on complexity, performance, and the amount of used locks, atomics, and reads/writes. We consider 11 graph algorithms, 3 programming models, 2 graph abstractions, and various families of graphs. The conducted analysis illustrates surprising differences between push and pull variants of different algorithms in performance, speed of convergence, and code complexity; the insights are backed up by performance data from hardware counters. We use these findings to illustrate which variant is faster for each algorithm and to develop generic strategies that enable even higher speedups. Our insights can be used to accelerate graph processing engines or libraries on both massively-parallel shared-memory machines as well as distributed-memory systems.

Documents

download article:
 

BibTeX

@inproceedings{pushpull,
  author={M. Besta and M. Podstawski and L. Groner and E. Solomonik and T. Hoefler},
  title={{To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations}},
  year={2017},
  month={Jun.},
  booktitle={Proceedings of the 26th International Symposium on High-Performance Parallel and Distributed Computing (HPDC'17)},
  location={Washington, DC, USA},
  publisher={ACM},
  source={http://www.unixer.de/~htor/publications/},
}

serving: 54.196.89.247:59850© Torsten Hoefler