本章要回答的三个问题:几百万个单元各放哪里,为什么这个组合问题是可解的?连线的几何与距离计算背后是什么数学?从全局规划到最终每一条走线,工程上如何分层把不可解的问题切成可解的几段?
第 2 章结束时我们手里有了一张门级网表:哪些门、怎么连,全部明确;但这些门在硅片上的坐标还是一片空白。布局布线要回答的正是坐标问题,而它的难度常被低估——综合是布尔问题,物理实现是连续几何与组合结构的混合问题,两者的算法气质完全不同。一块先进芯片的布局问题可以粗暴理解为:在几十万个标准单元行上安放数百万个单元,使总连线最短、每个区域不挤爆、时序关键的路径尽量近、功耗密度的热点别叠在一起——四个目标互相打架。
这一章是全册算法密度最高的一章,共七节。前两节补数学地基(图论三件套与计算几何),中段四节沿物理实现的真实工序推进(划分、布局规划、解析布局、时钟树、布线),它们是第 1 章流程图里"物理设计"方框的逐层展开。你会发现第 2 章埋的两笔投资在这里兑现:模拟退火在布局规划里原样复用,数值优化在全局布局里挑大梁。
读完本章你应当能够:对一个小电路手推 FM 算法一轮 pass 的增益表与割边数变化;说出 sequence pair 如何用两个排列编码任意非重叠布局,以及为什么退火天然适配这种编码;解释解析布局把线长写成函数后密度约束如何用罚函数处理,ePlace 的静电类比好在哪里;计算给定偏差预算与时钟周期下时钟树需要满足的数字条件;描述协商式布线为什么比单纯最短路布线更适合百万线网规模。这些能力合起来,就是"看懂一份物理实现工具报告与论文"的门槛水平。
| 节 | 回答哪个问题 | 关键产出 |
|---|---|---|
| 3.1 图论地基 | 切分与连线依赖什么数学 | 最小割、最短路、斯坦纳树三件套 |
| 3.2 计算几何地基 | 版图如何做几何运算 | 多边形布尔运算与扫描线复杂度 |
| 3.3 电路划分 | 千万对象怎么分而治之 | FM 最小割划分的完整一轮 |
| 3.4 布局规划 | 大模块的骨架怎么定 | sequence pair 与退火组合 |
| 3.5 解析式布局 | 数百万单元如何连续求解 | 线长光滑化与密度罚函数 |
| 3.6 时钟树综合 | 时钟凭什么同时到达 | 偏差预算与 DME 算法 |
| 3.7 布线 | 每条线怎么找到合法路径 | 迷宫算法与协商式拥塞控制 |
七节的依赖关系是两段式:3.1 与 3.2 是工具箱,之后每节从工具箱取件组装;3.3 到 3.7 严格按物理实现的工序先后排列,前一节的输出是后一节的输入。跳章读是可行的,但 3.5 依赖 3.1 的图论词汇、3.7 依赖 3.4 的坐标概念,建议保住这两条依赖边。
第 2 章的布尔网络与门级网表概念;基本图论(路径、树、生成树);微积分里的偏导数与拉格朗日乘数法(3.5 用到)。不需要版图设计经验——所有几何概念在本章内现学。
布线完成后,每条连线的几何长度确定,寄生电阻电容随之可提取,延迟从"估算"变成"实测级精确"。此时设计第一次拥有了可签核的时序数据——第 4 章的静态时序分析就站在这份数据上。物理实现给出事实,时序分析宣判事实是否达标,这是下一章的起点。