并行与分布式系统中的并行最大流算法：基于预流推进的Goldberg-Tarjan算法并行化
字数 3080 2025-12-22 20:04:16

并行与分布式系统中的并行最大流算法：基于预流推进的Goldberg-Tarjan算法并行化

1. 问题描述

最大流问题是图论中的一个经典优化问题。给定一个有向图 \(G=(V, E)\)，每条边 \(e \in E\) 有一个非负容量 \(c(e)\)，以及一个源点 \(s\) 和一个汇点 \(t\)，目标是找到一个从 \(s\) 到 \(t\) 的流，使得在满足每条边容量限制和流量守恒（除 \(s\) 和 \(t\) 外每个节点的流入等于流出）的前提下，从 \(s\) 流出的总流量（即流值）最大。

在并行与分布式计算环境中，我们希望利用多处理器或分布式节点来加速最大流的计算。Goldberg-Tarjan 的预流推进（Push-Relabel）算法是最高效的串行最大流算法之一，其最坏时间复杂度为 \(O(|V|^3)\)，但实际性能优异。并行化该算法面临的主要挑战是其固有的数据依赖和全局操作（如“重贴标签”操作需要知道邻居的最小高度）。本问题要求设计一个能有效并行化的预流推进算法版本，在保持正确性的同时，最大化并行度。

2. 预备知识：串行Goldberg-Tarjan预流推进算法

在深入并行化之前，必须理解串行算法的核心思想。算法维护两个关键变量：

  • 预流（Preflow）：允许节点的流入大于流出（即存在“盈余”），但不允许流出大于流入（违反容量限制）。
  • 高度（或距离标签）：为每个节点 \(u\) 分配一个非负整数高度 \(h(u)\)，初始时 \(h(s) = |V|\)，\(h(t) = 0\)，其他节点 \(h(u) = 0\)。算法保证：如果存在从 \(u\) 到 \(v\) 的残留边，则 \(h(u) \leq h(v) + 1\)。

主要操作：

  1. 推进（Push）：对一条边 \((u, v)\)，如果节点 \(u\) 有盈余（excess flow > 0），且 \(h(u) = h(v) + 1\)，并且该边残留容量 \(r(u, v) > 0\)，则可以将流量从 \(u\) 推送到 \(v\)。推进量是 \(\min(\text{excess}(u), r(u, v))\)。
    • 如果推送后 \(r(u, v)\) 变为 0，称为饱和推进；否则为非饱和推进。
  2. 重贴标签（Relabel）：如果节点 \(u\) 有盈余，但没有允许推送的邻接节点（即所有邻接节点的高度都不满足 \(h(v) = h(u) - 1\) 且残留容量 > 0），则将 \(h(u)\) 增加为 \(\min\{ h(v) \mid (u,v) \in E_f \} + 1\)，其中 \(E_f\) 是残留图中的边。

算法流程（串行）：

  • 初始化：从 \(s\) 出发，将所有 \((s, v)\) 的边推送到容量上限，使邻居节点获得盈余。
  • 循环：重复选择有盈余的节点（除 \(s\) 和 \(t\) 外），尝试对其进行推进或重贴标签，直到没有盈余节点为止。

正确性关键：高度函数确保不存在从 \(s\) 到 \(t\) 的可增广路径时，算法终止。此时，预流已转化为最大流。

3. 并行化挑战

  1. 数据竞争：并行推进可能导致同时对同一条边的残留容量进行修改，造成不一致。
  2. 全局同步：重贴标签操作需要知道所有邻居的当前高度，并行环境下高度可能被其他线程修改。
  3. 活跃节点调度：串行算法通常用队列管理有盈余的节点，并行时需要高效且无锁的调度策略。
  4. 终止检测：需要确定所有节点无盈余（除 \(s\) 和 \(t\)），在并行环境下需谨慎处理。

4. 并行化设计思路

一种常用的并行化方法是基于颜色（或优先级）的并行预流推进。其主要思想是将节点分为不同的组，按顺序处理，以降低数据依赖。

步骤 1：图划分与数据分布

  • 将图 \(G\) 划分为 \(P\) 个子图，每个处理器（或线程）负责一个子图的节点和关联的边。
  • 边可以按照有向边的起点或终点所在处理器进行分配，通常采用起点划分，这样每个处理器负责其“拥有”的节点的出边。

