Abstract
This paper presents a new distributed-memory algorithm called FastSV for finding connected components in an undirected graph. Our algorithm simplifies the classic Shiloach-Vishkin algorithm and employs several novel and efficient hooking strategies for faster convergence. We map different steps of FastSV to linear algebraic operations and implement them with the help of scalable graph libraries. FastSV uses sparse operations to avoid redundant work and optimized MPI communication to avoid bottlenecks. The resultant algorithm shows high-performance and scalability as it can find the connected components of a hyperlink graph with over 134B edges in 30 seconds using 262K cores on a Cray XC40 supercomputer. FastSV outperforms the state-of-the-art algorithm by an average speedup of 2.21x (max 4.27x) on a variety of real-world graphs.
Introduction
Finding connected components (CC) is a fundamental task in graph analysis, essential for applications ranging from bioinformatics to web structure analysis. However, parallelizing CC algorithms for "high-diameter" graphs—where paths between nodes can be extremely long—presents significant challenges. Traditional approaches like Breadth-First Search (BFS) scale poorly in these scenarios because their parallel depth is proportional to the graph's diameter.
The Shiloach-Vishkin (SV) scheme offers an alternative by treating the graph as a forest of trees, iteratively "hooking" trees together and "shortcutting" them to reduce height. While state-of-the-art implementations like LACC are scalable, they often involve complex multi-stage iterations that introduce computational overhead. FastSV addresses this by simplifying the SV framework and introducing novel hooking strategies to accelerate convergence.
Algorithmic Innovations
FastSV streamlines the SV process into two primary steps: hooking and shortcutting. To maintain efficiency despite this simplification, the authors introduced several key optimizations:
- Hooking to Grandparent: Instead of a tree root hooking onto a neighbor’s parent, it hooks onto the neighbor’s grandparent, creating shorter trees from the outset.
- Stochastic Hooking: This allows any node in a tree to hook independently, rather than restricting initiation to roots. This flexibility often leads to faster global merging.
- Aggressive Hooking: During the shortcutting phase, nodes are given additional opportunities to hook into a neighbor's grandparent, utilizing computationally "cheap" operations to further reduce tree height.
- Early Termination: The authors proved that if the grandparent vector remains unchanged after an iteration, the algorithm has converged, allowing it to skip unnecessary final cleanup steps.
As shown in the ablation study above, each successive optimization (from sv1 to sv5) generally reduces the number of iterations required to resolve the connected components across various graph types. This faster convergence is a primary driver of the algorithm's overall speed.
Implementation and Scalability
FastSV is implemented using GraphBLAS, expressing graph operations as linear algebra. By leveraging the CombBLAS library for distributed memory and SuiteSparse for shared memory, the algorithm achieves high portability and performance. A critical efficiency gain comes from the use of sparsity: as the algorithm progresses and most nodes find their roots, FastSV switches from dense to sparse matrix-vector multiplications, significantly cutting communication costs and avoiding redundant work.
Experimental Results
The researchers evaluated FastSV on 14 diverse datasets, including the massive Hyperlink graph with 124.9 billion edges. On the Cray XC40 supercomputer (Cori), the algorithm demonstrated linear scalability up to 262,144 cores.
In performance benchmarks, FastSV consistently outperformed LACC, the previous state-of-the-art. On average, FastSV achieved a 2.21x speedup, processing the massive Hyperlink graph in just 30 seconds. While LACC retains an advantage in graphs with a vast number of small, disconnected components due to its component retirement feature, FastSV's simplicity and faster iterations make it superior for most large-scale connectivity problems.
Conclusion
FastSV represents a significant advancement in distributed graph processing. By simplifying the SV framework and employing aggressive, stochastic hooking strategies, it achieves unprecedented performance on exascale-class systems. The integration with GraphBLAS ensures that the algorithm can be easily ported to other high-performance frameworks, such as GPUs, paving the way for even faster large-scale graph analytics.
Summary updated