parallel breadth first search

**Parallel Breadth-First Search (BFS)** is the **foundational graph traversal algorithm that explores vertices level by level from a source vertex — where parallelizing BFS requires handling the irregular, data-dependent nature of graph topology that creates severe load imbalance, unpredictable memory access patterns, and a very low computation-to-memory-access ratio, making parallel BFS one of the most challenging kernels in high-performance computing and the basis of the Graph500 benchmark for ranking supercomputers**. **Sequential BFS** Starting from source vertex s, visit all vertices at distance 1 (s's neighbors), then distance 2 (neighbors' neighbors), etc. Uses a FIFO queue — dequeue a vertex, enqueue its unvisited neighbors. O(V + E) time. **Parallel BFS Approaches** **Level-Synchronous (Top-Down)**: - Process all vertices in the current frontier in parallel. For each frontier vertex, explore its neighbors and add unvisited neighbors to the next frontier. - Each level is fully parallel — all frontier vertices processed simultaneously. A barrier synchronizes between levels. - Limitation: Load imbalance — power-law graphs have few high-degree vertices producing millions of neighbors and many low-degree vertices producing few. Some threads work 1000× harder than others. **Bottom-Up BFS (Beamer et al.)**: - Instead of frontier vertices searching outward, unvisited vertices check if ANY of their neighbors is in the current frontier. - Highly effective when the frontier is large (>10% of vertices) — most unvisited vertices find a frontier neighbor quickly, terminating the search early. - Direction-optimizing BFS switches between top-down (small frontier) and bottom-up (large frontier) — 2-10× faster than pure top-down on power-law graphs. **GPU BFS** - **Warp-Level Work Distribution**: Each warp processes one frontier vertex's adjacency list. High-degree vertices (1000+ neighbors) utilize the full warp; low-degree vertices waste threads. - **Load-Balanced Approaches**: Merge all frontier vertices' edge lists into a single list and distribute edges uniformly across threads (Merrill et al.). Each thread processes the same number of edges regardless of which vertex they belong to. - **Memory Challenges**: Adjacency list access is inherently irregular — graph structure determines memory access pattern, causing poor cache utilization and uncoalesced global memory reads. **Performance Characteristics** BFS on a scale-26 Graph500 graph (2^26 vertices, ~1 billion edges): - Single-thread CPU: ~100 seconds - 64-core CPU (direction-optimizing): ~1-2 seconds - Single GPU (H100): ~0.2-0.5 seconds - Multi-GPU (8× H100): ~0.05-0.1 seconds Measured in GTEPS (Giga Traversed Edges Per Second): top Graph500 systems achieve 10,000+ GTEPS using thousands of nodes. **Applications Beyond Graph Traversal** - **Shortest Paths (SSSP)**: BFS solves unweighted SSSP directly. Weighted SSSP (Dijkstra/Bellman-Ford) uses BFS-like level processing. - **Connected Components**: Label propagation algorithms use BFS-like frontier expansion. - **Social Network Analysis**: Betweenness centrality requires BFS from every vertex. Parallel BFS enables centrality computation on billion-vertex social graphs. - **Knowledge Graph Reasoning**: Multi-hop query answering traverses knowledge graphs using BFS-like exploration. Parallel BFS is **the litmus test for irregular parallel computing** — an algorithm where the data structure itself determines the parallelism, creating the load imbalance and memory-access challenges that expose the limits of both hardware and software in handling real-world graph workloads.