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

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

′
ec : gain s→t (VG) = EC (P)− EC (P ) (6)
其中, EC(P) 表示顶点组 VG 移动之前整个划分的边切割, EC(P ) 表示顶点组 VG 移动之后整个划分的边切割. 类
′
似地, 边切割的变化只有顶点组 VG 所在的分区 P s 和目标分区 P t 决定. 因此, 我们用公式 (7) 表示顶点组 VG 的边
切割增益.
ec : gain s→t (VG) = N t (VG)− N s (VG) (7)

其中, N t (VG) 和 N s (VG) 分别表示顶点组 VG 在分区 P t 和 P s 的其他部分中的邻居的数量.
定义 9. 顶点组移动增益 (vertex group migration gain). 为了综合考虑边切割和负载平衡这两个优化目标, 在负
载平衡增益和边切割增益的基础上, 公式 (8) 给出了将顶点组 VG 从它所在的分区 P s 移动到目标分区 P t 的移动
增益.
ec : gain s→t (VG) lb : gain s→t (VG)
vgm : gain s→t (VG) = γ × +(1−γ)× (8)
|E| |V|
其中, γ 同样指定了边切割和负载平衡之间的相对重要性, 且 γ 是介于 0–1 之间的值. 如果 γ 等于 0, 那么意味着不
考虑负载平衡. 如果 γ 等于 1, 那么意味着不考虑边切割. γ 越大, 划分越平衡. γ 越小, 边切割越低.
基于改进标签传播算法的顶点组搜索策略考虑在每个分区中, 当出现动态变化后, 在发生单元更新的附近区
域搜索顶点组 VG. 前面我们提出了动态处理器, 分别针对 4 种不同的动态变化类型提出了不同的处理策略. 但是
图划分问题有两个目标, 一是最小化不同分区之间边被切割的数量, 即 min EC(P); 二是每个分区中的顶点的数量
要尽可能相等, 即 min LB(P). 所以当考虑从一个分区移动顶点组 VG 到其他分区中, 要想降低边切割的数量, 必须
在该顶点组 VG 中包含分区的边界顶点. 因此, 本文采用的基于改进标签传播算法的顶点组搜索策略必须从单元
更新附近的边界顶点开始逐步搜索顶点组 VG. 接下来我们对顶点插入、边插入、顶点删除以及边删除这 4 种不
同的情况分别进行讨论分析.
首先, 对于顶点插入, 考虑顶点插入的两种情况. 第 1 种情况是新插入的顶点作为孤立顶点分配到拥有最低负
载大小的分区中, 主要是为了使得每个分区的负载大小平衡, 在这种情况下局部优化器不做考虑. 第 2 种情况是新
插入的顶点与其相关的一条边信息随之插入, 正如图 2 所分析的, 该种情况下在图动态变化的附近会出现局部次
优顶点划分, 因此需要局部优化器做优化, 使得从局部次优顶点划分转变为局部最优顶点划分. 但是很明显新插入
的顶点并不是一个边界顶点, 所以需要沿着新插入的这个顶点开始, 从它的邻居中搜索出邻居跳数相对较小的一
些边界顶点. 这里指出, 对于顶点插入这种单元更新, 在做局部优化时, 只涉及一个分区.
其次, 对于边插入, 同样也考虑边插入的两种情况. 第 1 种情况是新插入的边的两个端点都在同一分区中, 该
种情况下只涉及一个分区. 如果新插入边的两个端点中有边界顶点, 那么基于改进标签传播算法的顶点组搜索策
略从这些边界顶点开始进行搜索. 但是如果新插入边的两个端点都不是边界顶点, 那么同样我们需要在这两个端
点的邻居中搜索出邻居跳数相对较小的某些边界顶点. 第 2 种情况是新插入的边的两个端点在两个不同的分区
中, 该种情况下会涉及两个分区, 即需要在边插入这种单元更新类型涉及的两个分区中执行局部优化器做优化. 正
如图 3 所示, 新边涉及的两个端点都是边界顶点, 所以从这些边界顶点开始利用局部优化器做优化.
再次, 对于顶点删除, 正如图 4 所示, 顶点的删除有可能会导致分区出现欠负载的情况. 对于这种情况, 与前面
分析的其他情况不同, 我们不能在该顶点删除涉及的分区中移出顶点组 VG, 这样只会更加使得分区负载不平衡.
因此, 为了让每个分区中的顶点数尽可能相等, 我们考虑从所有分区中找出拥有最高负载的分区, 从高负载分区的
边界顶点开始, 搜索顶点组 VG 并将其移动到欠负载的分区中.
最后, 对于边删除, 考虑边删除的两种情况. 第 1 种情况是要删除边的两个端点在两个不同的分区中. 这种情
况下需要分别在这两个分区中执行局部优化器, 需要从这些端点的邻居中找出邻居跳数相对较小的一些边界顶
点, 从而从这些边界顶点开始搜索可用于移动的候选顶点组 VG. 第 2 种情况是要删除边的两个端点在同一分区
中, 正如图 5 所示, 此种情况只涉及一个分区, 同样需要从这两个端点开始搜索出其邻居跳数相对较小的那些边界
顶点.