PaperlayerView exact revision on arXiv

Source-linked AI summary

Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable

Laxman Dhulipala, Guy E. Blelloch, Julian Shun

arXiv:1805.05208v4cs.DScs.DC

TL;DR

Large public web graphs had rarely been evaluated with broad graph algorithms on a single shared-memory machine, despite fitting in terabyte-scale memory. The paper implements theoretically efficient parallel algorithms and memory- and contention-conscious techniques for 20 graph problems. On the largest real-world graphs, the implementations generally outperform prior results and use fewer resources than distributed solutions, while cache complexity remains unanalyzed.

  • Problem

    Existing graph evaluations largely used smaller graphs or distributed and external memory, leaving open whether broad graph workloads could run efficiently in memory on the largest public graph.

  • Method

    The paper implements theoretically efficient parallel algorithms for 20 graph problems, modifying algorithms and primitives for memory efficiency and reducing implementation bottlenecks.

  • Results

    The implementations generally outperform prior performance numbers and process the largest publicly available graph on a single shared-memory server with 1TB of memory.

  • Takeaways & Limitations

    The results provide evidence that theoretically efficient shared-memory graph algorithms can be efficient and scalable in practice, including on the largest public real-world graphs.

  • Takeaways & Limitations

    The algorithms are not analyzed for cache complexity, even though the authors observe good cache performance on tested graphs.

Abstract

from arXiv · show

There has been significant recent interest in parallel graph processing due to the need to quickly analyze the large graphs available today. Many graph codes have been designed for distributed memory or external memory. However, today even the largest publicly-available real-world graph (the Hyperlink Web graph with over 3.5 billion vertices and 128 billion edges) can fit in the memory of a single commodity multicore server. Nevertheless, most experimental work in the literature report results on much smaller graphs, and the ones for the Hyperlink graph use distributed or external memory. Therefore, it is natural to ask whether we can efficiently solve a broad class of graph problems on this graph in memory. This paper shows that theoretically-efficient parallel graph algorithms can scale to the largest publicly-available graphs using a single machine with a terabyte of RAM, processing them in minutes. We give implementations of theoretically-efficient parallel algorithms for 20 important graph problems. We also present the optimizations and techniques that we used in our implementations, which were crucial in enabling us to process these large graphs quickly. We show that the running times of our implementations outperform existing state-of-the-art implementations on the largest real-world graphs. For many of the problems that we consider, this is the first time they have been solved on graphs at this scale. We have made the implementations developed in this work publicly-available as the Graph-Based Benchmark Suite (GBBS).

1 INTRODUCTION

The paper asks whether theoretically efficient parallel graph algorithms can process billion-scale graphs quickly on one shared-memory machine. It implements 20 such algorithms, introduces scalability techniques, and reports strong performance on the largest public graphs.

  • Motivation: 3.5 billion vertices and 128 billion edges make the Hyperlink Web graph a major challenge for shared- and distributed-memory systems.Existing methods often take hours, while the fastest reported times require 1–6 minutes on a supercomputer.
  • Motivation: A terabyte-RAM commodity shared-memory machine solves broad graph problems on the Hyperlink graph, often in minutes.The k-core implementation takes under 3.5 minutes on 72 cores.
  • Contributions: The work implements theoretically efficient parallel algorithms for 20 problems, including connectivity, shortest paths, PageRank, matching, graph coloring, k-core, and triangle counting.The algorithms have strong theoretical bounds on work and depth.
  • Contributions: Existing algorithms were substantially modified for memory efficiency, while several implementations are new and designed to scale.The implementations use prior work from Ligra, Ligra+, Julienne, and other efficient parallel graph algorithms.
  • Results: The evaluation is faster than previous performance numbers in almost all cases, including results on the largest publicly available graph.The authors report that many problems are solved at this scale for the first time.

2 RELATED WORK

Prior work developed theoretically efficient parallel algorithms and graph-processing frameworks, but benchmark evidence generally stopped far below terabyte-scale graphs. This paper positions its evaluation against those limitations and related systems.

  • Parallel Graph Algorithms: Parallel graph research seeks work-efficient algorithms with polylogarithmic depth, although some important problems lack known algorithms with both properties.Strongly connected components and single-source shortest paths face the transitive-closure bottleneck, while k-core is P-complete.
  • Benchmarking Parallel Graph Algorithms: Existing benchmarks cover representative graph applications and architectural properties, but differ in algorithms and scale.GraphBIG, CRONO, and LDBC evaluate between 6 and 12 applications, depending on the benchmark.
  • Benchmarking Parallel Graph Algorithms: Existing graph benchmarks usually evaluate graphs with tens or hundreds of millions of edges, with the largest reaching about two billion.Such small evaluations make scalability to terabyte-scale graphs difficult to judge.

