Maciej Besta, M. Podstawski, L. Groner, Edgar Solomonik, Torsten 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: download slides:
Recorded talk (best effort)
BibTeX
@inproceedings{pushpull, author={Maciej Besta and M. Podstawski and L. Groner and Edgar Solomonik and Torsten 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/}, }
