第3章 布局布线的算法本质:门怎么落到硅片上


第 3 章 · 布局布线的算法本质:门怎么落到硅片上

本章要回答的三个问题:几百万个单元各放哪里,为什么这个组合问题是可解的?连线的几何与距离计算背后是什么数学?从全局规划到最终每一条走线,工程上如何分层把不可解的问题切成可解的几段?

为什么会有这一章

第 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 章的静态时序分析就站在这份数据上。物理实现给出事实,时序分析宣判事实是否达标,这是下一章的起点。

作者与出处
原作者:灏天文库
来源:平台策划编纂
整理人: 灏天文库整理
由灏天文库平台收录,内容或由平台用户上传,仅供学习交流
发布者: 作者: 灏天文库 转发
评论区 (0)
U