3.3 电路划分：FM 最小割算法

3.3 电路划分：FM 最小割算法

本节摘要：划分把千万级单元的网表切成规模可控的子块，是"分而治之"进入物理实现的第一刀。本节从 Kernighan-Lin 的 O(n² log n) 交换框架讲到 Fiduccia-Mattheyses 的线性时间增益桶改进，完整手推一轮 FM 的增益表与割边变化，并解释多层划分框架如何把算法推向千万单元规模。本节是第 3 章第一个正式工序，也是全书第一次见到"增益驱动移动"这一通用算法模式。

为什么第一刀是切割

布局布线的算法大多随规模超线性增长，而先进设计动辄数千万单元。工程上唯一的出路是分而治之：先把网表切成大小合适、相互连线尽量少的子块，块内分别求解，块间只处理少量接口。切口质量直接决定全局质量：切割的跨块连线越少，块间交互越少，后续每一步的接口代价与信号跨块延迟都越小。划分目标因此非常干脆：在每块大小落在给定区间（典型为总量的 45% 到 55%）的约束下，最小化跨块连接的代价和。3.1 节说过，带平衡约束的最小割是 NP 难——本节的主角 FM 算法，就是这个 NP 难问题四十年来最实用的启发式。

先明确输入的图模型：单元为节点，网（多引脚连线）为超边。为使用图算法，通常把每个网拆成团（clique，任意两引脚连边、每条边权 1 除以 k 减 1）或星形（引脚连到虚拟中心）模型。拆分有失真，但实测对划分质量影响有限，工程上默认接受。

Kernighan-Lin：交换框架的开山

KL 算法（1970）的思想是"先局部交换、贪心挑选、成对锁定"。每一轮：对所有分属两块且未锁定的节点对，计算交换后的割增量；选增量最有利的对执行交换并锁定（本轮不再动它）；重复直到没有候选。一轮结束后回看所有交换的历史点，选择累计收益最高的前缀作为本轮成果，然后解锁进入下一轮。KL 的精妙在"回看前缀"——允许中途暂时变差的交换序列，只要累计是赚的。代价是每轮要评估 O(n²) 个节点对的增益，每次评估又涉及邻域扫描，总复杂度 O(n² log n)。百万单元的图上，这个复杂度已经不可接受。

FM：从平方到线性的关键一跃

Fiduccia-Mattheyses（1982）保留了 KL 的"移动加锁定"骨架，但把节点对换成单节点移动，并解决了增益快速更新的问题。每轮流程：计算所有未锁节点的增益（移到对面的割变化量），按增益分组放进桶链表（桶下标即增益值）；每步从最高非空桶取出增益最大的节点尝试移动；移动受两块大小的平衡约束把关；移动后只需更新该节点邻居的增益（每个邻居增益变化量在正负 2 之间），邻居从旧桶摘下插进新桶——每次增益更新 O(1)。取最大增益用桶指针直取。一轮 pass 的总复杂度降到 O(引脚数)，即与电路规模线性。

拿一个 8 单元的小电路手推一轮。设初始分块 A 有 a、b、c、d，B 有 e、f、g、h，网连接为：网1 连 a、b、e；网2 连 b、c、f；网3 连 d、h；网4 连 c、g。初始割边：网2（b c 在 A，f 在 B）、网3（d 在 A，h 在 B）、网4（c 在 A，g 在 B），共 3 条。计算各 A 侧节点增益：a 的网1 全在 A 侧除 e，a 移走后网1 变割，增益负 1；b 在网1 与网2 中都有邻居在对面，移动后网1 成割（负 1）、网2 去割（正 1），增益 0；c 连接网2 与网4 均含对面邻居，移动后两条去割，增益正 2；d 移动后网3 去割，增益正 1。取最大增益 c 移动并锁定，割数降到 1。继续按规则评估、移动或拒绝，一轮结束后回看增益历史取最优前缀。这个小例子展示了 FM 的全部机制：增益桶选点、平衡把关、历史回看。

// FM 一轮 pass 的骨架
FMpass(graph, balance) {
    computeGains(); buildBuckets();       // 初始化增益与桶链表
    bestSeqGain = 0; acc = 0; k = 0;
    while (存在未锁定且可移动节点) {
        v = 从最高非空桶取增益最大者;      // O(1)
        if (移动 v 违反 balance) { lock(v); continue; }
        move v to 对面; lock(v); acc += gain(v);
        record(acc);                       // 记录累计增益序列
        if (acc > bestSeqGain) bestSeqGain = acc, bestK = k;
        for (u in neighbors(v)) {          // 只更新邻居
            move u between buckets;        // O(1) 摘插
        }
        k++;
    }
    if (bestSeqGain > 0) 回滚到第 bestK 步状态;  // 贪心前缀回看
}
​

多层框架：让 FM 吃下千万单元

单轮 FM 的质量随图变大而衰减（局部增益视野小），直接在大图上跑既慢又差。现代划分器（hMETIS、工业工具内嵌引擎）的标准架构是多层框架：粗化阶段把节点与超边反复合并，图从千万单元缩到几千节点；在最粗图上跑 FM（此时图小，可以跑多轮多起点甚至较精确算法）；细化阶段逐层把图展开，每展开一层就在该层再跑 FM 精修。多层框架的哲学与 2.1 节的抽象分层一脉相承：在低分辨率下看全局，在高分辨率下修细节。它让划分质量与规模近乎解耦，千万单元的划分在单机上分钟级完成。

划分在流程里的三张面孔

划分不只是物理实现的预处理，它在流程里反复出现。其一，布局前的功能块划分与多晶圆（multi-die）系统的 die 间切分——后者直接决定封装内互连带宽，割边权即带宽代价。其二，FPGA 综合里的逻辑分块：一块 FPGA 装不下的设计要切到多块，割越少跨块布线资源越省。其三，并行仿真与并行布线的负载切分：按割边少、块内均衡切，通信开销与负载不均同时最小。三张面孔共用 FM 加多层框架这一套内核，只是权函数不同——时序驱动的划分会把关键网的边权乘上权重因子，让关键路径尽量不跨块。理解了权函数可替换这一点，你就能把本节算法迁移到任何"切割代价"可定义的场合。

图：FM 一轮 pass 的增益桶与移动序列

本节要点回顾

• 划分即第一刀：跨块连线越少，后续接口代价越小；带平衡的最小割 NP 难，FM 是实用解。
• KL 开创交换框架：成对交换、锁定、前缀回看，O(n² log n) 在大图上不可行。
• FM 的三件事：单点移动、增益桶 O(1) 更新、平衡约束把关，一轮 pass 线性于引脚数。
• 前缀回看：允许中途变差的移动序列，只要累计收益为正——贪心框架里的短视豁免。
• 多层框架：粗化、顶层精解、逐层细化，质量与规模解耦，千万单元分钟级。
• 权函数可替换：时序驱动、带宽驱动、负载驱动的划分共用同一内核。