并行与分布式系统中的并行拓扑排序：基于并行DFS的拓扑排序算法（Kahn算法的并行化）

算法题目描述

拓扑排序（Topological Sorting）是有向无环图（DAG）的顶点的一种线性排序，使得对于每一条有向边 \((u, v)\)，顶点 \(u\) 都排在顶点 \(v\) 之前。这是一个经典的图算法问题，在并行与分布式系统中，我们可以利用并行性加速拓扑排序过程。

你提到的基于并行DFS的拓扑排序算法通常指对DFS遍历进行并行化，但更经典且易于并行化的方法是 Kahn算法 的并行变体。Kahn算法基于顶点的入度（in-degree）进行迭代，天然具有任务并行的特性。因此，本讲解将聚焦于 Kahn算法的并行化实现，它通过并行处理所有当前入度为0的顶点来加速排序。

核心问题：给定一个有向无环图（DAG），如何利用多个处理器并行地生成其拓扑排序？

算法解题过程循序渐进讲解

步骤1：理解串行Kahn算法

在深入并行版本前，必须掌握串行Kahn算法的工作原理：

1. 初始化：计算图中每个顶点的入度（即指向该顶点的边的数量）。
2. 队列初始化：将所有入度为0的顶点加入一个队列（或列表）。
3. 迭代过程：
   • 从队列中取出一个顶点 \(u\)（在串行算法中通常按顺序取出）。
   • 将 \(u\) 添加到拓扑排序的结果序列中。
   • 对于 \(u\) 的每个邻接顶点 \(v\)：
     • 将 \(v\) 的入度减1。
     • 如果减1后 \(v\) 的入度变为0，则将 \(v\) 加入队列。
4. 终止条件：当队列为空时，迭代停止。
   • 如果结果序列中的顶点数等于图中顶点总数，则成功得到拓扑排序。
   • 否则，说明图中存在环（非DAG），无法进行拓扑排序。

串行算法复杂度：时间复杂度为 \(O(V + E)\)，其中 \(V\) 是顶点数，\(E\) 是边数。

步骤2：识别并行化机会

Kahn算法的并行化潜力在于：

• 入度为0的顶点发现：在每一轮迭代中，可能存在多个入度为0的顶点，这些顶点的处理是相互独立的，因为删除一个顶点及其出边不会立即影响其他入度为0的顶点的状态（前提是这些顶点之间没有边相连，在DAG中它们可能没有直接边，但即使有，通过正确的同步机制也可以处理）。
• 入度更新操作：当一个顶点被处理时，对其所有后继顶点的入度减1操作可以并行执行。

因此，并行Kahn算法的核心思想是：在每一轮中，并行地处理所有当前入度为0的顶点。

步骤3：并行算法设计

我们假设一个共享内存的并行计算模型（如多线程），所有处理器可以访问共享的入度数组和邻接表。

数据结构：

• in_degree[v]：共享数组，存储每个顶点 \(v\) 的当前入度。
• adj_list[u]：共享数据结构，存储顶点 \(u\) 的所有后继顶点列表。
• zero_degree_set：共享容器，用于存储当前入度为0的顶点（可以是队列、列表或集合，但在并行版本中，我们通常使用一个“当前活跃集”）。
• topo_order：共享列表，用于收集拓扑排序结果。

并行算法伪代码：

1. 并行计算所有顶点的初始入度（并行遍历所有边，对每个边的目标顶点原子增加入度计数）。
2. 并行扫描所有顶点，将初始入度为0的顶点加入 zero_degree_set。
3. while zero_degree_set 非空:
    a. 当前处理器组并行处理 zero_degree_set 中的所有顶点：
        i.   每个处理器从 zero_degree_set 中获取一个顶点 u（通过工作窃取或静态分配）。
        ii.  将 u 追加到 topo_order 中（需要同步或原子操作以确保顺序一致性，但拓扑排序本身可能允许多种顺序，因此可以并发追加）。
        iii. 对于 u 的每个后继顶点 v：
             - 原子地递减 in_degree[v]（使用原子减操作，如 fetch-and-subtract）。
             - 如果递减后 in_degree[v] == 0：
                将 v 加入 new_zero_set（一个本地的临时集合，避免直接修改共享的 zero_degree_set 导致冲突）。
    b. 同步所有处理器，确保当前轮次的所有顶点处理完毕。
    c. 将 new_zero_set 合并为下一轮的 zero_degree_set（可以并行地合并到共享容器中，或使用一个共享队列，通过原子操作加入）。