3 PRELIMINARIES

The preliminaries define graph representations, the shared-memory execution model, atomic operations, and reusable parallel primitives underlying the algorithms. Ligra-style frontier operations provide the main graph-processing interface.

  • Graph Notation: Graphs are represented as G(V, E), with n vertices, m edges, neighbor sets N(v), and degree deg(v); weighted graphs additionally assign edge weights.The paper uses edgelist, CSC, and CSR representations and assumes no self-edges or duplicate edges.
  • Atomic Primitives: The algorithms use test-and-set, fetch-and-add, and priority-write as atomic operations.These operations coordinate concurrent updates to shared data.
  • Model: TRAM models nested parallelism through shared memory, forked threads, and series-parallel computation DAGs.Work is the number of DAG vertices, while depth is the longest path length.
  • Parallel Primitives: Scan, reduce, and filter provide standard parallel array operations with O(n) work and O(logn) depth under constant-time operators.Scan computes associative prefixes, while reduce aggregates and filter retains elements satisfying a predicate.
  • Ligra, Ligra+, and Julienne: Ligra supplies graph data structures and edgeMap, which maps edge functions over a selected vertex subset using sparse or dense methods.edgeMap runs in O(∑u∈U deg(u)) work and O(logn) depth when its functions take O(1) work.
  • Ligra, Ligra+, and Julienne: The optimized dense edgeMap method scans in-edges sequentially and can reduce examined edges at the cost of O(in-deg(v)) depth.This optimization is used in the experiments rather than the standard O(logn)-depth dense version.

4 BENCHMARK

The benchmark suite specifies inputs and outputs for a broad set of graph problems, spanning traversal, paths, connectivity, clustering, optimization, and graph statistics. These definitions establish the evaluated task coverage.

  • Benchmark Specification: The benchmark documentation identifies BFS and several shortest-path variants as distinct algorithmic tasks with explicitly specified graph inputs and output mappings.The suite separates integral-weight SSSP from general-weight Bellman-Ford SSSP.
  • Paths and Traversal: The suite includes BFS and multiple shortest-path tasks for unweighted, integral-weight, and general-weight graphs.Outputs include source-to-vertex distances, with negative-cycle handling for general-weight SSSP.
  • Decomposition and Selection: The benchmark covers low-diameter decomposition, maximal independent set, maximal matching, and graph coloring.The outputs encode clusters, independent vertices, matched edges, or colors using at most Δ+1 colors.
  • Connectivity: Connectivity tasks include connected components, spanning forest, biconnectivity, minimum spanning forest, and strongly connected components.The outputs are component labels or edge sets representing forests.
  • Approximation and Structure: Approximation and structural tasks include set cover, k-core decomposition, and approximate densest subgraph.The specified guarantees include an O(logn)-approximation for set cover and a 2(1 + ϵ) approximation for densest subgraph.
  • Graph Statistics: Graph statistics include triangle counting, PageRank after one iteration, single-source betweenness centrality, and widest-path computation.These tasks produce triangle totals, vertex scores, centrality contributions, or bottleneck path values.

5 ALGORITHMS

The paper implements theoretically efficient parallel algorithms across connectivity, shortest-path, centrality, and substructure problems, combining established primitives with memory-conscious engineering. The algorithms retain strong work/depth guarantees while targeting practical large-graph execution.

  • Algorithms: The benchmark implements parallel algorithms for connectivity, shortest paths, betweenness centrality, spanning forests, minimum spanning forests, MIS, and k-core decomposition.It also covers breadth-first search, weighted BFS, Bellman-Ford, and related graph problems.
  • Shortest Path Problems: BFS uses frontier expansion with test-and-set, while Bellman-Ford uses priority writes to propagate minimum distances.The implementations are based on graph-search routines and synchronize across search rounds.
  • Connectivity Problems: Connectivity uses low-diameter decomposition, graph contraction, and recursion to achieve O(m) expected work and O(log^3 n) depth w.h.p.The implementation separates decomposition and contraction into reusable subroutines.
  • Connectivity Problems: Borůvka’s minimum-spanning-forest implementation runs in O(m log n) work and O(log^2 n) depth on the PW-TRAM.Filtering steps reduce the edge-list sizes while supporting CSR/CSC storage for very large weighted graphs.
  • Covering Problems: The rootset-based MIS implementation runs in O(m) expected work and O(log^2 n) depth w.h.p. by processing a priority-DAG.Each round adds DAG roots to the MIS and updates neighboring priorities.
  • Substructure Problems: The parallel k-core algorithm uses degree buckets and repeated peeling, with O(m + n) expected work and ρ log n depth w.h.p.Here, ρ is the graph’s peeling-complexity, measured by the number of minimum-degree peeling rounds.

