PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Breadth-First Search on Distributed Memory Systems

Aydin Buluc, Kamesh Madduri

arXiv:1104.4518v2cs.DCcs.MScs.PF

TL;DR

Distributed-memory BFS is difficult because graph analyses require faster parallel graph algorithms and conventional complexity models omit important machine costs. This paper explores two complementary distributed BFS approaches and reports high performance, including reduced communication overhead and strong scaling implications.

  • Problem

    Graph-based computations are important in scientific applications, but speeding up their underlying problems on distributed systems is challenging, and RAM or PRAM models inadequately capture current-system costs.

  • Method

    The paper compares a one-dimensional vertex-partitioned adjacency-array BFS with a two-dimensional sparse-matrix-partitioned BFS, including intranode multithreading and a communication-cost model.

  • Results

    The study reports the highest-reported Graph 500 per-node BFS efficiency on large distributed-memory systems and a 3.5-factor reduction in communication overhead for the hybrid two-dimensional approach.

  • Takeaways & Limitations

    The results indicate that communication-aware partitioning can deliver high distributed BFS performance and that its advantages are likely to grow as cores outpace bisection bandwidth.

  • Takeaways & Limitations

    The evaluation uses sparse graphs with skewed degree distributions, small or logarithmically bounded average path lengths, and performance remains heavily dependent on collective communication routines.

Abstract

from arXiv · show

Data-intensive, graph-based computations are pervasive in several scientific applications, and are known to to be quite challenging to implement on distributed memory systems. In this work, we explore the design space of parallel algorithms for Breadth-First Search (BFS), a key subroutine in several graph algorithms. We present two highly-tuned parallel approaches for BFS on large parallel systems: a level-synchronous strategy that relies on a simple vertex-based partitioning of the graph, and a two-dimensional sparse matrix-partitioning-based approach that mitigates parallel communication overhead. For both approaches, we also present hybrid versions with intra-node multithreading. Our novel hybrid two-dimensional algorithm reduces communication times by up to a factor of 3.5, relative to a common vertex based approach. Our experimental study identifies execution regimes in which these approaches will be competitive, and we demonstrate extremely high performance on leading distributed-memory parallel systems. For instance, for a 40,000-core parallel execution on Hopper, an AMD Magny-Cours based system, we achieve a BFS performance rate of 17.8 billion edge visits per second on an undirected graph of 4.3 billion vertices and 68.7 billion edges with skewed degree distribution.

1. INTRODUCTION

Graph analytics are increasingly important but difficult to execute efficiently on distributed-memory systems because BFS is irregular and communication-intensive. The paper explores complementary BFS strategies, optimized implementations, and a memory-reference model for understanding their performance.

  • Motivation: BFS is difficult on current platforms because graph traversal is memory-access-bound, irregular, and dependent on input-graph structure.RAM-model work estimates do not directly predict performance on architectures that penalize irregular memory accesses.
  • Motivation: Distributed-memory BFS performance depends on explicit processor communication and graph partitioning, motivating optimized parallel implementations.The study evaluates sparse graphs with billions of vertices and edges.
  • Approaches: The paper presents one-dimensional vertex-based and two-dimensional sparse-matrix partitioning approaches for distributed-memory BFS on graphs with skewed degree distributions.Both approaches are designed as complementary strategies for large-scale systems.
  • Results: The work presents highest-reported Graph 500 per-node BFS efficiency numbers for large-scale distributed-memory systems.The study also reports advantages that are likely to grow as cores-to-bandwidth ratios increase on larger systems.
  • Results: 3.5 factor reduction in communication overhead is reported for the two-dimensional partitioning approach with intra-node multithreading at high process concurrencies.The hybrid schemes also include intra-node multicore tuning and enable BFS scalability up to 40,000 cores.
  • Analysis: A memory-reference-centric performance model captures regular and irregular memory costs and inter-processor communication differences between the two BFS strategies.The model is intended to provide insight into architectural trends supporting high-performance graph algorithms.

2. BREADTH-FIRST SEARCH OVERVIEW

