可证明并行双连通性算法的快速和空间高效性

(CC) is a maximal subset in 𝑉 such that every two verticesin it are connected by a path. A biconnected component(BCC) (or blocks) is a maximal subset 𝐶 ⊆ 𝑉 such that𝐶 is connected and remains connected after removing anyvertex 𝑣 ∈ 𝐶. In this paper, we use BCC (or CC) for both thebiconnected (or connected) component in the graph and theproblem of computing all BCCs (or CCs). BCC has extensiveapplications such as planarity testing [8, 24, 46], centralitycomputation [48, 59, 60], and network analysis [7, 56].Sequentially, the Hopcroft-Tarjan algorithm [45] for BCCuses 𝑂(𝑛 + 𝑚) work. However, this algorithm requires gen-erating a spanning tree of 𝐺 based on the depth-first search(DFS), which is considered hard to be parallelized [57]. Later,Tarjan and Vishkin proposed the canonical parallel BCC al-gorithm [65]. It uses an arbitrary spanning tree (AST) (aspanning tree with any possible shape) of the graph insteadof the depth-first tree. Tarjan-Vishkin algorithm has𝑂(𝑛+𝑚)optimal work (number of operations) and polylogarithmicspan (longest dependent operations), assuming an efficientparallel CC algorithm.Although the Tarjan-Vishkin algorithm is theoreticallyconsidered “optimal” in work and span, significant chal-lenges still remain in achieving a high-performance imple-mentation in practice. The main issue in Tarjan-Vishkin isspace-inefficiency. Tarjan-Vishkin generates an auxiliarygraph 𝐺′ = (𝑉 ′, 𝐸′) (which we refer to as the skeleton),where every edge 𝑒 ∈ 𝐸 maps to a vertex in 𝑉 ′. Tarjan andVishkin showed that computing CC on 𝐺′ gives the BCCon 𝐺, and we refer to this step as the connectivity phase.This skeleton-connectivity framework is adopted in manylater papers. Such algorithms first generate a skeletonas anauxiliary graph 𝐺′ from 𝐺, and then finds the CCs on 𝐺′ thatreflect BCC information on the input graph𝐺. Unfortunately,in Tarjan-Vishkin, generating the skeleton𝐺′ and computingCC on 𝐺′ take 𝑂(𝑚) extra space, which greatly increases thememory usage and slows down the performance.In practice, most existing parallel BCC implementationsalso follow the skeleton-connectivity framework but over-come the space issue by using other skeletons based onbreadth-first search (BFS) trees [25, 26, 29, 31, 40, 64, 68].These algorithms either use skeletons with 𝑂(𝑛) size [25, 26,29, 40, 68] or maintain implicit skeletons with 𝑂(𝑛) auxiliaryspace [31, 64]. We say a BCC algorithm is space-efficientif it uses 𝑂(𝑛) auxiliary space (other than the input graph).However, since computing BFS has span proportional tothe graph, these BFS-based algorithms can be fast on small-diameter graphs (e.g., social and web graphs), but have poorperformance on large-diameter graphs (e.g., 𝑘-nn and road520可证明快速且空间高效的并行双连通性0Xiaojun Dong UCRiversidexdong038@ucr.edu0Letong Wang UCRiversidelwang323@ucr.edu0Yan Gu UCRiversideygu@cs.ucr.edu0Yihan Sun UCRiversideyihans@cs.ucr.edu0摘要计算图的双连通分量（BCC）是一个基本的图问题。经典的并行BCC算法是Tarjan-Vishkin算法，对于具有A个顶点和A条边的图，其具有A(A+A)的最优工作量和对数级的跨度。然而，Tarjan-Vishkin算法在实践中并不常用。我们认为原因是其空间效率低下（它使用A(A)的额外空间）。在实践中，现有的并行实现是基于广度优先搜索（BFS）。由于BFS的跨度与图的直径成比例，现有的并行BCC实现在直径较大的图上性能较差，并且在许多实际图上比顺序算法慢。我们提出了第一个具有最优工作量、对数级跨度且空间高效的并行双连通性算法（FAST-BCC）。我们的算法基于输入图的任意生成树创建一个骨架图。然后我们利用骨架的连通性信息计算原始输入的双连通性。我们仔细分析了我们算法的正确性，这是非常不平凡的。我们实现了FAST-BCC并将其与现有的实现进行了比较，包括GBBS、Slota和Madduri的算法以及顺序的Hopcroft-Tarjan算法。我们在一台96核的机器上对27个具有不同边分布的图进行了测试。FAST-BCC在所有图上都是最快的。平均而言（几何平均），FAST-BCC比每个图上最好的现有基准快3.1倍。0CCS概念：•计算理论→共享内存算法；图算法分析；并行算法。0关键词：并行算法，图算法，双连通性，连通性，图分析01 引言0PPoPP’23，2023年2月25日至3月1日，加拿大蒙特利尔，QC，©2023年版权由所有者/作者所有。ACM ISBN979-8-4007-0015-6/23/02。https://doi.org/10.1145/3572848.35774830本作品采用知识共享署名国际4.0许可协议。10.524816 32 >32530我们的 GBBS SM'14 SEQ 我们的 GBBS SM'14 SEQ0社交0YT 5.88 4.36 3.15 1.000HH5 7.01 1.14 n 1.000OK 30.51 19.91 5.66 1.00 CH5 4.11 0.37 n 1.000LJ 17.92 11.77 n 1.00 GL2 6.24 1.64 n 1.000TW 34.21 17.42 2.40 1.00 GL5 8.53 1.44 n 1.000FT 39.26 18.93 10.22 1.00 GL10 10.59 4.31 n 1.000平均值21.23 12.75 4.57 1.00 GL15 11.88 5.91 n 1.000网络0GG 8.92 5.65 n 1.00 GL20 11.84 6.88 n 1.000SD 29.74 16.46 n 1.00 COS5 14.16 6.86 n 1.000CW 30.37 17.52 n 1.00 平均值8.68 2.42 - 1.000HL14 32.46 19.96 n 1.000SQR 18.50 1.59 10.56 1.000HL12 33.99 29.15 n 1.00 REC 12.48 0.36 3.02 1.000平均值24.53 15.68 - 1.00 SQR' 8.06 0.85 n 1.000道路0CA 5.15 0.55 n 1.00 REC' 7.81 0.48 n 1.000美国6.69 0.49 0.60 1.00 Chn7 11.97 0.04 0.08 1.000GE 10.77 1.43 2.44 1.00 Chn8 11.97 0.04 0.06 1.000平均值7.18 0.73 1.21 1.00 平均值11.30 0.27 0.18 1.000总平均值12.89 2.50 0.96 1.000平均值=几何平均数n=0图1.并行BCC算法相对于顺序Hopcroft-Tarjan算法[45]在96个核心（192个超线程）上的加速比热图。较大/绿色表示较好。数字表示并行算法比顺序Hopcroft-Tarjan算法快多少倍（<1表示更慢）。两个基准算法来自[31, 64]。完整的结果请参见表2。0在我们的实验中，我们观察到现有的并行实现在许多真实世界的图上甚至比顺序的Hopcroft-Tarjan算法更慢（参见图1中的GBBS [31]和SM'14[64]）。在本文中，我们提供了第一个空间高效（�（�）辅助空间）的并行双连通性算法，该算法具有高效的�（� +�）工作和对数级别的跨度。我们的骨架�'基于任意生成树（AST）。与Tarjan-Vishkin不同，我们的�'是�的子图，并且可以在�（）辅助空间中隐式维护。关键思想是仔细识别一些fence边，这些边指示BCC的“边界”。在高层次上，我们将所有图边分为fence树边，普通（非fence）树边，反向边和交叉边。我们的骨架�'包含普通树边和交叉边。使用�（�）空间，我们可以高效地确定�中每条边的类别。在处理骨架时，我们使用输入图�，但跳过fence和反向边。我们展示了�的BCC信息可以从�'的CC信息加上一些简单的后处理来构建。由于我们的算法基于“Fencing an Arbitrary SpanningTree”，我们将我们的算法称为FAST-BCC。有关FAST-BCC的更多细节，请参见图2。我们注意到，从概念上讲，我们的算法很简单，但正确性分析非常复杂。我们实现了理论上高效的FAST-BCC算法，并将其与最先进的并行BFS-basedBCC实现GBBS [31]和SM'14[64]以及顺序的Hopcroft-Tarjan算法进行了比较。我们测试了27个图，包括社交图、网络图、道路图、�-NN图和合成图，它们的大小和边分布差异显著。图和结果的详细信息请参见文中。0在表2中给出了详细结果。我们还在图1中显示了相对运行时间，相对于顺序Hopcroft-Tarjan进行了归一化。在一台具有96个核心的机器上，FAST-BCC在所有测试图上都是最快的。我们使用几何平均数来比较多个图之间的“平均”性能。由于工作和空间效率，我们的算法在一个核心上运行时与Hopcroft-Tarjan竞争（平均慢2.8倍）。对数级别的跨度使得所有类型的图都具有良好的并行性（平均自相对加速比为15-66倍）。在直径较小的图（社交图和网络图）上，尽管GBBS和SM'14也实现了良好的并行性，FAST-BCC仍然比两者中最好的快1.2-2.1倍，并且比顺序Hopcroft-Tarjan快5.9-39倍。对于直径较大的图（道路、�-NN、网格和链图），现有的基于BFS的实现可能比Hopcroft-Tarjan表现更差。由于跨度较低，FAST-BCC比GBBS快1.7-295倍（平均10倍），比顺序Hopcroft-Tarjan快4.1-18.5倍（平均9.2倍）。在所有图上，FAST-BCC的平均速度比三个现有实现中最好的速度快3.1倍。我们的代码公开可用[36]。我们在本文的完整版本中提供了更多结果和分析[37]。02 预备知识计算模型。我们使用工作-跨度（或工作-深度）模型来分析并行算法中的二叉分叉式并行性[15,30]，该模型最近在许多并行算法的论文中使用[3, 10, 11, 13,14, 16-22, 33-35, 42, 43, 62,71]。我们假设一组共享公共内存的线程。一个进程可以并行地fork两个子软件线程进行工作。当两个子线程都完成时，父进程继续执行。算法的工作是计算中依赖指令的总数，而跨度（深度）是计算中依赖指令序列的最长长度。如果一个算法的工作与最佳顺序算法的工作渐近相同，则称该算法是工作高效的。在实践中，我们可以使用随机化的工作窃取调度器[6,23]执行计算。我们假设单位成本的原子操作compare_and_swap(�, � old, �new)（或CAS），它原子地读取由�指向的内存位置，并将值�new写入其中，如果当前值为�old，则返回true，否则返回false。符号。给定一个无向图� =(�, �)，我们使用� = |�|，� = |�|。�的直径为�的直径，� -�是�和�之间的一条边。CC和BCC在第1节中定义。关节点（或割顶）是一个顶点，删除它会增加CC的数量。桥（或割边）是一条边，删除它会增加CC的数量。一个连通图�的生成树�是�的一个生成子图，不包含环。如果�是不连通的，则类似地定义生成森林。为了简单起见，我们假设�是连通的，但我们的算法和实现适用于任何图。给定一个图�和一个根生成树540� = (�, �)：输入图� = (�, � �)：�中的一棵生成树0�,�,�,�, �,�,�,�,�,�,�', �',�' ∙ ∙ ∙ ∈ �：顶点在�中0� - � ∈ �：�中的一条边� �,� �：�中的一个BCC0� �：�的子树在�中��：�的BCC头部0� (�)：�在�中的父节点� ～ �：�上的一条树路径0� = � - � - ∙ ∙ ∙ ：路径�'：骨架0栅栏边：(� (�), �) ∈ � �,  � (�,�) ∈ �，使得� ∈ � �且� � � � (�)0（�的子树中没有边逃逸出�（�）的子树）0普通边：(� (�), �) ∈ � �，(� (�), �)不是栅栏边，反向边，交叉边：� \ �中的边，按照通常的定义，骨架�' = (�, �')在FAST-BCC中：�' ={普通和交叉边}0表1. 本文中的符号和术语。0树�中的边是树边，如果它在�中。非树边是反向边，如果一个端点是另一个端点的祖先，否则是交叉边。图2的第3步给出了一个示例。如果�是BFS树，则没有反向边；如果�是DFS树，则没有交叉边。我们使用� ～�来表示�和�之间的树路径在�上。我们将顶点�的父节点表示为�将�的子树表示为��。本文中使用的符号见表1。我们在Tarjan-Vishkin中使用�(�(�)的概率很高（whp）来表示�(��(�))，其中�(�)为��的概率至少对于�≥1。 Euler tour技术（ETT）。ETT是Tarjan和Vishkin在他们的BCC算法中提出的一种根据生成树的方法。后来，ETT成为顺序和并行环境中广泛使用的原语，包括计算几何[2]，图算法[5, 28,67]，维护子树或树路径和[30]等等。ETT在Tarjan-Vishkin中是必需的，因为当为图生成任意生成树（例如，从CC算法）时，它没有根，因此我们没有顶点的父子信息。给定一个具有�-1条边的未根化树�，ETT找到�的欧拉遍历，它是一个遍历�中的每条边恰好两次（每个方向一次）的循环。ETT首先在2�-2个有向树边上构建一个链表，并在其上运行列表排名。我们建议读者参考并行算法的教材[47,58]，以了解有关ETT的更多细节。使用来自[15,44]的半排序算法和来自[15]的列表排名，ETT的期望工作量为�(�)，期望跨度为�(log�)。给定�，我们可以将任何顶点设置为�的根，并使用ETT确定边的方向。然后我们可以确定任何顶点的父节点，以及�中的边是树边、反向边还是交叉边，工作量为�(1)。03个现有的BCC算法0本节回顾了现有的BCC算法和实现。我们将使用骨架连接框架来描述现有的BCC算法。骨架阶段从�生成一个辅助图�'，这是一个骨架。然后，连通性阶段在�'上计算连通性以构建�的BCCs。现有的BCC算法可以根据生成骨架�'的方式进行分类。Hopcroft-Tarjan算法使用基于DFS的骨架；Tarjan-Vishkin算法基于一个0任意生成树（AST）；几乎所有其他BCC算法（见第3.3节）使用基于BFS的骨架。03.1 Hopcroft-Tarjan算法0顺序地，Hopcroft-TarjanBCC算法[45]使用深度优先搜索（DFS）树�，其工作量为�(�+�)。基于�，为每个顶点分配了两个标签first[∙]和low[∙]。first[�]是�中每个顶点的先序号。low[�]给出了任何顶点�∈��通过非树边与�相连的最早（最小的先序号）顶点和�本身。更正式地说，0low[�]=min{�1[�]|�∈�是以�为根的子树}�1[�]=min{{first[�]}∪{first[�']|(�,�')��}}0为了计算BCCs，还维护了一个额外的栈。每次访问一个新的边，它都被推入栈中。当找到一个关节点�(�)时（�的low[�]≥first[�(�)]），边从栈中弹出，直到弹出�-�(�)。这些边和相关的顶点形成一个BCC。从概念上讲，Hopcroft-Tarjan中的骨架是DFS树，但没有“围栏边”�-�(�)当low[�]≥first[�(�)]。这个观点也启发了我们的BCC算法。03.2 Tarjan-Vishkin算法0Hopcroft-Tarjan使用DFS树作为骨架，但DFS本质上是串行的，很难并行化[57]。为了并行化BCC，Tarjan-Vishkin算法[65]使用任意生成树（AST）代替DFS树。这棵生成树�可以通过任何并行CC算法获得。然后，算法使用ETT（也是该论文中提出的）来根据�使树�成为根（见第2节）。然后算法构建一个骨架�'=(�,�')并在其上运行一个连通性算法。我们在完整论文[37]中更详细地描述了�'，这里只简要回顾一下。�'中的顶点对应于�1中的边。为了确定�'中的边，算法为每个顶点使用四个标签（first[∙]、last[∙]、low[∙]和high[∙]）。这里的first[�]和last[�]是顶点�在欧拉遍历中的第一次和最后一次出现（注意这与Hopcroft-Tarjan中的first[∙]不同，但在概念上是等价的）。low[∙]与Hopcroft-Tarjan中定义的相同，而high[∙]则对称定义：0high[�]=max{�2[�]|�∈�是以�为根的子树}�2[�]=max{{first[�]}∪{first[�']|(�,�')��}}0使用ETT可以在�(�+�)的期望工作量和�(log�)的span下计算所有标签，whp。然后，Tarjan-Vishkin在�'上找到CCs来计算�的BCCs。然而，Tarjan-Vishkin中的�'可能很大，使得算法不太实用。假设存在高效的ETT和并行CC算法，Tarjan-Vishkin使用�(�+�)的最优期望工作量和多对数级的span。然而，空间效率不高阻碍了Tarjan-Vishkin的实用性，因为�'包含�(�)条边。在我们的实验中，Tarjan-Vishkin最多需要0在后续的一篇论文[39]中，证明了�'中的顶点数可以减少到�(�)，但|�'|仍然是�(�)。3.3Other Existing Algorithms / ImplementationsBefore Tarjan-Vishkin, Savage and JáJá [61] showed a par-allel BCC algorithm based on matrix-multiplication with𝑂(𝑛3 log𝑛) work. Tsin and Chin [66] gave an algorithm thatuses an AST-based skeleton. It is quite similar to Tarjan-Vishkin, but uses 𝑂(𝑛2) work.To achieve space-efficiency, many later parallel BCC algo-rithms use BFS-based skeletons [25, 26, 29, 31, 40, 50, 64, 68].Many of them use the similar idea of sparse certificates [27].BCC is much simpler with a BFS tree—all non-tree edgesare cross edges with both endpoints in the same or adja-cent levels. Cong and Bader’s TV-filter algorithm [29] usesthe skeleton as the BFS tree 𝑇 and an arbitrary spanningtree/forest for 𝐺 \ 𝑇 (𝑂(𝑛) total size). Slota and Madduri’salgorithms [64] and Dhulipala et al.’s algorithm [31] use theskeletons as the input graph𝐺 excluding𝑂(𝑛) vertices/edges.The other algorithms [25, 26, 40, 68] use a BFS tree as theskeleton, and compute connectivity dynamically. All thesealgorithms are space-efficient. Their skeleton graphs eitherhave 𝑂(𝑛) size [25, 26, 29, 40, 68] or can be implicitly repre-sented using 𝑂(𝑛) information [31, 64]. However, the spanto generate a BFS tree is proportional to the diameter of thegraph, which is inefficient for large-diameter graphs.3.4Space-Efficient BCC RepresentationSince some vertices (articulation points) appear in multipleBCCs (see Fig. 2 as an example), we need a representation ofall BCCs in a space-efficient manner (𝑂(𝑛) space). We use acommonly used representation [11, 31, 40] in our algorithm.Given a spanning tree 𝑇, we assign a label for each vertexexcept for the root of 𝑇, indicating which BCC this vertexis in. For all vertices with the same label, we find anothervertex called the component head (see details in Sec. 4.1)attached to this label. All vertices with the same label and thecorresponding component head form a BCC. An example ofthis representation is given in Fig. 2. It is easy to see that thisrepresentation uses 𝑂(𝑛) space since we have 𝑛 − 1 labelsfor all vertices and at most 𝑛 − 1 component heads.Algorithm 1: The FAST-BCC algorithmInput: An undirected graph 𝐺 = (𝑉, 𝐸)Output: The labels 𝑙[·] for vertices, and the component headfor each BCC1 Compute the spanning forest 𝐹 of 𝐺⊲ First CC2 Root all trees in 𝐹 using the Euler tour technique ⊲ Rooting3 Compute tags (e.g., low, high) of each vertex based on theEuler tour⊲ Tagging4 Compute the vertex label 𝑙[·] using connectivity on 𝐺 withedges satisfying InSkeleton(𝑢, 𝑣) = true⊲ Last CC5 ParallelForEach 𝑢 ∈ 𝑉 with 𝑙[𝑢] ≠ 𝑙[𝑝(𝑢)]6Set the component head of 𝑙[𝑢] as 𝑝(𝑢)7 Function InSkeleton(𝑢, 𝑣)⊲ Decide if 𝑢–𝑣 is in skeleton 𝐺′8if (𝑢, 𝑣) is a tree edge then9return ¬ Fence(𝑢, 𝑣) and ¬ Fence(𝑣,𝑢)10else return ¬ Back(𝑢, 𝑣) and ¬ Back(𝑣,𝑢)11 Function Fence(𝑢, 𝑣)⊲ Decide if tree edge is fence edge12return first[𝑢] ≤ low[𝑣] and last[𝑢] ≥ high[𝑣]13 Function Back(𝑢, 𝑣) ⊲ Decide if non-tree edge is back edge14return first[𝑢] ≤ first[𝑣] and last[𝑢] ≥ first[𝑣]4The FAST-BCC AlgorithmIn this section, we present our FAST-BCC algorithm withanalysis. Our algorithm is the first parallel BCC algorithmthat is work-efficient, space-efficient, and has polylogarith-mic span. Recall that BFS-based algorithms are space-efficient,but BFS itself does not parallelize well. Tarjan-Vishkin isbased on AST and is highly parallel, but generating the skele-ton is space-inefficient. To achieve both high parallelism andspace efficiency, we need novel algorithmic insights.Interestingly, our key idea is to revisit the sequential DFS-based Hopcroft-Tarjan algorithm (Sec. 3.1). Although DFSis inherently sequential, the insights in Hopcroft-Tarjan in-spire our parallel BCC algorithm. The (implicit) skeletonin Hopcroft-Tarjan is simple and the skeleton size is small(𝑂(𝑛)). Unlike many later parallel BCC algorithms with thehigh-level ideas to combine cycles (based on Fact 4.2), theidea in Hopcroft-Tarjan is the “fencing” condition as follows.When computing the CC on the skeleton 𝐺′ (the DFS tree)and traversing the edge from 𝑣 to 𝑝(𝑣), the CC on𝐺′ (BCC on𝐺) is fenced if low[𝑣] ≥ first[𝑝(𝑣)]. This condition partitionsthe DFS tree 𝑇 into multiple CCs that correspond to BCCsin 𝐺. Note that 𝐺′ in Hopcroft-Tarjan only contains edgesfrom the DFS tree, because there are no cross edges in DFStrees and all back edge information is captured by low[·].Now we try to generalize this idea to an arbitrary span-ning tree (AST). Directly using the “fencing” condition inHopcroft-Tarjan does not work since we need to deal withcross edges. Note that a fence edge𝑣–𝑝(𝑣) in Hopcroft-Tarjanmeans that vertices in 𝑢’s subtree do not have an edge thatescapes (i.e., the other endpoint is outside) 𝑝(𝑢)’s subtree. Wedefine our fence edges also based on this condition. More for-mally, we say a tree edge (𝑢, 𝑣) where𝑢 = 𝑝(𝑣) is a fence edge550与我们的FAST-BCC或GBBS相比，它的额外空间是它们的11倍。在我们的1.5TB内存机器上，Tarjan-Vishkin在处理Clueweb图[54]时会耗尽内存，尽管存储图只需要大约300GB（详见完整版本[37]中的讨论）。大量的空间使用禁止在大多数多核机器上运行Tarjan-Vishkin的大规模图。即使对于小图，高空间使用也会增加内存占用并降低性能。一些现有的BCC实现（例如GBBS[31]和TV-filter[29]）也被描述为Tarjan-Vishkin算法，可能是因为它们也使用了骨架连接框架。我们注意到它们的正确性依赖于基于BFS的骨架（即稀疏证书[27]），我们将它们与其他几种算法一起归类如下。4.2Correctness for the FAST-BCC AlgorithmWe now prove the correctness of our algorithm. Note that ouralgorithm will identify the spanning forest in the first stepand deal with each CC respectively. For simplicity, through-out the section, we focus on one CC in 𝐺.In the following, when we use the concepts about a span-ning tree of the graph (e.g., root, parent, child, and subtree),we refer to the specific spanning tree identified in Step 1of our algorithm, and use 𝑇 to represent it. Recall that 𝑇𝑢denotes the subtree rooted at vertex 𝑢, and 𝑢 ~𝑣 denotes thetree path on 𝑇 from 𝑢 to 𝑣. Some other notation is givenin Tab. 1. In a spanning tree, we say a node 𝑢 is shallower(deeper) than 𝑣 if 𝑢 is closer (farther) to the root than 𝑣. Weuse node and vertex interchangeably.We note that although Alg. 1 is simple, the correctnessproof is sophisticated. We show the relati