布局阶段最常用的线长指标叫 HPWL，给每个网套一个最小包围盒，取长加宽，再把所有网累加起来。二十年来的解析式布局，基本都在这上面做梯度下降。
2026 年 10 月 20 日挂上 arXiv 的 DiffRMST 换了个打法：把这个目标函数本身换掉。作者来自东南大学集成电路学院和福州大学离散数学与理论计算机科学研究中心，论文标注已投稿 IEEE，初步版本发在今年 DAC 的 Late Breaking Results（最新成果）环节上。
结果有点反直觉。ISPD2019 十个设计上，最终布线线长比加权平均基线低 3.5%，GeoSteiner 算的精确 Steiner 树低 3.2%，RMST 低 5.0%。同一批结果里，HPWL 平均高了 4.7%，十个设计无一例外。
一个指标方向全错，另外三个方向全对。数据没出问题。它把布局里一个长期被折叠的问题翻到了正面：我们优化的东西，和验收的东西，一直不是同一个。
一、HPWL 量的是包围盒，不是线长
HPWL 便宜得让人上瘾。给出引脚坐标，取 x、y 各自极值，算 (max−min) 之和，O(n) 完事；天然并行，平滑之后梯度连续，正好塞进 Nesterov 那类加速梯度框架。
代价藏在细节里。包围盒只认四个极值引脚，盒子里的引脚对目标函数没有贡献，梯度也拿不到。两个网可以 HPWL 完全一样，内部连接差出一大截：一个绕着边缘走，一个从中间穿过去。对 HPWL 来说，这两种布局没有区别。
于是有了另外两把尺子。RMST 是引脚之间的直角最小生成树，不插 Steiner 点，多项式时间可解，Hwang 定理保证它不超过最优 Steiner 树的 1.5 倍。RSMT 允许插 Steiner 点，最贴近真实布线，对应的问题却是 NP-完全的，构造过程离散，扔不进梯度优化。
HPWL 最便宜最粗，RSMT 最贵最准，RMST 夹在中间。麻烦在于 RMST 也只是便宜，它不可导。
二、难的地方在“选树”这一步求不了导
RMST 的长度是两个东西的最小值：曼哈顿距离之和，以及从所有生成树里挑最短的那一棵。两处都卡住了求导。
绝对值在原点是尖角，换个平滑函数就行。论文用 φ_γ(d)=d·tanh(d/γ)：d 大时它退化成 d，d 小时把尖角抹平，γ 管抹平的范围。
麻烦的是后一层。n 个引脚的网有 n^(n−2) 棵生成树，最短树是里头挑出来的一个离散选择。对这个“挑”的动作求导，无从下手。
于是再平滑一次，对树长取 log-sum-exp 软最小：−β·log Σ_T exp(−树长_T/β)。温度 β 大，大量树同时参与，梯度看到的是期望意义下的树；β 逼近 0，收敛到真正的最短树。
思路到这里还算常规。真问题是那个求和号：n^(n−2) 棵树，枚举一遍就完了。
三、矩阵树定理：把指数级的树压成一次求逆
指数项 exp(−w/β) 在树上能按边拆开连乘，这个性质正好接上加权矩阵树定理：拉普拉斯矩阵任意一个 n−1 阶主子阵（删掉同一行同一列）的行列式，等于所有生成树边权连乘之和。
两边一对，配分函数不用枚举。松弛后的线长就是 −β·log det(L 的主子阵)，一次行列式，结束。
梯度也能顺手拿出来。对边权求偏导，得到这条边出现在生成树里的概率 p_ij——严格说，是松弛后那个树分布下的边际概率。全部加起来正好 n−1。Jacobi 公式让这一步变成一次矩阵求逆，不必逐棵树点数。
坐标梯度写出来是 Σ p_ij·∂w_ij/∂x_i。工程上可以这么看：每条边拉一下，力道等于它在松弛分布里的边际概率。所谓“拓扑感知”就落在这里。HPWL 的力来自包围盒边界，DiffRMST 的力来自整张网连接结构的期望。
代价是单网 O(n³) 的矩阵运算，用 Kron 消元（逐阶消去，等价于反复求 Schur 补）来做。前向的线长代价和反向的梯度共用同一次求逆。GPU 上按度数分三条路：2 引脚一线程，3 到 32 引脚一个子组，超过 32 引脚整块 128 线程，边权只存上三角。
全局布局迭代平均加速 14.7 倍，四个最大的设计做到 38.8 到 49.5 倍。
四、5.0% 和 4.7% 是同一笔交易
把账摊开。相对加权平均基线，RMST 平均降 5.0%，GeoSteiner 算的精确 RSMT 降 3.2%，CUGR2.0 在同一版图上评出的布线线长降 3.5%（布线器按访问点算，和几何指标不同源）；相对 LSE 基线是 4.9%、2.9%、3.2%。十个设计里，三个指标同时压过两个基线的有八个。
HPWL 反着走，平均 +4.7%（对 WA）、+4.9%（对 LSE）。时间也涨，总量平均比值 0.919 和 0.928，多花 8% 上下；最大的 ispd_test10 用了 45.81 秒，基线是 41.73 和 40.74 秒。
三个数字放一起，逻辑是通的。HPWL 只由极值坐标决定，把内部引脚往外拉开，包围盒变大，树却可以变短。论文给了一个 26 引脚网的对比：HPWL 从 52.192 涨到 68.281 微米，RMST 从 131.120 降到 92.320，RSMT 从 115.360 降到 87.508，树线长分别降 29.59% 和 24.14%。
一个网说明不了十个设计，但机制说清楚了：包围盒变大和树变短可以同时发生。
五、收益落在多引脚网，成本摊到所有网
收益不均匀。五个引脚以上的所有分组，RMST 和 RSMT 都优于两个基线，引脚越多优势越明显；17 到 32 引脚这一组，WA 到 DiffRMST 的比值 RMST 到 1.221，RSMT 到 1.182。
另一头在漏。2、3、4 引脚网的平均 RSMT 比值低于 1。2 引脚网最尴尬，只有一棵树，HPWL、RMST、RSMT 完全重合，模型再好也没地方使劲。而 ISPD2019 里 2 引脚网占到全部网的 49.76% 到 80.37%。
同一个方法，换张网表结果能差一个数量级。ispd_test1 里 33 到 99 引脚的网约占 5.90%，整体 RSMT 降 7.7%；ispd_test4 这一段几乎空着，整体只降 0.5%。
成本却是全局的。O(Σ|V_e|³) 对所有多引脚网都要付。所以全局布局加速 14.74 倍，总量加速只有 6.47 倍：ispd_test10 的 45.81 秒里，全局布局只占 10.97 秒，其余在初始化、合法化、输出。
Amdahl 定律的形状。目标函数再快，也只能快在它自己那一段。
六、验收指标选错，好方法会被自己的门挡在外面
这篇论文最值得拿走的数字，可能是那个 +4.7%。
设想一个团队把 HPWL 写进了布局验收门槛。现在来一个方法，布线线长降 3.5%，精确 Steiner 树降 3.2%，HPWL 涨 4.7%。按现有门槛，它会被拒。拒得还挺有道理：指标退化了。流程没错，门槛选错了对象。
过去几年布局的进展，大头在“更快地优化同一个目标”：GPU 化、算子融合、稀疏化，DREAMPlace 那条线跑出了数量级的加速。DiffRMST 走另一条轴，承认目标函数本身有偏差，换一个更接近布线的替代品。两条轴不冲突，可以叠在同一条流程里。
边界要说清楚。评测只在 ISPD2019 上做，布线线长由全局布线器评，没有时序、拥塞、功耗和 sign-off 的结果；RMST 终究不是 RSMT，误差界里还挂着 2Cγ(n−1)+β(n−2)log n 这一项，得靠密度溢出驱动的退火参数压住；时序驱动、拥塞感知和 3D 布局，作者列进了后续工作。这些都超出这篇论文的范围，也不该被标题里的 5% 盖过去。
顺带一句和流程有关的话。这类改进能不能进产线，往往不取决于算法本身，取决于它能不能被接进现有的 EDA flow：目标函数挂在哪个环节、参数怎么随工艺和网表调、结果和旧 flow 怎么对比、谁来签字。可落地的 AI+EDA 也绕不开同一件事，把专业模型、企业知识库和流程编排接进同一条研发链路，让每次改动都有可追溯的输入、输出和复核节点。
DiffRMST 说明了一件事：解析式布局里的目标函数，本身就是一个可以重新设计的工程对象。用矩阵树定理把指数级的离散选择压成一次求逆，再用 GPU 把这次求逆压回可接受的成本，这条路成立。
下一步看三件事。
验收指标和优化目标对不对得上。团队内部报的指标，和最终决定芯片好坏的结果，中间隔了几层？
收益会不会落在你的网表上。多引脚网、高扇出网多的设计收益明显；以两点连接为主的网表，可能只付成本。
成本能不能被流程摊销。单网三次复杂度，只加速全局布局这一段，放进完整 flow 还剩多少。
这三问答完，“线长降了 3.5%”才有意义。
作者：麒芯
本文为公开预印本的技术解读。线长与运行时间数据均来自作者论文在 ISPD2019 上的报告，不代表独立复现、产线实测或签核结论。
参考资料：Fuxing Huang、Hao Ai、Wenxing Zhu、Xinning Liu、Ziran Zhu，《DiffRMST: A GPU-Accelerated Fully Differentiable Rectilinear Minimum Spanning Tree Wirelength Model for Global Placement》，arXiv:2610.28246v1，2026 年 10 月。
热门跟贴