BFS discovers reachable vertices level by level and computes shortest-path distances in unweighted graphs. Parallel implementations must balance traversal work and synchronization against irregular memory access and distributed communication costs.

  • BFS definition: BFS systematically explores every vertex reachable from a source and produces shortest-path distances in an unweighted graph.Vertices are organized into levels according to their distance from the source.
  • Serial BFS: The serial algorithm maintains a current frontier and newly visited set, advancing one level after each frontier expansion.The outer-loop count is bounded by the longest shortest path from the source to a reachable vertex.
  • Parallel BFS: Classical parallel BFS executes frontier edge traversals concurrently, uses atomic updates, and synchronizes once per level, yielding PRAM time O(D).D denotes the graph diameter in this analysis.
  • Optimization goals: Parallel BFS optimization targets load balance, reduced atomic and barrier synchronization, and improved memory locality.These directions adapt level-synchronous BFS to the underlying architecture while keeping work near O(m+n).
  • Multithreaded systems: GPGPU BFS optimization is challenging because high utilization requires regular contiguous accesses, while level-synchronous updates to the distance array lack a work-efficient coalescing method.GPU approaches rely on large-scale multithreading to hide memory latency.
  • Multicore systems: On multicore systems, BFS performance remains dependent on graph size, cache hierarchy, and memory bandwidth despite available thread-level parallelism.Partitioning vertices and replicating high-contention structures can alleviate synchronization overhead.
  • Distributed-memory systems: Distributed 1D BFS replaces non-local visited checks with edge aggregation and an all-to-all exchange after each frontier expansion.This introduces extraneous computation and can deviate from the O(m+n) work bound.
  • Distributed-memory systems: Two-dimensional graph partitioning can limit key collective communication phases to at most √p processors, avoiding expensive all-to-all steps.Sparse-matrix sparse-vector multiplication provides a basis for the paper’s two-dimensional BFS formulation.

3. BREADTH-FIRST SEARCH ON DISTRIBUTED MEMORY SYSTEMS

The paper develops distributed-memory BFS through complementary 1D vertex partitioning and 2D sparse-matrix partitioning, with hybrid versions for multicore nodes. The 2D method organizes vector and matrix data across a processor grid and uses collective communication around each sparse matrix–sparse vector step.

  • 3.1 BFS with 1D Partitioning: 1D partitioning assigns each processor n/p vertices and their outgoing edges, representing a one-dimensional incidence-matrix decomposition.
  • 3.1 BFS with 1D Partitioning: The 1D distributed BFS aggregates frontier edges and sends them to vertex owners, where newly visited status is determined.Only owner processes maintain vertex status; multithreading enumerates adjacencies and performs buffer operations data-parallelly, with barriers for synchronization.
  • 3.2 BFS with 2D Partitioning: Each BFS iteration in the 2D approach is equivalent to sparse matrix–sparse vector multiplication over a sparse boolean adjacency matrix.The frontier is a sparse vector, and the update includes matrix–vector multiplication followed by element-wise filtering with the complement of the visited set.
  • 3.2 BFS with 2D Partitioning: The 2D algorithm partitions the adjacency matrix into submatrices on a processor grid and distributes vectors consistently with that matrix layout.Each processor stores a local matrix block, while distributed vectors expose local pieces and row-wise collective subvectors.
  • 3.2 BFS with 2D Partitioning: The 2D iteration expands frontier subvectors within processor columns, computes local SpMSV, then folds intermediate vectors across processor rows.TransposeVector precedes column-wise Allgatherv; local products are exchanged by row-wise Alltoallv before visited filtering and frontier formation.
  • 3.2 BFS with 2D Partitioning: Distributing vector entries across all processors balances storage and computation, whereas subset-only distribution can cause severe imbalance for SpMSV.The all-processor scheme matches the matrix distribution, although its expand phase uses all-gather rather than broadcast.

4. IMPLEMENTATION DETAILS

The implementations combine graph- and matrix-oriented sparse data structures with MPI communication and multicore optimizations. Their design addresses local computation, frontier storage, synchronization, and load balance in distributed BFS.

  • 4.1 Graph Representation: The graph-based implementation stores adjacencies in a CSR-like representation with sorted contiguous blocks and 64-bit vertex identifiers.Undirected edges are stored twice, and an n + 1 array indexes each vertex’s adjacency block.
  • 4.1 Graph Representation: 2D partitioning requires an O(m) local matrix structure with fast indexing, motivating DCSC for hypersparse submatrices.DCSC stores row ids alongside column pointers and column ids, whose auxiliary sizes depend on nonempty columns.
  • 4.1 Graph Representation: Hybrid 2D computation splits each node-local matrix rowwise among threads, storing each thread’s submatrix in DCSC format.
  • 4.1 Graph Representation: Frontiers remain compact sparse structures because BFS communication volume is directly proportional to frontier-vector size.The 1D implementation uses a stack, while the 2D implementation uses a sorted sparse vector.
  • 4.2 Local Computation: The SPA outperforms a heap for local SpMSV at lower processor counts, but after 10K processors the difference is marginal and the heap is preferable for lower memory consumption.The comparison was run on Hopper; the heap’s logarithmic merge cost hurts performance at small concurrencies, whereas its cumulative memory requirement is O(m).
  • 4.2 Local Computation: At six-way threading, non-atomic distance updates cause fewer than 0.5% additional insertions across all tested graphs.This optimization avoids non-scaling atomics across multi-socket configurations while preserving correct distance values after synchronization.
  • 4.3 Distributed-memory parallelism: Distributing sparse vectors only to diagonal processors creates idle time because diagonal processors perform an additional local merging phase.The observed idling time is approximately 3-4 times the communication time; distributing vectors over all processors produces almost no load imbalance.
  • 4.3 Distributed-memory parallelism: Randomly shuffling vertex identifiers before partitioning balances vertices and edges despite skewed degree distributions, but can produce an edge cut of O(m).