步骤 2：并行初始化

  • 并行初始化高度：\(h(s) = |V|\)，\(h(t) = 0\)，其他节点为 0。
  • 并行从源点 \(s\) 推送：每个处理器检查从 \(s\) 出发的边（如果 \(s\) 在其分区内），并饱和推送流量到邻居，更新邻居的盈余值。
  • 将获得盈余的节点（除 \(t\) 外）加入“活跃节点”集合。

步骤 3：基于高度的并行迭代

核心循环：重复以下步骤直到无活跃节点。

（1）全局重贴标签（可选，周期性执行）

  • 周期性（如每 \(k\) 次迭代后）通过并行 BFS 从 \(t\) 出发在残留图中计算精确距离标签，以加快收敛。这可以替换局部重贴标签，减少竞争。

（2）局部推进与重贴标签

  • 将活跃节点按高度降序排列（或使用桶结构），因为更高节点更可能将流量推向低处，最终流向 \(t\)。
  • 并行处理同一高度桶内的节点：
    a. 推进阶段：对每个节点 \(u\) 在桶中，尝试对其所有出边进行推送。推送时需原子地减少残留容量、增加邻居盈余。如果邻居变为活跃且高度满足条件，则将其加入合适的高度桶。
    b. 重贴标签阶段：如果 \(u\) 仍有盈余，则计算其最小邻居高度（原子读取），然后原子地更新 \(h(u)\) 为该值加 1，并将 \(u\) 移到新高度对应的桶。

关键同步：

  • 每个高度桶内的节点并行处理，但不同高度桶之间顺序处理（从高到低），以避免流量反向推送到高处。
  • 对同一条边的推送操作需通过原子操作（如 compare-and-swap）或细粒度锁来保证一致性。

步骤 4：终止检测

  • 当所有高度桶为空，且全局同步后无活跃节点，则算法终止。可以使用全局归约操作（如 MPI_Allreduce）来检查是否所有处理器的活跃节点数为 0。

5. 并行算法伪代码

输入: 图 G = (V, E), 容量 c, 源 s, 汇 t
输出: 最大流值 f
初始化:
  将 V 划分为 P 个子集，每个处理器 p 负责 V_p
  并行初始化 h(s)=|V|, h(t)=0, 其他 h(u)=0
  并行从 s 推送饱和流，将获得的盈余节点加入活跃集
  将活跃节点按 h 分配到高度桶 B[0..2|V|]  // 高度不超过 2|V|

while 有活跃节点存在 do:
  for 高度 H = 最高桶 downto 1:  // 从高到低处理桶
    并行处理桶 B[H] 中的所有节点 u:
      重复直到 u 的盈余为 0 或无法推进:
        尝试推进: 对所有 (u,v) 满足 h(u)=h(v)+1 且 r(u,v)>0:
          推送量 Δ = min(excess(u), r(u,v))
          原子更新 r(u,v) -= Δ, r(v,u) += Δ
          excess(u) -= Δ, excess(v) += Δ
          如果 v 不是 s 或 t，将 v 加入 B[h(v)]
        如果 u 仍有盈余:
          重贴标签: 计算 h_min = min{ h(v) | (u,v) 在残留图中 } + 1
          原子更新 h(u) = h_min
          将 u 移至 B[h_min]
  全局同步: 通过归约检查是否所有处理器无活跃节点
  若所有处理器无活跃节点，则退出循环
end while
返回 f = excess(t)  // 流入 t 的总流量

6. 性能优化与注意事项

  • 桶结构：使用基于高度的桶，允许并行处理同一桶内的节点，同时保持高度的单调性。
  • 原子操作：对残留容量和盈余的更新需原子化，但重贴标签时的“读-计算-写”可能需要细粒度锁以避免竞态。
  • 负载均衡：由于节点度数差异，可能造成某些处理器负载过高。动态调度（如工作窃取）可用于平衡桶内节点的处理。
  • 通信开销：在分布式环境中，边可能跨越处理器，推送操作需要跨节点通信更新残留容量和盈余。可以通过异步通信和消息缓冲来隐藏延迟。

