Page 252 - 《软件学报》2024年第4期

1830 软件学报 2024 年第 35 卷第 4 期

个具有相同标签的候选顶点组 VG, 如果该候选顶点组 VG 的移动会导致分区欠负载, 那么什么都不做, 跳过该候
选顶点组 VG (行 9–11). 否则, 将根据公式 (8) 计算该候选顶点组 VG 的移动增益 vgm : gain s→t (VG) . 同样, 设计一
个拥有 k 个元素的数组, 用 migration_gain_array 表示, 该数组中的每一项代表候选顶点组 VG 的移动增益, 移动
增益利用公式 (7) 提出的综合考虑边切割和负载平衡这两个优化目标的方式来进行计算. 假设候选顶点组 VG 当
前所在分区为 P i , 则 migration_gain_array 数组中第 i 个元素对应该候选顶点组 VG 所在的分区, 我们设置其为 0,
migration_gain_array 中第 j 个元素代表的是将该候选顶点组 VG 移动到分区 P j 的移动增益值, 这里 1 ⩽ j ⩽ k 并且
j , i . 根据公式 (8) 更新每一个候选顶点组 VG 的 migration_gain_array 数组, 并且挑选出在该 VG 和目标分区之
间拥有最大移动增益的目标分区 P t (行 12–13). 在这个过程当中, 拥有正的移动增益值的候选顶点组 VG 被保留
(行 14–16). 搜索过程继续, 直到对于所有的候选顶点组 VG 而言, 移动它将违反其所在分区 P s 的负载约束 (行 18).
最后, 该过程将回退到拥有最大移动增益的候选顶点组 VG, 并且将其移动到目标分区中 (行 19).
3.3 算法设计
在局部优化器中, 我们讨论和分析了顶点插入、边插入、顶点删除和边删除这 4 种不同的单元更新类型会涉
及的分区发生变化的个数, 以及如何在每种单元更新附近找到一些边界顶点, 并从这些边界顶点开始利用基于改
进标签传播的顶点组搜索策略搜索出最有益的顶点组 VG. 从中可以得知, 每个单元更新会涉及一个或两个分区.
当单元更新涉及两个分区时, 同时执行局部优化器有可能出现移动干扰, 移动干扰会导致算法效率降低和划分质
量下降. 因此, 为了避免无效的移动和最大限度地提高划分质量, 在本文提出的 ED-IDGP 算法中, 采用一种顺序的
方式解决移动干扰的问题. 对于一个单元更新会涉及两个分区发生变化的这种情况, 我们不是同时独立地在这两
个分区中运行局部优化器, 而是一个一个地依次执行局部优化器. 这里指出, 由于只有两个分区有可能会出现移动
干扰的问题, 所以采用顺序的方式对算法效率的影响不是很大, 同时也保证了图划分的质量不受影响.
本节提出了 ED-IDGP 算法 (如算法 2 所示) 解决动态增量图划分问题, 在拥有高效率的情况下最大限度获得
高质量的划分结果. ED-IDGP 算法的输入参数是初始图 G 的一个划分 P, 动态更新∆G, 在顶点组移动 ED-IDGP
算法的详细过程如下: 对于在动态更新∆G 中的每一个单元更新, 利用提出的动态处理器进行处理 (行 2). 如果该
单元更新是顶点删除, 在除该单元更新所涉及的分区的所有其他分区中, 选择拥有最高负载大小的分区考虑做移
动 (行 3–6). 否则, 对于其他单元更新, 获得其涉及动态变化的分区 P s (行 7–9). 将分区 P s 和参数 γ 作为算法 1 的
输入, 利用基于改进标签传播算法的顶点组搜索策略获得顶点组 VG (行 10). 从该顶点组 VG 的移动增益数组
migration_gain_array 中选择拥有最大元素值所代表的目标分区 P t (行 11). 如果将该顶点组 VG 从分区 P s 移动到
分区 P t 的移动增益值 vgm : gain s→t (VG) 大于 0, 那么我们就将该顶点组 VG 移动到目标分区 P t 中 (行 12–14).

算法 2. 基于顶点组重分配的动态增量图划分算法.
输入: partitioning P of G, dynamic update ∆G, γ;
′
输入: updated partitioning P of G+∆G.
1. for each unit update in ∆G
2. process it according to dynamic processor
3. if the unit update is vertex deletion then
4. foreach part P i ∈ P do
5. find P s with maximum overload ratio
6. end
7. else

8. P s ← the unit update
9. end if
10. VG←基于改进标签传播算法的顶点组搜索策略 (P s , γ)
( )
P t ← argmax migration_gain_array[t −1]
11. select