EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Parallel Strong Connectivity Based on Faster Reachability

Letong Wang, Xiaojun Dong, Yan Gu, Yihan Sun

Proceedings of the ACM on Management of Data · 13.06.2023 · 1 (2) · 1-29

DOI: 10.1145/3589259 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 20.06.2023. Verfasst von Letong Wang und 3 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 112 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Computing strongly connected components (SCC) is among the most fundamental problems in graph analytics. Given the large size of today's real-world graphs, parallel SCC implementation is increasingly important. SCC is challenging in the parallel setting and is particularly hard on large-diameter graphs. Many existing parallel SCC implementations can be even slower than Tarjan's sequential algorithm on large-diameter graphs. To tackle this challenge, we propose an efficient parallel SCC implementation using a new parallel reachability approach. Our solution is based on a novel idea referred to as vertical granularity control (VGC). It breaks the synchronization barriers to increase parallelism and hide scheduling overhead. To use VGC in our SCC algorithm, we also design an efficient data structure called the parallel hash bag. It uses parallel dynamic resizing to avoid redundant work in maintaining frontiers (vertices processed in a round). We implement the parallel SCC algorithm by Blelloch et al. (J. ACM, 2020) using our new parallel reachability approach. We compare our implementation to the state-of-the-art systems, including GBBS, iSpan, Multi-step, and our highly optimized Tarjan's (sequential) algorithm, on 18 graphs, including social, web, k-NN, and lattice graphs. On a machine with 96 cores, our implementation is the fastest on 16 out of 18 graphs. On average (geometric means) over all graphs, our SCC is 6.0× faster than the best previous parallel code (GBBS), 12.8× faster than Tarjan's sequential algorithms, and 2.7× faster than the best existing implementation on each graph. We believe that our techniques are of independent interest. We also apply our parallel hash bag and VGC scheme to other graph problems, including connectivity and least-element lists (LE-lists). Our implementations improve the performance of the state-of-the-art parallel implementations for these two problems.

Förderung

  • National Science Foundation

Zitieren

APA

Wang, L., Dong, X., Gu, Y., & Sun, Y. (2023). Parallel Strong Connectivity Based on Faster Reachability. Proceedings of the ACM on Management of Data, 1(2), 1-29. https://doi.org/10.1145/3589259

Vancouver

Wang L, Dong X, Gu Y, Sun Y. Parallel Strong Connectivity Based on Faster Reachability. Proceedings of the ACM on Management of Data. 2023;1(2):1-29. doi:10.1145/3589259

BibTeX
@article{Wang2023,
  author = {Wang, Letong and Dong, Xiaojun and Gu, Yan and Sun, Yihan},
  title = {Parallel Strong Connectivity Based on Faster Reachability},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2023},
  volume = {1},
  number = {2},
  pages = {1--29},
  doi = {10.1145/3589259}
}
Kostenlos starten →