5. ALGORITHM ANALYSIS

The analysis models distributed BFS performance through memory-reference and MPI communication costs rather than asymptotic work and time alone. It contrasts 1D and 2D partitioning, showing trade-offs between cache working sets, computation, and communication.

  • PRAM costs O(D) time and O(m + n) work, but these terms do not realistically estimate performance on current parallel systems.
  • The proposed linear model represents regular and irregular memory references and inter-processor MPI communication using latency α and transfer-time β terms.The model distinguishes local-memory latency αL, network latency αN, and communication-pattern-specific bandwidth terms.
  • 1D Algorithm: 1D BFS includes cumulative adjacency accesses, frontier operations, distance-array checks, and writes; distance checks dominate when αL,n/p greatly exceeds βL.Distributed execution reduces the random-access array size from n to approximately n/p, lowering the cache working set.
  • 1D Algorithm: 1D all-to-all communication sends m(p−1)/p words cumulatively, while network topology and processor count determine its latency and bandwidth costs.For a ring, the estimated communication cost implies no parallel speedup.
  • 2D Algorithm: The 2D processor grid partitions the adjacency matrix across pr×pc processors, but larger local frontier vectors increase cache misses and computation costs.The local input and output vector sizes are n/pr and n/pc, respectively.
  • 2D Algorithm: Allgatherv in the expand phase and Alltoallv in the fold phase dominate 2D remote-access analysis, with Allgatherv consuming the larger share as sparsity increases.The communication-time table keeps edge counts constant while decomposing these two operations on R-MAT graphs.

6. EXPERIMENTAL STUDIES

The experiments compare 1D and 2D BFS distributions, flat MPI, and hybrid implementations across architectures, scaling regimes, graph densities, and reference systems. Performance depends on the balance between communication, computation, memory access, and available bandwidth.

  • Experimental setup: The study compares flat MPI and hybrid MPI+threading implementations of both 1D and 2D BFS distributions on R-MAT and uk-union graphs.The experiments use TEPS/GTEPS-style traversal rates and span Franklin, Hopper, and Carver systems.
  • Strong scaling: 1.5−1.8× faster performance was achieved by flat 1D algorithms than by 2D algorithms on Franklin strong-scaling experiments.The 1D hybrid algorithm became faster at larger concurrencies, while 2D algorithms spent more time in computation.
  • Communication: 30-60% less communication time was observed for 2D algorithms than for corresponding 1D algorithms at scale 32 on Franklin.Communication measurements include waiting at synchronization barriers.
  • Architecture effects: On Hopper, 2D algorithms outperformed their 1D counterparts, while flat 1D communication consumed more than 90% of execution time between 10K and 20K cores.The 2D hybrid algorithm spent less than 50% of execution time communicating on 20K cores.
  • Weak scaling: On Franklin weak scaling, flat 1D outperformed hybrid 1D, while 2D algorithms communicated less but ran slower because of higher computation overheads.The weak-scaling experiments fixed the number of edges per processor.
  • Graph density: At average degree 64, flat 2D beat flat 1D; as graphs became sparser, the performance margin increasingly favored 1D.The results support a memory-access explanation involving larger 2D vectors and local cache misses.
  • Reference comparisons: 2.72×, 3.43×, and 4.13× speedups over non-replicated reference MPI were measured for flat 1D on Franklin at 512, 1024, and 2048 cores.The implementations were also reported as up to 16× faster than PBGL on completed Carver instances.

7. CONCLUSIONS AND FUTURE WORK

The paper concludes that its hybrid 1D and 2D approaches provide strong large-scale BFS performance, with the 2D hybrid method reducing communication overhead. It also identifies future work on graph storage, programming models, partitioning, and collective communication.

  • Conclusions: The paper presents two hybrid-parallel approaches for distributed-memory BFS on large-scale synthetic and real graphs.The study analyzes both performance and communication and memory-access costs on Hopper and Franklin.
  • Conclusions: 3 GTEPS maximum performance and 4× speedup from 500 to 4000 cores are reported for the 2D algorithms on uk-union.Figure 11 reports running times on Hopper, where lower is better.
  • Conclusions: The paper reports absolute performance significantly higher than prior work on Hopper and Franklin.The comparison covers large-scale synthetic graphs used in the Graph 500 benchmark.
  • Future work: Future work includes exploiting undirected-graph symmetry to save 50% space and studying comparable communication savings.The paper also proposes investigating PGAS implementations and whether they can deliver comparable performance.
  • Future work: Hypergraph partitioning remains an open direction because BFS frontier sparsity changes across iterations and SpMSV communication has not been studied.The paper also identifies All-to-all and Allgather as important collective-communication bottlenecks at high concurrencies.
Loading 1104.4518v2…