6 IMPLEMENTATIONS AND TECHNIQUES

The implementations use theoretically efficient graph primitives together with cache-, contention-, and memory-conscious optimizations for massive graphs. Key techniques include histogram processing, blocked edge traversal, reachability-label management, and compressed-graph primitives.

  • General techniques: High-degree vertices create fetch-and-add contention in early k-core peeling rounds, motivating a fast histogram implementation.The issue is especially pronounced in graphs with large maximum degree but relatively small degeneracy.
  • General techniques: Histogram aggregates values sharing each key, supporting frontier-neighbor counts through theoretically efficient semisorting or radix-sort-based processing.The radix-sort implementation targets cache performance while retaining O(n^ε) depth.
  • edgeMapBlocked: edgeMapBlocked assigns frontier edges to fixed-size logical blocks, processes live neighbors in parallel, and compacts them using prefix sums.The procedure avoids explicitly materializing all incident frontier edges before blocking.
  • edgeMapBlocked: edgeMapBlocked reduces writes and cache misses when few frontier edges produce live neighbors, improving weighted BFS running time by as much as 1.8x.The optimization is most useful when output size is substantially smaller than the total number of incident frontier edges.
  • Strongly connected components: SCC reachability phases use two graph traversals and hash-table labels, with parallel sizing and sparse storage to manage per-vertex visitation information.The implementation avoids allocating O(log n) space for every vertex because most vertices are visited only a few times.
  • Primitives on compressed graphs: Compressed-graph primitives decode large neighbor lists in parallel for filtering and packing, while intersection uses block starts and binary search.Filter and pack run in O(|L|) work and O(log n) depth; intersection runs in O(|L_a| log(1 + |L_b|/|L_a|)) work and O(log n) depth.

7 EXPERIMENTS

The experiments evaluate the implementations on real-world graphs using a 72-core machine with 1TB of memory. The inputs include social, web, and hyperlink graphs, with graph statistics and compression details reported for reproducibility.

  • Experimental evaluation: The evaluation reports running times for the implementations on real-world graph inputs, using compression schemes extended to preserve theoretical efficiency.Tables 3 and 4 contain the running-time measurements, while additional algorithm statistics are described separately.
  • Experimental setup: Experiments run on a 72-core Dell PowerEdge R930 with two-way hyper-threading and 1TB of main memory.The machine uses four 2.4GHz 18-core Intel Xeon processors.
  • Graph inputs: Table 2 records vertices, edges, diameter, peeling complexity, and degeneracy, marking unavailable exact diameters with effective lower-bound values.For undirected graphs, ρ denotes peeling rounds and kmax the largest non-empty core.
  • Experimental setup: Cilk Plus expresses parallelism, and work-stealing provides expected running time W/P + O(D) on P processors for algorithms with W work and D depth.Memory allocation is balanced across sockets with numactl.
  • Graph inputs: The graph suite includes LiveJournal, com-Orkut, Twitter, ClueWeb, Hyperlink2012, and Hyperlink2014, spanning social-network and web graphs.The inputs are directed or undirected according to the source graph and task requirements.

7.2 SSSP Problems

