Page 109 - 《软件学报》2026年第3期

1072 软件学报 2026 年第 37 卷第 3 期

1. begin
2. M ← mapping of vertex IDs to previous partition IDs
3. P = [P 0 ,...,P n−1 ] ← [∅ for i in 0..n−1] //清空原本的布局
4. foreach v in V
5. x ← M [v] //尝试分配至原布局位置
while x < n and P x is full then x ← x+1
6.
if x = n then x ← any free partition
7.
8. P x ← P x ∪v
foreach u ∈ IN (v)
9.
y ← max(M [u], x) //尝试分配邻居至原布局位置
10.
while y < n and P y is full then y ← y+1
11.
12. if y = n then y ← any free partition
13. P y ← P y ∪u
14. endfor
15 endfor
16. end

(3) 分配算法 C: 基于邻居频率启发式的收敛分配算法
在分配算法 B 的布局基础上, 本文再提出基于邻居频率启发式的收敛优化算法, 期望在尽量不破坏分配算法
B 的先后顺序基础上, 进一步加强松弛化条件, 具体流程如算法 7 所示: 给定迭代轮数 β 与已有布局 (第 2–4 行),
按照随机顺序访问所有点 (第 5 行), 当访问点 p 时, 统计其邻接出边点所在分区号的最大值 PID direct 与邻接入边点
PID reverse (第 6、7
所在分区号的最小值 行), 如果 PID direct 小于等于 PID reverse , 则当前访问点 p 可以取到局部最优解,
PID reverse 之间的最小分区上 (第 9、10 PID direct 之
也就是把点 p 分配到 PID direct 与 行); 否则, 把点分配到 PID reverse 与
间权重最大值分区上 (第 11–21 行), 权重值为当前分区及以后的入边邻居数与当前分区及以前的出边邻居数之和
(第 13–16 行).
算法 7. 基于启发式的收敛分配算法.

输入: 图G = (V,N (V)), 迭代轮数β;
输出: 新布局P.
1. begin
2. M ← mapping of vertex IDs to previous partition IDs
3. P = [P 0 ,...,P n−1 ] ← [∅ for i in 0..n−1] //清空原本的布局
4. while iteration ⩽ β
5. foreach v in V
6. PID direct ← max partition ID in direct neighbors
7. PID reverse ← min partition ID in reverse neighbors
8. x ← −1
9. if PID direct ⩽ PID reverse
10. x ← ID of smallest partition ∈ [P PID direct ,P PID reverse ]
11. else
12. W max ← −1
13. for i ← PID reverse to PID direct