FastCC: A System-Algorithm Co-Design for Connected Components Computation on Large Power-Law Graphs

Connected Components (CC) is fundamental for analyzing topological structures in complex systems, with critical applications spanning social networks, communication infrastructures, and graph machine learning.Efficiently computing CC on prevalent real-world power-law graphs remains challenging due to skewed degree distributions, which induce redundant memory operations and severe performance bottlenecks. Our systematic evaluation of 23 state-of-the-art algorithms reveals that the sampling phase dominates runtime (>85% on average) and that CC with breadth-first search (BFS) sampling is optimal for power-law graphs. However, existing BFS sampling implementations suffer from two critical hardware utilization issues: (i) low thread utilization (<2%) in the first iteration due to vertex-level task assignment, and (ii) excessive synchronization overhead caused by rigid layer-based barriers inherited from traditional BFS. To address these limitations, we propose FastCC, a system-algorithm co-designed CC method optimized for power-law graphs. FastCC focuses on maximizing hardware resource utilization through two core innovations: (i) Hybrid-granularity Task Partitioning (HTP) employs an initial edge-grained distribution to engage all threads effectively, achieving over 60% thread utilization in the first iteration. It then transitions to vertex-grained partitioning in subsequent iterations to enhance task allocation efficiency. (ii) Relaxed Synchronization (RS) eliminates rigid layer barriers, enabling out-of-order, multi-hop processing within iterations to drastically reduce synchronization overhead and redundant computation. Experimental results demonstrate FastCC’s exceptional efficiency and scalability. It achieves 4.8 × to 35.9 × (average 21.8 ×) speedup over state-of-the-art algorithms across diverse datasets. Crucially, FastCC can process graphs with over 42 billion edges in under 2 seconds on a single node using less than 384GB DRAM, establishing it as a leading solution for large-scale power-law graph analysis. Moreover, deployed as the preprocessing stage on the Tianhe Exa-node Prototype, FastCC propelled the system to rank No.1 in the latest GreenGraph500, being 1.44 × more efficient than the second most efficient system.