本页目录

制造 III · EDA：用算法造芯片

层次：本科接触 + 硕博第三条路（EDA 算法方向）+ 业界日常。一颗现代芯片有数百亿个晶体管。没有任何人能手工设计它们——芯片是被软件造出来的。EDA（电子设计自动化）是一个规模不大但极其关键的产业：它把设计意图逐层翻译成可制造的几何图形，而这条流水线上的每一步几乎都是 NP 难问题的启发式求解。对计算机背景的读者，这是本课最亲切的一页（🔗 cs 站算法线、编译线）。

学习层：时序签核把一个巨大图问题压缩成可证明的最长路径

具体谜题：优化了很多门，为什么时钟仍然不收敛？

考虑三个从 launch 到 capture 的时序路径：P1 的组合延迟为 1.1+2.0+1.3=4.4 ns，P2 为 1.8+2.4+1.2=5.4 ns，P3 为 2.0+1.7+1.5=5.2 ns。时钟周期为 5.5 ns、setup 预算为 0.2 ns。你预计哪个节点决定签核？如果工具把 P1 缩短 0.6 ns，而没有碰 P2，最坏 slack 会变好吗？这就是“局部优化”和“全局约束”之间的差别。

先做预测

先选出临界路径并判断周期 5.5 ns 是否通过。再预测：① STA 不需要枚举指数多条完整路径，只需在 DAG 上传播每个节点的最大到达时间；② 优化非临界路径不会改变最坏 slack；③ 把时钟周期从 5.5 ns 放宽到 6.0 ns 会使 slack 增加 0.5 ns，但不会减少真实组合延迟；④ 一旦加入反馈环，简单的 DAG 最长路递推就失去适用条件。

最小 mental model：约束图上的最长路径

把寄存器、组合逻辑和时钟边界抽象为有向图。每条边有延迟，节点的 arrival time 是所有前驱到达时间加边延迟的最大值；后端布局、布线和寄生提取只是不断改变这些边权。EDA 的翻译链要保持功能等价，但物理实现还必须让所有时序、功耗、拥塞和设计规则约束同时成立。

形式机制与不变量

AT(v) = max_{u -> v} [AT(u) + d(u,v)], slack(p) = T_clk - t_setup - delay(p)

在拓扑序上计算 AT(v)，终点的最大 arrival 就是最坏路径延迟 D_max。setup 签核的必要条件是 T_clk - t_setup - D_max >= 0。这个递推的不变量是：处理节点时所有前驱已经完成，且当前值等于从源点到该节点的最大路径长度；因此不需要把所有路径显式存下来。

实验把一个“修复动作”建模为对选定路径减去固定延迟并增加面积/功耗代价。它不会伪装成真实综合器，却能验证一个核心事实：签核目标是最坏约束，不是平均门延迟。

反例与失效边界

真实 STA 不只看 setup：hold、clock skew、OCV、串扰、IR drop 和多时钟域会增加约束边界。
图中若存在组合环，或时钟关系没有被正确声明，DAG 递推不能直接给出可信签核；约束文件写错会让“通过”没有意义。
把一条路径变快可能增加拥塞、寄生或功耗，导致另一条路径变慢；物理设计是耦合的多目标迭代。
形式等价只证明功能关系，不证明布局后的时序、可靠性和可制造性。

交互实验：沿着 DAG 做一次 timing closure

无 JavaScript 时的静态读法：固定三条路径 P1=4.4 ns、P2=5.4 ns、P3=5.2 ns，setup=0.2 ns。当周期为 5.5 ns 时，最坏 slack 为 5.5-0.2-5.4=-0.1 ns，由 P2 决定。把 P1 缩短 0.6 ns 后，P1=3.8 ns，但最坏 slack 仍为 -0.1 ns；把 P2 缩短 0.6 ns 后，P2=4.8 ns，但 P3 的 5.2 ns 变成新的临界路径，最坏 slack 仅变为 5.5-0.2-5.2=+0.1 ns。拓扑递推的结果必须等于三条路径总和的最大值。

路径	边延迟	总延迟	周期 5.5 ns 下 slack
P1	1.1 + 2.0 + 1.3	4.4 ns	0.9 ns
P2	1.8 + 2.4 + 1.2	5.4 ns	-0.1 ns
P3	2.0 + 1.7 + 1.5	5.2 ns	0.1 ns

迁移任务：把一个 RTL 约束写成可审计问题

为一个两级流水线加速器列出 launch/capture 时钟、setup/hold、最大组合延迟、输入输出延迟和允许的 clock skew。然后设计两种修复：一是对临界路径插入缓冲或换大单元，二是重定时移动寄存器。对每种修复分别预测面积、功耗、拥塞和 hold 风险，说明你会用哪些报告确认“修复真的跨过了签核边界”。

一、抽象层次：一条翻译链

EDA 的本质是一系列保持等价性的翻译，这与编译器高度同构：

层次	表示	对应编译器
行为/算法	C/SystemC、高层次综合	源语言
RTL	Verilog/VHDL（寄存器传输级）	中间表示
门级网表	标准单元 + 连接关系	目标汇编
版图（GDSII）	多边形几何图形	机器码

每一层都需要验证与前一层等价（形式等价性检查、时序验证）。"编译器要保证语义等价，EDA 要保证功能 + 时序 + 物理都等价"——后者难得多，因为它还要满足物理约束。

二、前端：从 RTL 到网表

逻辑综合：把 RTL 描述转换为门级网表，同时优化面积、时序、功耗。