The SSSP experiments compare parallel shortest-path implementations across graph inputs using speedups and running times. The reported results show strong speedups for weighted BFS and related shortest-path tasks, with graph symmetrization affecting comparisons.

  • Shortest-path results: 13–67x speedups are achieved by BFS, weighted BFS, Bellman-Ford, and betweenness centrality across all inputs.The shortest-path experiments use symmetrized graph versions.
  • Shortest-path results: 38–72x speedups are achieved by the widest-path implementation across all inputs.The spanner implementation achieves 31–65x speedup with k = 4.
  • Reported measurements: The tables report single-thread time, 72-core hyper-threaded time, and speedup for algorithms on symmetric graph inputs.Experiments that did not finish within five hours are marked with an em dash.
  • Comparison conditions: Weighted BFS on Hyperlink graphs is slower than Julienne’s reported times because those experiments used directed rather than symmetrized graphs.The directed version exposes fewer reachable vertices from an average source.
  • Prior comparisons: Weighted BFS was 1.07–1.1x slower than GAP’s Δ-stepping implementation and 1.6–3.4x faster than Galois’s implementation in an earlier comparison.The comparison also included a fast sequential DIMACS shortest-path implementation.

7.3 Connectivity Problems

Connectivity-related implementations achieve substantial speedups across inputs while retaining theoretically efficient work and depth. The results also show competitive performance against prior implementations and practical effects of graph structure and ordering.

  • Low-Diameter Decomposition: 17–59x speedup is achieved by low-diameter decomposition across all inputs.The implementation fixes β at 0.2, and its running time is comparable to a BFS visiting most vertices.
  • Connectivity and Spanning Forest: 25–57x and 31–67x speedups are achieved by connectivity and spanning forest, respectively, across all inputs.Connectivity is 1.2–2.1x faster than a work-efficient prior implementation on uncompressed graphs.
  • Biconnectivity: 20–59x speedup is achieved by biconnectivity across all inputs despite O(diam(G)) depth.Most evaluated graphs have extremely low diameter; the implementation is about 3–5 times slower than connectivity.
  • Biconnectivity: 1.4–2.1x faster performance than the compared implementation is reported for biconnectivity.The comparison used a DFS-ordered subgraph; preserving the original graph order made the compared implementation 2–3x slower.
  • Strongly Connected Components: 13–43x speedup is achieved by strongly connected components across all inputs.The implementation uses β between 1.1–2.0, and larger β can improve running time on smaller graphs by up to 2x.
  • Minimum Spanning Forest: 17–54x speedup is achieved by minimum spanning forest over a single-threaded implementation across all inputs.The paper compares this implementation with PBBS union-find and Borůvka implementations.

7.4 Covering Problems

The covering-related implementations provide large speedups across inputs, including improvements for MIS, maximal matching, coloring, and approximate set cover. The comparisons also identify implementation-specific performance differences.

  • MIS and Maximal Matching: 31–70x and 25–70x speedups are achieved by MIS and maximal matching, respectively, across all inputs.The rootset-based MIS implementation is 1.1–3.5x faster than the prefix-based implementation, while maximal matching is 3–4.2x faster than the compared implementation.
  • Graph Coloring: 11–56x speedup is achieved by graph coloring across all inputs.The implementation appears 1.2–1.6x slower than the asynchronous JP implementation because many rounds synchronize on few vertices.
  • Approximate Set Cover: 5–57x speedup is achieved by approximate set cover across all inputs.The implementation regenerates random priorities for active sets and uses ϵ = 0.01 in the comparison.

7.5 Substructure Problems

The substructure implementations achieve substantial speedups across inputs, with especially large gains for approximate densest subgraph and triangle counting. The evaluation also reports scope limits for triangle-counting comparisons.

  • k-Core Decomposition: 5–46x speedup is achieved by k-core decomposition across all inputs, including 114x on the 3D-Torus graph.The 3D-Torus result occurs because all vertices are removed in a single peeling round.
  • Approximate Densest Subgraph: 44–77x speedup is achieved by approximate densest subgraph across all inputs.With ϵ = 0.001, the produced subgraphs have density roughly equal to those from a 2-approximation based on degeneracy ordering or ϵ = 0.
  • Triangle Counting: 39–81x speedup is achieved by triangle counting across all inputs.Speedups are unavailable for larger graphs because single-threaded execution took too long under the O(m3/2)-work algorithm.

7.6 Eigenvector Problems

The PageRank implementation achieves large speedups across inputs, while the figure evaluates normalized throughput scaling for several graph applications on 3D-Torus graphs. The paper also reports a comparison with GraphIt.

  • PageRank: 39–54x speedup is achieved by PageRank across all inputs.The implementation uses ϵ = 1e−6 and ϵ′ = 0.01, with dense-iteration reductions over in-neighbors reducing contention.
  • Scaling Evaluation: The figure plots normalized throughput against vertices for MIS, BFS, BC, and coloring on the 3D-Torus graph family.Throughput is measured as edges processed per second.
  • PageRank: The PageRank implementation is about 1.8x slower than GraphIt on LiveJournal and Twitter using the same thread counts.

