4.1.1 K-L 算法与 FM 算法

文档摘要

4.1.1 K-L 算法与 FM 算法在超大规模集成电路（VLSI）物理设计的浩瀚星图中，电路划分（Partitioning）绝非一道可有可无的工序——它是一道决定全局命运的“分水岭”。当千万级门电路被抽象为一张带权无向图，当互连线长、时序收敛、功耗分布、测试可访问性这些看似遥远的后端指标，其根系早已深扎于划分结果的土壤之中；当我们在布局布线工具中点击“Run Floorplan”那一刻，真正被悄然加载的，不是网表，而是你三天前手写的那个partition脚本所产出的割集（cutset）。这便是4.1.1节的重量：K-L算法与FM算法，不是教科书里泛黄的两页公式，而是嵌入EDA工具内核、每秒执行数万次迭代、在毫秒级时间内完成百万节点博弈的“数字裁缝”。