Parallel Strong Connectivity Based on Faster Reachability
Parallel Strong Connectivity Based on Faster Reachability
复制标题
DOI：
10.1145/3589259
复制
发表时间：
2023-03
期刊：
影响因子：
--
通讯作者：
Letong Wang;Xiaojun Dong;Yan Gu;Yihan Sun
中科院分区：
文献类型：
--
作者：
Letong Wang;Xiaojun Dong;Yan Gu;Yihan Sun
计算强连通分量（SCC）是图分析中最基本的问题之一。鉴于当今现实世界中图的规模庞大，并行SCC实现变得越来越重要。在并行环境下，SCC具有挑战性，在大直径图上尤其困难。许多现有的并行SCC实现方案在大直径图上甚至可能比Tarjan的顺序算法还慢。为了应对这一挑战，我们利用一种新的并行可达性方法提出了一种高效的并行SCC实现方案。我们的解决方案基于一种被称为垂直粒度控制（VGC）的新颖理念。它打破了同步障碍以提高并行性并隐藏调度开销。为了在我们的SCC算法中使用VGC，我们还设计了一种高效的数据结构，称为并行哈希袋。它使用并行动态调整大小来避免在维护边界（一轮中处理的顶点）时的冗余工作。我们使用我们的新并行可达性方法实现了Blelloch等人（《美国计算机协会杂志》，2020年）提出的并行SCC算法。我们在18个图上，包括社交图、网络图、k - 近邻图和格图，将我们的实现与最先进的系统进行比较，这些系统包括GBBS、iSpan、多步算法以及我们高度优化的Tarjan（顺序）算法。在一台具有96个核心的机器上，我们的实现在18个图中的16个图上是最快的。在所有图上的平均（几何平均）速度方面，我们的SCC比之前最好的并行代码（GBBS）快6.0倍，比Tarjan的顺序算法快12.8倍，并且在每个图上比现有的最佳实现快2.7倍。我们相信我们的技术具有独立的研究价值。我们还将我们的并行哈希袋和VGC方案应用于其他图问题，包括连通性和最小元素列表（LE - 列表）。我们的实现提高了这两个问题的最先进并行实现的性能。
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.