技术无关优化：布尔化简、公共子表达式提取、重定时（retiming，把寄存器在组合逻辑中移动以平衡各级延迟）；
技术映射：把逻辑网络映射到具体标准单元库——这是一个覆盖问题，经典解法是树覆盖的动态规划（与编译器的指令选择是同一个算法）；
约束驱动：综合完全由约束文件（SDC）引导——约束写错，后面全错（承第七页）。

验证（占据芯片项目的大部分工时，这是学校严重低估的部分）：

仿真：写测试激励跑波形，覆盖率驱动；
形式验证：等价性检查（综合前后是否一致）、属性检查（模型检验，🔗 cs 站）；
UVM 等验证方法学：构建可复用的验证平台。

业界现实：在大型芯片项目中，验证工程师的数量常常超过设计工程师。"设计一个模块两周，验证它三个月"并不夸张。因为流片错误的代价是数百万美元与数月时间（第十一页）。

三、后端：物理设计

① 布局（placement）：决定每个标准单元的坐标。

目标：总线长最短、时序满足、密度均匀、可布线；
这是一个大规模非凸优化问题。经典方法是解析式布局——先把线长用二次型或对数-指数光滑函数近似，解出连续解（大规模稀疏线性系统），再逐步施加密度约束把单元"推开"合法化。规模达数千万个单元；

② 时钟树综合（CTS）：构造缓冲树，控制偏斜与插入延迟（第七页）；

③ 布线（routing）：在多层金属上连接所有网络。

全局布线：把芯片划分为网格，规划每条网络大致走哪些通道——本质是多商品流问题；
详细布线：确定精确的轨道与过孔，必须满足所有设计规则；
迷宫布线（Lee 算法）与 A* 是基本工具，但真实问题需处理数百万条网络、十几层金属、以及先进节点极其复杂的规则。

④ 时序收敛与签核：反复优化（改尺寸、插缓冲、改布局）直到所有路径裕量非负，然后做全面签核分析——STA、功耗、IR 压降、电迁移、串扰、天线效应。

这个流程的痛苦之处在于耦合：改布局影响布线，布线影响寄生参数，寄生参数影响时序，修时序又要改布局。它是一个高维、多目标、强耦合的迭代过程，大型芯片一轮完整流程需要数天到数周的机时，整体收敛需要数月。

四、为什么 EDA 是算法的富矿

几乎每一步都对应一个经典的困难问题：

环节	问题本质
技术映射	树覆盖 / 动态规划
布局	大规模非凸优化、二次规划
划分	图划分（NP 难，用 KL/FM 启发式、谱方法）
布线	多商品流、迷宫搜索、约束满足
STA	图上的最长路径（DAG，可线性时间求解——这正是它能穷举所有路径的原因）
逻辑综合	布尔函数优化、SAT 求解
形式验证	模型检验、SAT/SMT
OPC/ILT	大规模逆问题优化（第十二页）

注意 STA 那一行：它之所以能"穷举所有路径"而不爆炸，是因为时序图是 DAG，最长路径可以用一次拓扑排序线性求解——不需要真的枚举指数多条路径。这是一个漂亮的算法洞察，也是 STA 能成为工业标准的原因。

近年趋势：机器学习进入 EDA——布局的强化学习方法、时序预测代理模型、参数自动调优。效果真实但需谨慎判读：这类工作的对比基线是否公平、是否在独立设计上验证，争议不少【争】。成熟的应用目前更多在"预测与调参"，而非取代核心引擎。

五、模拟设计为什么没被自动化

数字有完整的自动化流程，模拟至今主要靠人：

数字的抽象是干净的（0/1、时序契约），模拟的性能指标是连续、多维、强耦合的（增益、带宽、噪声、失配、功耗同时冲突）；
模拟版图对寄生参数、匹配、对称性、热梯度极其敏感，几何细节直接决定性能；
设计空间小而深，依赖拓扑创新与经验直觉。

现状：有辅助工具（自动布局布线的局部尝试、优化式尺寸设计、基于代理模型的搜索），但完整的"模拟综合"仍未实现。这就是模拟设计者稀缺且值钱的原因——它是行业中最难被自动化的岗位之一。

六、产业结构与工具链现实

EDA 是高度集中的产业：少数几家公司（Synopsys、Cadence、Siemens EDA）占据绝大部分市场；
工具授权极其昂贵，一套完整流程的年费可达数百万美元量级——这是初创芯片公司的主要门槛之一；
工具与工艺深度绑定：代工厂提供 PDK（工艺设计套件），包含器件模型、标准单元库、设计规则、验证脚本。PDK 是设计与制造之间的正式契约；
开源生态（OpenROAD、OpenLane 等）近年活跃，配合开放 PDK 已能完成成熟节点的完整流程，对教学与小型项目意义重大——但先进节点仍完全依赖商业工具。

七、要点

EDA 是一条保持等价性的翻译链，与编译器同构，但还要满足物理约束；
每一步几乎都是 NP 难问题的启发式求解——这是算法与优化的富矿；
验证占据项目大部分工时，因为流片错误代价极高；
STA 能穷举路径，靠的是 DAG 最长路径的线性算法；
模拟设计尚未被自动化，原因在于其抽象无法干净切分；
PDK 是设计与制造的契约，EDA 与工艺深度耦合。

下一页：制造线的最后一站——良率、变异与可靠性。这是学校讲得最少、而工业界最看重的内容：造出来是一回事，造得出、卖得掉、用得久是另一回事。