3.5 解析式布局：把线长写成函数

3.5 解析式布局：把线长写成函数

本节摘要：布局规划解决大模块骨架，真正要安放的是数百万标准单元。解析式布局把线长与密度写成坐标的光滑函数，用连续优化的机器一气算出所有单元坐标——这是近二十年布局算法的主干路线。本节从二次布局讲到 ePlace 的静电类比，拆解光滑化、密度罚函数、迭代交替三个支柱，并给出各步骤的复杂度数字。2.4 节的数值方法在本节全面上岗。

线长的两种写法

布局的物理目标是让连线的实际长度短，但"实际长度"在布局阶段不可得（布线还没发生），工程上用半周长线长 HPWL 代替：一个网所有引脚包围盒的半周长。HPWL 对单个网好算，但对全体单元坐标却不是光滑函数——包围盒由"最左引脚"这类 arg min 结构决定，坐标微小移动时函数斜率跳变，梯度法无从下手。解析式布局的全部技术含量，就在于把 HPWL 替换成既够近似又光滑的替代品。

第一代替代是二次线长：把每个网建模成弹簧系统（团模型），线长写成网内引脚两两坐标差的平方和。整个布局的代价函数是一个标准的二次型，对任意单元求偏导得到线性方程组——二次布局的解就是解一个稀疏线性系统，预条件共轭梯度法在百万变量上分钟级收敛。它便宜且光滑，但有个结构性偏差：平方惩罚过度放大长网的权重，长网被过分缩短、短网被挤扁，布局质量有系统性缺陷。改进分两路：对长网降权（BonnPlace 路线），或换更贴近 HPWL 的光滑近似（log-sum-exp，即 ePlace 前身的 Kraftwerk2 路线）。

密度约束：光滑化之后的真正难关

只有线长目标时，解析布局的解会把单元堆成一团——线长最短的解就是全部重叠在质心。密度约束（每个区域利用率不超过阈值）才是布局问题的灵魂，也是解析路线真正的技术关卡。处理方式从历史上数过来有三代。第一代是离散合法化：先无约束光滑求解，再用简单的散开算法把重叠单元推开到合法位置——快，但散开破坏线长，质量差。第二代是罚函数法：把"超标密度"写成平滑的罚项加进目标函数，与线长项加权交替优化，代表是 BonnPlace 与 RePlAce 的早期形态；罚函数的光滑化（如用泊松方程的热扩散近似密度场）让梯度可算。第三代是静电场类比，把整个问题换了一副物理面孔。

ePlace（2012 年后成为学术与工业原型主流）的类比值得完整说一遍：把每个单元看作带正电的粒子，电荷量等于其面积；密度场对应电势场，密度梯度对应电场。线长项把粒子拉向质心（弹簧力），密度罚项以电场力把粒子从拥挤区推开——过密区域电势高，梯度指向稀疏方向，粒子自然被推向空地。两个力平衡时单元既不过度堆叠也不彼此远离。这个类比的价值不止于直观：电势场满足泊松方程，而泊松方程有极快的数值解法（多重网格法近线性时间），密度梯度的计算从暴力 O(n²) 降到近线性。整套流程在百万单元上十几分钟内收敛，这是解析路线压倒退火路线（对百万单元完全不现实）的根本原因。

ePlace 主循环（线长与密度的交替下降）

repeat
    线长梯度 g_w = log-sum-exp 近似的 HPWL 对坐标求导
    密度场 phi 由泊松方程解出（多重网格法，近线性）
    密度梯度 g_d = 电场力 = 负梯度 phi 乘单元电荷
    总梯度 g = g_w + lambda 乘 g_d        // lambda 随迭代增大
    沿 g 做非单调线搜索更新坐标            // 共轭梯度或 L-BFGS
until 密度超标面积小于阈值 且 线长改善停滞
然后: 合法化(散开微调到单元行与列网格) + 细节布局
​

迭代链条上的工程细节

从解析解到可交付布局，链条上还有三道工序，每道都有自己的算法味道。合法化（legalization）：连续坐标对齐到单元行与列的离散网格并消除残余重叠，代表算法 Tetris（按 x 排序逐个放入最近空位）与 Abacus（在 Tetris 基础上允许行内滑动再优化），两者都在秒级处理百万单元。细节布局（detailed placement）：合法解上做局部改良——单元交换、窗口内重排、行内平移——每次移动后用精确 HPWL 复评，接受改良。典型增益是全局解基础上再省几个百分点的线长，看似不多，但时序关键路径恰恰对这几个点敏感。增量布局（ECO 场景）：设计改动只影响局部时，从既有布局出发做局部重解，数分钟内收敛，这是量产设计迭代的真实节奏。

时序驱动：给线长加权

纯线长驱动的布局对时序是盲的——关键路径上的网与非关键网等价看待。时序驱动的标准做法是网加权：静态时序分析（预布线用线长估算延迟）给出每个网的负裕量，裕量越负的网在代价函数里权重越高，解析求解时这些网被优先缩短。权重在布局迭代中周期性更新，形成"布局、估时序、再加权"的外环。更进一步的做法是把关键路径（而非单网）作为约束：路径级约束更贴近真实时序语义，但约束求解复杂度上升。工业工具普遍采用网加权为主、路径约束为辅的混合策略。到这里，单元有了合法坐标、时钟还没安排——下一节的时钟树综合接棒，处理全芯片要求最高的那一棵特殊网。

log-sum-exp 近似值得多看一眼公式形态：包围盒半周长被写成 gamma 乘以对数里"坐标指数加权和"的形状，gamma 控制近似强度——gamma 小则平滑但偏差大，gamma 大则贴近 HPWL 但梯度病态。工程做法是 gamma 随迭代逐渐增大，从"光滑优先"过渡到"精度优先"，这与模拟退火的温度调度在结构上同构：都是一个从易解到较真的调度参数。理解了这个同构，你会发现连续优化的几乎所有实用算法都共享"先宽松后收紧"的骨架。

本节要点回顾

• HPWL 不光滑：arg min 结构使梯度跳变，光滑化是解析布局的第一道工序。
• 二次布局：弹簧模型加稀疏线性系统，便宜但系统性放大长网权重。
• 密度约束是灵魂：无约束解必然堆叠成团，罚函数与静电类比是三代解法。
• ePlace 类比：线长是弹簧力、密度梯度是电场力，泊松方程近线性求解是速度来源。
• 链条三工序：合法化秒级、细节布局补几个百分点、增量布局服务 ECO 迭代。
• 时序驱动：负裕量网加权形成布局估时序再加权的外环，路径约束为辅。