7. 复杂度与正确性

  • 正确性：并行版本维持了串行预流推进的不变式（特别是高度约束），因此最终结果正确。
  • 时间复杂度：最坏情况下与串行相同（\(O(|V|^3)\)），但实际并行度取决于图结构和高度分布。平均情况下，可达到近线性加速。
  • 空间复杂度：每个处理器需存储局部子图及相邻边界信息，总空间为 \(O(|V|+|E|)\)。

8. 总结

并行化Goldberg-Tarjan预流推进算法的核心是基于高度桶的顺序处理，它减少了数据依赖，同时允许桶内节点并行推进和重贴标签。通过细粒度的同步和原子操作保证一致性，配合周期性的全局重贴标签加速收敛，可以高效求解大规模图的最大流问题。

并行与分布式系统中的并行最大流算法：基于预流推进的Goldberg-Tarjan算法并行化 1. 问题描述 最大流问题 是图论中的一个经典优化问题。给定一个有向图 \( G=(V, E) \)，每条边 \( e \in E \) 有一个非负容量 \( c(e) \)，以及一个源点 \( s \) 和一个汇点 \( t \)，目标是找到一个从 \( s \) 到 \( t \) 的流，使得在满足每条边容量限制和流量守恒（除 \( s \) 和 \( t \) 外每个节点的流入等于流出）的前提下，从 \( s \) 流出的总流量（即流值）最大。 在并行与分布式计算环境中，我们希望利用多处理器或分布式节点来加速最大流的计算。Goldberg-Tarjan 的 预流推进（Push-Relabel）算法 是最高效的串行最大流算法之一，其最坏时间复杂度为 \( O(|V|^3) \)，但实际性能优异。并行化该算法面临的主要挑战是其固有的 数据依赖 和 全局操作 （如“重贴标签”操作需要知道邻居的最小高度）。本问题要求设计一个能有效并行化的预流推进算法版本，在保持正确性的同时，最大化并行度。 2. 预备知识：串行Goldberg-Tarjan预流推进算法 在深入并行化之前，必须理解串行算法的核心思想。算法维护两个关键变量： 预流（Preflow） ：允许节点的流入大于流出（即存在“盈余”），但不允许流出大于流入（违反容量限制）。 高度（或距离标签） ：为每个节点 \( u \) 分配一个非负整数高度 \( h(u) \)，初始时 \( h(s) = |V| \)，\( h(t) = 0 \)，其他节点 \( h(u) = 0 \)。算法保证：如果存在从 \( u \) 到 \( v \) 的残留边，则 \( h(u) \leq h(v) + 1 \)。 主要操作 ： 推进（Push） ：对一条边 \( (u, v) \)，如果节点 \( u \) 有盈余（excess flow > 0），且 \( h(u) = h(v) + 1 \)，并且该边残留容量 \( r(u, v) > 0 \)，则可以将流量从 \( u \) 推送到 \( v \)。推进量是 \( \min(\text{excess}(u), r(u, v)) \)。 如果推送后 \( r(u, v) \) 变为 0，称为 饱和推进 ；否则为 非饱和推进 。 重贴标签（Relabel） ：如果节点 \( u \) 有盈余，但没有允许推送的邻接节点（即所有邻接节点的高度都不满足 \( h(v) = h(u) - 1 \) 且残留容量 > 0），则将 \( h(u) \) 增加为 \( \min\{ h(v) \mid (u,v) \in E_ f \} + 1 \)，其中 \( E_ f \) 是残留图中的边。 算法流程 （串行）： 初始化：从 \( s \) 出发，将所有 \( (s, v) \) 的边推送到容量上限，使邻居节点获得盈余。 循环：重复选择 有盈余的节点 （除 \( s \) 和 \( t \) 外），尝试对其进行 推进 或 重贴标签 ，直到没有盈余节点为止。 正确性关键 ：高度函数确保不存在从 \( s \) 到 \( t \) 的可增广路径时，算法终止。此时，预流已转化为最大流。 3. 并行化挑战 数据竞争 ：并行推进可能导致同时对同一条边的残留容量进行修改，造成不一致。 全局同步 ：重贴标签操作需要知道所有邻居的当前高度，并行环境下高度可能被其他线程修改。 活跃节点调度 ：串行算法通常用队列管理有盈余的节点，并行时需要高效且无锁的调度策略。 终止检测 ：需要确定所有节点无盈余（除 \( s \) 和 \( t \)），在并行环境下需谨慎处理。 4. 并行化设计思路 一种常用的并行化方法是 基于颜色（或优先级）的并行预流推进 。其主要思想是将节点分为不同的组，按顺序处理，以降低数据依赖。 步骤 1：图划分与数据分布 将图 \( G \) 划分为 \( P \) 个子图，每个处理器（或线程）负责一个子图的节点和关联的边。 边可以按照 有向边 的起点或终点所在处理器进行分配，通常采用起点划分，这样每个处理器负责其“拥有”的节点的出边。 步骤 2：并行初始化 并行初始化高度：\( h(s) = |V| \)，\( h(t) = 0 \)，其他节点为 0。 并行从源点 \( s \) 推送：每个处理器检查从 \( s \) 出发的边（如果 \( s \) 在其分区内），并饱和推送流量到邻居，更新邻居的盈余值。 将获得盈余的节点（除 \( t \) 外）加入“活跃节点”集合。 步骤 3：基于高度的并行迭代 核心循环：重复以下步骤直到无活跃节点。 （1）全局重贴标签（可选，周期性执行） 周期性（如每 \( k \) 次迭代后）通过并行 BFS 从 \( t \) 出发在残留图中计算精确距离标签，以加快收敛。这可以替换局部重贴标签，减少竞争。 （2）局部推进与重贴标签 将活跃节点按高度 降序排列 （或使用桶结构），因为更高节点更可能将流量推向低处，最终流向 \( t \)。 并行处理同一高度桶内的节点： a. 推进阶段 ：对每个节点 \( u \) 在桶中，尝试对其所有出边进行推送。推送时需原子地减少残留容量、增加邻居盈余。如果邻居变为活跃且高度满足条件，则将其加入合适的高度桶。 b. 重贴标签阶段 ：如果 \( u \) 仍有盈余，则计算其最小邻居高度（原子读取），然后原子地更新 \( h(u) \) 为该值加 1，并将 \( u \) 移到新高度对应的桶。 关键同步 ： 每个高度桶内的节点并行处理，但 不同高度桶之间顺序处理 （从高到低），以避免流量反向推送到高处。 对同一条边的推送操作需通过原子操作（如 compare-and-swap ）或细粒度锁来保证一致性。 步骤 4：终止检测 当所有高度桶为空，且全局同步后无活跃节点，则算法终止。可以使用全局归约操作（如 MPI_Allreduce ）来检查是否所有处理器的活跃节点数为 0。 5. 并行算法伪代码 6. 性能优化与注意事项 桶结构 ：使用基于高度的桶，允许并行处理同一桶内的节点，同时保持高度的单调性。 原子操作 ：对残留容量和盈余的更新需原子化，但重贴标签时的“读-计算-写”可能需要细粒度锁以避免竞态。 负载均衡 ：由于节点度数差异，可能造成某些处理器负载过高。动态调度（如工作窃取）可用于平衡桶内节点的处理。 通信开销 ：在分布式环境中，边可能跨越处理器，推送操作需要跨节点通信更新残留容量和盈余。可以通过异步通信和消息缓冲来隐藏延迟。 7. 复杂度与正确性 正确性 ：并行版本维持了串行预流推进的不变式（特别是高度约束），因此最终结果正确。 时间复杂度 ：最坏情况下与串行相同（\( O(|V|^3) \)），但实际并行度取决于图结构和高度分布。平均情况下，可达到近线性加速。 空间复杂度 ：每个处理器需存储局部子图及相邻边界信息，总空间为 \( O(|V|+|E|) \)。 8. 总结 并行化Goldberg-Tarjan预流推进算法的核心是 基于高度桶的顺序处理 ，它减少了数据依赖，同时允许桶内节点并行推进和重贴标签。通过细粒度的同步和原子操作保证一致性，配合周期性的全局重贴标签加速收敛，可以高效求解大规模图的最大流问题。