4. 如果 topo_order 中的顶点数等于 V，则成功；否则报告图中有环。

步骤4：关键细节与优化

1. 原子操作：对 in_degree[v] 的递减必须是原子的，以防止多个处理器同时修改同一顶点的入度导致竞态条件。
2. 新零入度顶点收集：每个处理器在处理自己的顶点时，将新产生的入度为0的顶点暂存于本地列表 new_zero_set，待一轮结束后统一合并。这减少了在共享数据结构上的并发冲突。
3. 负载均衡：在步骤3.a.i中，可以采用动态负载均衡策略，如工作窃取（work stealing），确保每个处理器都有足够的任务处理。
4. 同步点：每一轮结束后需要一个同步点（如屏障同步），确保所有处理器都完成了当前轮次的任务，再开始下一轮。这使算法成为 层级同步并行算法（level-synchronized parallel algorithm）。
5. 环检测：如果算法结束时，已处理的顶点数少于 \(V\)，而 zero_degree_set 为空，则说明剩余顶点构成环（因为再也找不到入度为0的顶点）。并行算法可以轻松检测这一点。

步骤5：复杂度分析

• 时间复杂度：假设有 \(p\) 个处理器。在理想情况下，每一轮可以并行处理多个顶点。最坏情况下，图是一条链，每次只能处理一个顶点，并行算法退化为串行，时间复杂度为 \(O(V)\)。在最好的情况下（如一个有许多源节点的图），第一轮就能处理大量顶点。平均时间复杂度依赖于图的深度和宽度，通常为 \(O(V/p + D)\)，其中 \(D\) 是图的深度（最长路径长度），因为每一轮至少需要 \(D\) 步同步。
• 空间复杂度：与串行算法相同，为 \(O(V + E)\)，加上并行所需的临时集合，额外空间为 \(O(V)\)。

步骤6：实例演示

考虑一个简单的DAG：
顶点：A, B, C, D, E
边：A→B, A→C, B→D, C→D, D→E

初始入度：A:0, B:1, C:1, D:2, E:1
第1轮：zero_degree_set = {A}

• 并行处理A（只有一个顶点，但演示并行逻辑）：
  • 移除A，加入topo_order。
  • 更新后继：B入度变0，C入度变0。将B、C加入new_zero_set。
    合并后，zero_degree_set = {B, C}

第2轮：zero_degree_set = {B, C}

• 并行处理B和C（两个处理器可以同时工作）：
  • 处理器1处理B：移除B，加入topo_order；更新D入度从2变为1（不为0）。
  • 处理器2处理C：移除C，加入topo_order；更新D入度从1变为0，将D加入new_zero_set。
    合并后，zero_degree_set = {D}

第3轮：zero_degree_set = {D}

• 处理D：移除D，加入topo_order；更新E入度从1变为0，将E加入new_zero_set。
  合并后，zero_degree_set = {E}

第4轮：zero_degree_set = {E}

• 处理E：移除E，加入topo_order；无后继。
  合并后，zero_degree_set = {}

结果：topo_order = [A, B, C, D, E]（注意B和C的顺序可能互换，因为它们是并行处理的，但都保证在D之前，这是一种合法的拓扑排序）。

步骤7：扩展与变体

• 分布式环境：在分布式系统中，图顶点分布在不同机器上。此时需要跨机器通信来传递入度更新消息。可以采用类似BSP（Bulk Synchronous Parallel）模型，每一轮同步交换消息。入度为0的顶点由各自所在的机器处理，并向其后继顶点所在的机器发送入度减少的消息。
• 无同步并行：可以通过更细粒度的锁或无锁数据结构（如并发队列）来实现异步处理，减少同步开销，但算法逻辑会更复杂。
• 动态图：如果图是动态变化的（边添加/删除），需要维护入度并动态更新zero_degree_set，这涉及更复杂的并行数据结构和一致性协议。

总结

并行化Kahn算法通过层级同步的方式，在每一轮中并行处理所有当前入度为0的顶点，充分利用了DAG中可并行任务的天然特性。关键点包括使用原子操作安全更新入度、每轮同步收集新产生的零入度顶点，以及负载均衡策略。该算法在共享内存多核系统中能有效加速拓扑排序，尤其适用于宽而浅的DAG。