  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.
