Source-linked AI summary
To Push or To Pull: On Reducing Communication and Synchronization in Graph Computations
Maciej Besta, Michal Podstawski, Linus Groner, Edgar Solomonik, Torsten Hoefler
TL;DR
Graph processing suffers from costly communication and synchronization, motivating a comparison of pushing updates to shared state with pulling them into private state. The paper analyzes this dichotomy across many algorithms and execution settings, finding complementary trade-offs and using generic switching strategies to reduce both costs. These findings identify suitable variants for graph algorithms and support improvements to graph-processing engines.
Problem
Irregular communication and limited locality make synchronization and data movement expensive in graph processing.
Method
The paper analyzes push and pull formulations across graph algorithms, programming models, graph abstractions, and graph families using complexity analysis, performance data, and hardware counters.
Results
Pulling usually reduces atomics and locks, while pushing often reduces memory reads and writes; generic strategies limit both costs.
Takeaways & Limitations
The push-pull analysis can guide faster implementations of graph-processing engines and libraries across shared-memory and distributed-memory systems.
Takeaways & Limitations
The Boruvka scheme is practically efficient despite relying on a simple approach rather than theoretically faster connectivity and spanning-forest algorithms.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Graph processing is difficult to parallelize because irregular communication and limited locality make synchronization and data movement expensive. This paper studies push-pull formulations across algorithms, models, and graph settings to determine their complexity and performance trade-offs.
- Problem: Graph computations incur expensive synchronization and large data movement because their communication patterns are irregular and locality is limited.These costs arise on both shared-memory and distributed-memory systems.
- Motivation: 2.4x: direction optimization accelerates BFS on real-world graphs by combining top-down pushing with bottom-up pulling.Top-down BFS iterates over neighbors of active-frontier vertices, whereas bottom-up BFS has unvisited vertices search for frontier neighbors.
- Motivation: Push and pull differ in where updates are applied: pushing writes to shared state, while pulling gathers updates into a thread’s private state.The distinction is illustrated for BFS and PageRank and motivates questions about applicability, speed, and acceleration.
- Contribution: The paper presents an extensive analysis of push-pull formulations across graph algorithms, programming models, and graph representations.It covers centrality schemes, traversals, minimum spanning trees, graph coloring, and triangle counting, using PRAM analysis and shared- and distributed-memory performance studies.
- Evaluation scope: Graph processing is evaluated across shared- and distributed-memory systems using threading, message passing, and remote memory access.The paper also analyzes PRAM synchronization and communication differences between push and pull variants.
3 PUSH-PULL: APPLICABILITY
The push-pull dichotomy applies to iterative graph schemes and traversals, including PageRank, triangle counting, graph coloring, minimum spanning trees, BFS, SSSP, and betweenness centrality. Across these algorithms, pulling generally confines writes to owned vertices, while pushing can reduce work when only a subset of vertices is active.
- Algorithm Formulations: PageRank, triangle counting, BFS, SSSP-Δ, betweenness centrality, graph coloring, and Boruvka MST each admit push and pull variants.The formulations differ in whether updates are propagated from active or owned vertices or gathered by their destinations.
- Betweenness Centrality: Brandes’ betweenness centrality combines shortest-path traversal with backward accumulation, and both phases can use push or pull formulations.The first phase computes predecessor and shortest-path information; the second accumulates dependencies backward through the resulting tree.
- Push-Pull Insights: Pulling restricts each thread to modifying its assigned vertices, whereas pushing permits updates to vertices owned by other threads.This ownership distinction is the basis for the paper’s synchronization analysis.
- Push-Pull Insights: Pulling requires less synchronization, while pushing can require less work when only a subset of vertices updates its neighbors.The trade-off connects synchronization cost with the amount of active graph work.
- Applicability: The dichotomy covers iterative schemes and traversals, including PageRank, triangle counting, graph coloring, Boruvka MST, BFS, SSSP-Δ, and betweenness centrality.The paper provides push and pull formulations for each class, including both phases of Brandes’ betweenness-centrality algorithm.
4 THEORETICAL ANALYSIS
The analysis derives push and pull formulations, PRAM costs, conflicts, and synchronization requirements for several graph algorithms. Pulling avoids write conflicts, while pushing can incur locks or atomics depending on the algorithm and model.
- 4 THEORETICAL ANALYSIS: The study derives push and pull variants while identifying read/write conflicts, asymptotic costs, and required atomics or locks under CRCW-CB and CREW PRAM models.The analysis covers PageRank, triangle counting, BFS, and related algorithms.
- PageRank: Pull-based PageRank has O(L(m/P + d̂)) time and O(Lm) work, while CREW pushing adds logarithmic factors to time and work.CRCW-CB pushing matches pulling asymptotically for the stated PageRank bounds.
- PageRank: PageRank pushing generates O(Lm) write conflicts and requires O(Lm) locks, whereas pulling requires no such atomics or locks.The lock requirement follows from floating-point write conflicts in pushing.
- Triangle Counting: Triangle counting has equal pulling and CRCW-CB pushing time and work bounds, but CREW pushing incurs logarithmic overhead.Both variants generate O(m d̂) read conflicts, while pushing also generates O(m d̂) write conflicts.
- Breadth-First Search: The generalized BFS supports push and pull implementations using shared or private frontiers and an associative, commutative accumulation operator.The formulation permits standard BFS by setting the readiness threshold to one.
PULLING
Pulling checks incoming information in private state, avoiding frontier filters and write conflicts but often scanning more graph structure. Its derived costs are favorable for some dense, all-vertex-update computations and less favorable for traversals.
- Breadth-First Search: Pulling avoids the d̂f_i-filter during frontier merging because it checks whether each vertex belongs to the frontier directly.Pushing requires an additional filter after merging frontiers.
- Breadth-First Search: Pulling BFS costs O(D(m/P + d̂)) time and O(Dm) work, compared with lower-work push bounds in CRCW-CB.Pulling checks all edges during exploration, while pushing processes frontier-dependent relaxations and filtering.
- Breadth-First Search: Pulling involves O(Dm) BFS read conflicts, whereas pushing has O(m) write conflicts and requires O(m) CAS atomics.The conflict types differ because pulling reads broadly while pushing updates shared state.
PUSHING
Pushing updates shared state from active vertices or edges, which can reduce communication but introduces write conflicts and synchronization. Its costs depend on frontier or bucket activity, graph structure, and the PRAM model.
- Δ-Stepping SSSP: Push-based Δ-stepping performs O(m l_Δ) edge relaxations and uses O(m l_Δ) CAS atomics.The algorithm processes L/Δ epochs, with each edge relaxed O(l_Δ) times.
- Betweenness Centrality: Betweenness centrality is dominated by 2n BFS invocations, and its conflict and atomic counts can vary by up to O(n) with additional parallelism.Floating-point accumulation in the second BFS requires locks instead of atomics.
- Boman Graph Coloring: Pushing and pulling in graph coloring require O(Lm) conflicts, with CAS operations resolving write conflicts in both variants.The coloring algorithm alternates partition coloring with border-vertex conflict repair.
PUSHING
The concluding comparison shows that push and pull trade communication against synchronization rather than producing one universally superior formulation. Pulling often removes atomics or locks, while pushing can reduce communication and favor traversal costs.
- Boruvka Minimum Spanning Tree: The Boruvka scheme is practical despite theoretically faster PRAM algorithms for connectivity and minimum spanning forests.Its practical efficiency relies on supervertex degrees generally growing slower than the worst-case bound.
- More Parallelism: With up to m processors, the distinction between pushing and pulling disappears in many cases.The main analysis assumes P ≤ O(n), while additional parallelism exposes other sources of concurrency.
- Atomics/Locks: Pulling removes atomics or locks completely in TC, PR, BFS, Δ-Stepping, and MST, while changing floating-point conflicts to integer conflicts in BC.The integer conflicts in BC enable atomics instead of locks.
- PUSHING: Pulling reduces synchronization relative to pushing, while pushing limits communication by reducing memory reads in BFS.The preferred direction therefore depends on the algorithm and its workload.
- Complexity: Pulling entails more time and work for traversal algorithms, whereas it is faster than pushing for PR and TC in CREW PRAM by a logarithmic factor.The comparison distinguishes traversal behavior from algorithms that update all vertices each iteration.
5 ACCELERATING PUSHING & PULLING
The paper reduces communication and synchronization overhead by targeting excessive atomics/locks in pushing and excessive reads/writes in pulling. Partition-Awareness separates local from remote neighbors so updates can use non-atomic or atomic operations selectively.
- Partition-Awareness: Partition-Awareness separates each vertex’s adjacency array into local and remote neighbors, enabling non-atomic updates for locally owned vertices and atomic updates otherwise.The transformation increases representation size from n + 2m to 2n + 2m and applies to PR, TC, and BGC.
- Partition-Awareness: The strategy reduces atomics by distinguishing whether the executing thread owns the updated vertex.Ownership determines whether an update is performed atomically or non-atomically.
- Partition-Awareness: A lightweight barrier can be outweighed by eliminating write conflicts in the local-update phase.Algorithm 8 performs local updates before the barrier and remote updates afterward.
PART 1: LOCAL UPDATES
The paper introduces strategies that reduce memory accesses, iteration counts, and conflicts in push- and pull-based graph algorithms. These include frontier-restricted processing, switching between push and pull, and switching to greedy or sequential coloring when conflicts remain concentrated.
- Frontier-Exploit: Frontier-Exploit reduces excessive reads and writes by processing only a fraction of vertices in each iteration.For graph coloring, it maintains a frontier of vertices and propagates colors through newly marked neighbors.
- Generic-Switch: Generic-Switch alternates between pushing and pulling to reduce communication while limiting the iteration count.For graph coloring, pulling can avoid conflicts, whereas using it too early causes excessive memory accesses.
- Greedy-Switch: Greedy-Switch replaces the parallel variant with an optimized greedy scheme when remaining vertices require many conflict-driven iterations.This is particularly useful when only a small fraction of vertices remains to be colored.
- Performance analysis: Table 1 reports PAPI events for PR, BGC, TC, and SSSP-Δ in the shared-memory setting.PR and BGC use average events per iteration, while TC and SSSP-Δ use total counts.
- Conflict-Removal: Conflict-Removal colors border vertices sequentially before coloring the remaining partitions in parallel, eliminating conflicts.The strategy is advantageous when the border set is small relative to the full vertex set.
6 PERFORMANCE ANALYSIS
Across shared- and distributed-memory experiments, push and pull performance varies substantially by algorithm, graph structure, and programming model. The results identify recurring trade-offs involving atomics, memory accesses, synchronization, communication, and buffering.
- Shared-Memory Analysis: Pushing is faster for Graph Coloring by ≈10% on orc and ≈9% on rca, with fewer cache/TLB misses and issued reads and writes.Both variants acquire the same number of locks.
- Shared-Memory Analysis: Pushing usually outperforms pulling for SSSP-Δ and BFS, but larger frontiers and higher-degree graphs can reduce or reverse the gap.For SSSP-Δ, increasing Δ also narrows the difference between the variants.
- Acceleration Strategies: Acceleration strategies can change the preferred variant: PageRank pushing+PA beats pulling by ≈24% on higher-degree graphs but is ≈205% slower than pushing on sparser graphs.The reported differences reflect changes in atomics, branches, reads, cache misses, and barrier overheads.
- Distributed-Memory Analysis: In distributed-memory strong scaling, Message Passing consistently outperforms RMA for PageRank by more than 10x, while RMA outperforms Message Passing for Triangle Counting.PageRank pushing is slowest, whereas Triangle Counting pulling is always faster than pushing, by less than 1% on orc and ≈25% on ljn for P=48.
7 DISCUSSION
The discussion frames push and pull as broadly applicable graph-processing choices whose trade-offs depend on data representation, algorithm structure, and programming model. It also connects these choices to communication, synchronization, implementation complexity, and established graph abstractions.
- Algorithmic scope: The push-pull distinction extends beyond BFS and PageRank to algorithms designed with abstractions such as Gather-Apply-Scatter, including SSSP and graph coloring.The paper describes push and pull formulations for both SSSP distance updates and graph-coloring updates.
- Linear-algebra formulations: Push and pull can express graph algorithms through matrix-vector operations, with CSR corresponding to pulling and CSC corresponding to pushing.CSR computes output entries independently, whereas CSC requires atomics or reduction trees to combine updates.
- Programming models: Programming models change the trade-off: point-to-point messaging can favor pushing, traversal algorithms benefit from switching, and collectives eliminate the distinction.For iterative algorithms with fixed communication patterns, pulling increases message count; collective operations have processes both push and pull data.
- Implementation complexity: Push and pull variants have similar code complexity, but pull implementations can be harder to optimize because they must fetch neighbors’ degrees in inner loops.The PageRank example contrasts simple atomic updates in pushing with additional neighbor-degree accesses in pulling.
8 RELATED WORK
Related work includes push-pull formulations for graph algorithms, graph frameworks that operationalize the distinction, acceleration strategies, and applications outside graph processing.
- Push/Pull Algorithm Variants: Prior graph-algorithm work includes bottom-up and direction-optimizing BFS, backward-traversal improvements for BC, and other push-pull variants.Direction-optimizing BFS switches between top-down and bottom-up traversal variants.
- Pushing/Pulling in Graph Frameworks: Graph frameworks implement related ideas through message passing, GAS, sparse/dense representations, or switching update directions in distributed environments.Examples include Pregel, PowerGraph, Ligra, and Gemini.
- Accelerating Strategies: Existing acceleration strategies reduce caching overheads, switch sparse and dense representations, or move from distributed schemes to sequential variants.The discussion relates Grace, Ligra, and Pregel-based improvements to the paper’s strategies.
- Pushing/Pulling outside Graph Processing: Push-pull communication has also been studied for gossip, multicasting, Intel TBB flow graphs, and software engineering.These works use push, pull, or exchange schemes for information spreading and communication control.
9 CONCLUSION
The conclusion presents push-pull analysis as a way to reduce graph-processing communication and synchronization across algorithms, systems, and graph abstractions. It reports generic strategies for limiting atomics, locks, reads, writes, and related overheads.
- 9 CONCLUSION: The paper derives advantageous update directions and analyzes their specifications, complexities, hardware-counter performance, and suitability across graph algorithms.The analysis covers triangle counting, minimum spanning trees, graph coloring, and other algorithms.
- 9 CONCLUSION: Pushing usually incurs excessive atomics and locks, whereas pulling entails more memory reads and writes.These opposing costs motivate strategies that limit both types of overhead.
- 9 CONCLUSION: Generic strategies accelerate graph processing across road networks, citation graphs, social networks, and other graph families.The conclusion attributes these gains to limiting the communication and synchronization costs associated with push and pull.
- 9 CONCLUSION: The push-pull dichotomy applies across a wide range of algorithms, strategies, graph abstractions, and programming models.The conclusion identifies vectorization as another graph-processing concept to which the dichotomy may be generalized.