EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

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

Menghan Jia, Yongquan Fu, Yiming Zhang, Xinhai Chen, Dongsheng Li

ACM Transactions on Architecture and Code Optimization · 30.06.2026 · 23 (2) · 1-25

DOI: 10.1145/3803020 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Architecture and Code Optimization, online erschienen am 26.06.2026. Verfasst von Menghan Jia und 4 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0). Gefördert von: National Key Research and Development Program of China, National Natural Science Foundation of China.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Connected Components (CC) computation is a fundamental graph analytics kernel. While BFS-sampling has emerged as the state-of-the-art approach for power-law graphs, its performance in existing implementations is severely limited by inheriting unnecessary BFS semantics. The core issue is a fundamental mismatch: BFS requires strict level-synchronization to compute shortest paths, while CC only needs eventual label consistency without ordering constraints. This semantic mismatch manifests as three critical bottlenecks: (i) severe load imbalance from vertex-centric task allocation, which fails to distribute the massive workload of high-degree hub vertices; (ii) redundant writes from dynamic push/pull mode switching, which necessitates costly frontier reconstruction; and (iii) redundant synchronization and computation from enforcing BFS’s strict ordering guarantees, which are superfluous for CC computation. We introduce FastCC , a lightweight multiprocess system-algorithm co-designed solution that breaks this semantic mismatch. The cornerstone of our approach is the strategic decision to fix the highest-degree vertex as the BFS root, creating a predictable computation topology. This enables three synergistic innovations: (1) hybrid task partitioning that employs edge-centric allocation in the critical first iteration to eliminate load imbalance at its source; (2) predictable mode switching that leverages the deterministic computation graph to bypass expensive frontier reconstruction; and (3) lightweight, custom synchronization primitives that relax BFS’s strict ordering to match CC’s eventual consistency requirements, while allowing earlier label propagation within the same iteration to reduce the overall computational workload. Extensive evaluation on large-scale real-world and synthetic power-law graphs demonstrates that FastCC achieves significant performance improvements, with speedups of 10.6-55.5× faster (average: 37.8×) over state-of-the-art CC implementations including ConnectIt and vGraph. FastCC also reduces peak memory footprint by up to 2.87× and exhibits superior, more predictable scalability. The practical efficacy of our approach is validated by its deployment as the core engine in a top-ranked GreenGraph500 solution.

Förderung

  • National Key Research and Development Program of China
  • National Natural Science Foundation of China

Zitieren

APA

Jia, M., Fu, Y., Zhang, Y., Chen, X., & Li, D. (2026). FastCC: A System-Algorithm Co-Design for Connected Components Computation on Large Power-Law Graphs. ACM Transactions on Architecture and Code Optimization, 23(2), 1-25. https://doi.org/10.1145/3803020

Vancouver

Jia M, Fu Y, Zhang Y, Chen X, Li D. FastCC: A System-Algorithm Co-Design for Connected Components Computation on Large Power-Law Graphs. ACM Transactions on Architecture and Code Optimization. 2026;23(2):1-25. doi:10.1145/3803020

BibTeX
@article{Jia2026,
  author = {Jia, Menghan and Fu, Yongquan and Zhang, Yiming and Chen, Xinhai and Li, Dongsheng},
  title = {FastCC: A System-Algorithm Co-Design for Connected Components Computation on Large Power-Law Graphs},
  journal = {ACM Transactions on Architecture and Code Optimization},
  year = {2026},
  volume = {23},
  number = {2},
  pages = {1--25},
  doi = {10.1145/3803020}
}
Kostenlos starten →