7.7 Performance on 3D-Torus

Experiments on 3D-Torus graphs examine scaling, throughput saturation, theoretical-depth predictions, and cache-oriented implementation choices. The results show that some polylogarithmic-depth algorithms can be substantially more expensive on these graphs than on real-world graphs.

  • Scaling: LDD and connectivity ran 17–40x longer on 3D-Torus graphs than on Twitter and Twitter-Sym despite only 4x and 2.4x more edges.The experiments used a family of 3D-Torus graphs to compare diameter-bounded and polylogarithmic-depth algorithms.
  • Throughput: Throughput saturated before the largest tested graph for MIS, BFS, betweenness centrality, and graph coloring, except BFS, which saturated at 2 billion vertices.Throughput is measured as edges processed per second.
  • Theoretical depth: The half-length ordering—coloring, MIS, BFS, then BC—matches the algorithms’ ordering by depth on these graphs.Half-length is the graph size at which the system reaches half of peak performance.
  • Locality: The algorithms lack a cache-complexity analysis, although the authors observed good cache performance on the tested graphs.The datasets’ highly local vertex orders and the algorithms’ primitives may contribute to this observed behavior.

7.8 Processing Massive Web Graphs

The paper compares its implementations with distributed, disk-based, and supercomputer results on massive Hyperlink graphs. Across many tasks, the single-machine implementations are faster while using substantially fewer resources, though some comparisons have different problem definitions or outcomes.

  • Experimental setup: The evaluation compares 72-core running times with prior results and distinguishes directed Hyperlink graphs from symmetrized versions.Table 6 reports system configurations, memory, hyper-threads, nodes, and running times.
  • Comparisons with prior systems: On Hyperlink2012, the implementations outperform FlashGraph by 12x on BFS, 16x on BC, 5.3x on triangle counting, and 18x on connectivity.FlashGraph used 64 hyper-threads, 512GB of memory, and 15 SSDs on a 4-socket, 32-core machine.
  • Comparisons with prior systems: Against Blue Waters, all-connected-components is 2.5x faster, while all-strongly-connected-components is 1.6x slower than the reported largest-component implementations.The comparison uses Hyperlink2012 results from a 256-node system with 8192 hyper-threads.
  • Comparisons with prior systems: Exact coreness takes 184s, 1.9x faster than the approximate implementation while using 113x fewer cores.The competing approximation rounds coreness up to the nearest power of 2.
  • Comparisons with prior systems: Compared with Gluon, BFS, connectivity, and SSSP are 22.7x, 3x, and 9.8x faster, respectively, while PageRank is 2.9x slower.The PageRank comparison is not directly equivalent because Gluon reports PageRank-Delta rather than true PageRank.

8 CONCLUSION

The paper concludes that theoretically efficient parallel graph algorithms can process the largest publicly available real-world graph on a single shared-memory server. Its results provide evidence that such algorithms can be efficient and scalable in practice.

  • Conclusion: A single shared-memory server with 1TB of memory processed the largest publicly available real-world graph using theoretically efficient parallel algorithms.The conclusion also reports outperforming existing implementations while using fewer resources than distributed-memory solutions.
  • Conclusion: The implementations provide evidence that theoretically efficient shared-memory graph algorithms can be efficient and scalable in practice.The authors also report significantly better per-core results and expect the implementations to scale to larger graphs.

A GRAPH STATISTICS

The appendix documents graph statistics used to describe and verify the experimental datasets. It covers component structure, connectivity, triangles, and other graph-specific measures across several real-world graphs.

  • Statistics and verification: The appendix lists statistics such as connected and strongly connected components, heuristic color counts, and triangle counts for the experimental graphs.These statistics support correctness and quality checks for future algorithms run on the same graphs.
  • Metric definitions: Effective directed and undirected diameter measure the maximum traversal levels reached by SCC or BFS procedures on the directed graph.The appendix also defines largest-component size as the number of vertices in the relevant component.
  • Dataset coverage: The appendix includes graph-statistics tables for LiveJournal, com-Orkut, Twitter, ClueWeb, Hyperlink2014, and Hyperlink2012.The com-Orkut table marks statistics that do not apply to its undirected graph with dashes.
Loading 1805.05208v4…