布局合法化:legalization 与 detailed placement 的位移最小化深讲
更新时间:2026-10-02。在 P&R 流程里,全局布局(global placement)交出来的并不是一个能直接往 CTS 送的网表状态——单元位置是连续坐标,行没有对齐,单元之间还互相压着。把这些「差不多对」的位置变成「完全合法且尽量不动」的位置,就是布局合法化(legalization)加上详细布局(detailed placement)这两步要干的事。本站 PnR Innovus 流程 给过从 floorplan 到 signoff 的全景,数据流之 floorplan 与 place 交接 讲了这一步上下游的数据契约,布局拥塞与 cell padding 讲了全局布局侧怎么给合法化留空间。这一篇往算法和工程细节里走一步:合法化到底在解一个什么样的约束满足问题,为什么说它的核心目标是位移(displacement)最小化,detailed placement 又在合法框架内做哪些局部优化。
本文要回答的问题
- 全局布局的输出为什么必然不合法,布局合法化要消除的违规到底有哪几类?
- 位移最小化为什么成为合法化的第一目标,它如何度量、和时序是什么关系?
- 合法化的典型算法思路(行吸附、二分/网络流、Abacus 类插入)各自怎么工作?
- detailed placement 在合法状态下还能做哪些局部优化,边界在哪里?
- 实战中怎么读合法化的报告,哪些指标说明「全局布局交得不好」而不是合法化本身的问题?
一、合法化要解决什么:全局布局留下的违规清单
先把问题的来源说清楚。全局布局的数学模型是把布局看成一个连续优化问题:以半周长线长(HPWL)或线长加密度的可微分目标为代价函数,用解析式方法(典型是力导向加密度惩罚,RePlAce、ePlace 这一路)把几十上百万个单元在二维平面上摊开。这个模型里,「单元不能重叠」不是硬约束而是一个密度惩罚项——目标函数鼓励散开,但最终解里仍然存在少量重叠、单元中心不在行位(site)上、行方向(row orientation)没对齐、跨电源域边界、压到 placement blockage 等问题。
这不是工具的缺陷,而是问题结构决定的:如果把「完全不重叠、全部贴格」作为硬约束直接放进全局优化,问题就变成离散组合问题,百万变量规模下无解可求。所以工程上把问题切成两段——连续近似先求一个「结构上对」的解,再由布局合法化把它「修」成离散合法的解。两段之间的信息损失,就是合法化要付的代价,也是它的全部技术含量所在。
合法化的硬约束清单,按来源可以分成四类。第一类是行结构约束:每个标准单元必须落在某条 row 的某个 site 上,row 有高度(track 数)、有 site 宽度、有翻转方向(N/FS 交替),多高度单元(double-height、triple-height 的时钟缓冲、复杂时序单元)必须跨对应数量的连续同向 row。第二类是重叠约束:任何两个单元(含 macro、blockage、well tap、endcap 这些先放下去的固定物)的 bounding box 不允许相交,well tap 与 endcap 布局 讲的那些先置单元就是合法化的「地形」。第三类是区域约束:fence/region/guide 划定的软性或硬性归属区、电压域(voltage area)边界,voltage area 与 floorplan 有完整讨论。第四类是工艺规则类:先进节点的 Vt 规则、implant 层边界、site 子类型(有的 site 只能放特定 cell family)、fin 对齐等。

这张图是三步的位置关系。读图的要点是「信息单向流动」:全局布局的连续解是合法化的唯一输入,合法化一旦把某个单元从全局解的位置挪走,这个「挪」就是纯损失——全局布局已经把线长和密度的权衡揉进了那个位置里。这就引出下一节的核心概念。
二、位移最小化:合法化的第一目标函数
位移(displacement)的定义很直白:单元合法化后的位置与全局布局给出的位置之间的距离。度量上有两种口径——单个单元的欧氏距离或曼哈顿距离,以及全局的总位移(sum of displacement)和最大位移(max displacement)。工业界报告里两个都会看:总位移反映整体扰动量,最大位移捕捉「最倒霉的那个单元被扔了多远」。
为什么位移最小化是第一目标而不是时序、线长直接当目标?因为全局布局的解已经编码了时序驱动的信息——现代全局布局是 timing-driven 的,关键路径上的单元被拉得更近,net weight 高的 net 在半周线长里权重大。合法化阶段如果直接重算时序再来一轮优化,一是太贵(百万级单元的增量时序分析开销),二是会和全局布局的解打架——你等于否定了上一阶段的成果。位移最小化是一个聪明的代理目标(proxy):合法化越接近全局解,全局布局已经优化好的时序和线长就被保留得越多。这个「忠实于上游解」的思路在 EDA 里反复出现,CTS 的 useful skew 之前不碰布局也是同一逻辑。
一个经验数字帮你建立量级感:一个健康的全局布局加合法化组合,总位移折合成「平均每单元移动」大约在一到三个 row 高度以内,max displacement 在几十个 site 宽度量级。如果报告里平均位移超过五六个行高,或者一大片区域的单元被同方向推走,那不是合法化算法差,是全局布局交的解局部密度太高——密度惩罚没摊开,或者 blockage/macro 之间的通道塞了太多逻辑。这时候正确动作是回到全局布局调密度目标、加 cell padding(见 布局拥塞与 cell padding),而不是指望合法化算法更聪明。

这张图把三个位移口径和它们的工程判读放在一起。位移报告是合法化质量的体温计,但它测的其实是上游的病——这是读报告时最容易搞反的因果关系。
还有一个细节:位移最小化在实践中通常是带权重的。时序关键单元、clock 网络相关单元的位移权重更高,宁可让非关键单元多走几步也要保住关键单元的位置。这个权重表来自上游的时序分析结果,是合法化「忠实于全局解」原则的细化——不是忠实于每个单元的绝对位置,而是忠实于全局解里「哪些位置重要」的排序。
三、合法化算法:从行吸附到 Abacus 类插入
布局合法化的算法族可以按「解空间怎么搜」分成三代思路,实际商用工具往往是混合体。
最朴素的是行吸附(row snapping):把每个单元直接贴到最近的行位上,然后处理冲突。冲突处理用局部扩散——两个单元压在一起就把其中一个往旁边空位推。这个方法快,但在高密度区域会连锁反应:一个单元的推挤引发一串推挤,最后总位移失控。它只适合密度很低的区域或作为别的算法的后处理。
第二代是把合法化建模成运输问题或最小费用流:行上的空位是供给,单元是需求,位移代价是边权,解一个全局分配。这个思路的最优性很好,但「一个单元占连续多个 site」「多高度单元」这类约束让纯网络流模型变得笨重,实际多用于单高度单元占绝对主流的设计,或作为混合算法的子问题求解器。
第三代也是当前学术和工业界的主流,是 Abacus 类(Tetris/Abacus 一脉)的插入式算法。思路是:按某种顺序逐个处理单元,每处理一个,在所有候选行里找到「插入该单元后该行总位移代价最小」的位置,插入动作本身是把行内已有单元左右推挤腾出空间——行内推挤用动态规划精确求解,保证行内不重不漏且代价最小;跨行的选择则枚举或用上界剪枝。这个结构把指数问题拆成「行内精确加跨行贪心」,质量和速度的平衡点被市场验证过,后续大量工作(多高度单元扩展、区域约束扩展、位移权重扩展)都是在这个骨架上加约束。

这张流程图是 Abacus 类算法的骨架。两个设计决策值得记住。其一,处理顺序不是任意的:时序关键度高的单元先落位,让它们拿到离全局解最近的位置,后处理的非关键单元去吸收推挤——这就是上一节「带权位移」在算法里的具体实现。其二,「行内精确、跨行贪心」的拆分意味着算法可能把单元放进次优行:当所有行都很满时,贪心选择会积累误差,这就是为什么全局布局的密度均匀性直接决定合法化质量上限。
先进节点还有两个新变量挤进合法化。一个是多高度单元比例上升——低功耗设计里 clock cell、部分时序单元用双倍高换驱动和速度,跨行插入的推挤模型要同步维护多行状态,行内 DP 变成多行联立。另一个是 site 子类型与 Vt 规则:7nm 以下同一行内不同 cell family 对 implant 层有不同要求,插入位置除了空间合法还要「化学合法」,候选位置集合被进一步切碎。这些约束不改变算法骨架,但显著压缩了可行解空间,间接推高位移代价。
四、detailed placement:合法框架内的局部优化
合法化结束的状态是「零违规但未必最优」——位移最小化保的是全局解的忠实度,并没有在合法状态下做细颗粒度的时序和线长打磨。detailed placement(详细布局,也叫 placement refinement)接手这个状态,工作原则是:任何操作不得引入新的布局违规,只在合法邻域里做改进。
常用手段有四类。第一类是局部换位(cell swapping):同行或邻近行里两个同尺寸单元交换位置,如果交换后线长或时序改善就接受。这类操作的评估必须是增量的——只重算受影响的 net 的线长和受影响路径的时序,否则百万单元的设计上做不动。第二类是单单元微移(single-cell shifting):一个单元沿行滑动若干个 site,腾出更好的相对位置,常用于给时序关键 net 缩短几微米。第三类是行内压缩(row squeezing):把行内松散分布的单元向中间或某个方向压缩,回收零散空位,为后续 ECO 或缓冲器插入留空间——STA setup 修复之换 Vt 与 sizing 和 STA hold 修复之插缓冲 那些修复动作需要落脚点,空位质量直接决定后续修复的代价。第四类是镜像翻转(flipping):单元沿行方向做镜像,把引脚侧朝向最近的连接方向,对白赚的几微米有效。
这些手段的搜索框架一般是多轮迭代:每一轮扫描全设计或热点区域,收集候选改进操作,按时序收益排序,贪心接受,直到收益收敛或轮次耗尽。窗口大小是重要参数——窗口太小改进有限,窗口太大增量评估的组合数爆炸,工程上典型是几十到几百个单元的滑动窗口。

这张图里四种手段的共性比差异更重要:全部操作都受「不得违规」约束,全部靠增量评估支撑速度。detailed placement 的边界也由此而来——它只改善局部,不改变布局的宏观结构。如果时序问题来自 floorplan 级别的分区不合理、macro 摆放把数据流拧成了麻花,detailed placement 再努力也只是裱糊,floorplan 与 powerplan 层级的问题必须回到那个层级解决。
detailed placement 阶段通常也是时序驱动布局的最后一次全芯片机会:再往后走,CTS 时钟树综合 会把大量单元钉死(clock 网络相关逻辑一旦进树就动不得),布局的可塑性断崖式下降。所以流程上常见「place_opt 预 CTS 优化」把 legalization、detailed placement 和 incremental timing 优化打包在一起,作为 CTS 之前的收口。
五、实战:读报告、判病因、做取舍
把前面四节落成日常工作,核心是会读合法化报告并做对归因。
报告里的关键指标,按优先级排:布局违规数(必须清零,不清零 CTS 会拒收或带病继续);平均与最大位移(判全局布局健康度);各 row 的利用率分布(utilization histogram——如果某些行 95% 以上满而邻近行 60%,说明密度摊开失败);区域约束违例数(fence/region 没守住的单元数,非零通常意味着区域容量估错了);多高度单元的合法化失败数(这类单元约束最强,失败往往暴露 row 结构规划问题)。
归因决策可以归纳成一张表。
| 症状 | 大概率病因 | 正确动作 |
|---|---|---|
| 平均位移小、最大位移大且集中 | 局部密度尖峰(小区域塞爆) | 回全局布局,热点区加 padding 或调密度权重 |
| 平均位移整体偏大 | 全局利用率目标定高了 | 降 utilization target 重跑全局布局 |
| 违规集中在 macro 间通道 | floorplan 通道容量不足 | 回 floorplan 加宽通道或减通道内逻辑 |
| 多高度单元合法化失败多 | row 结构与多高度单元需求不匹配 | 检查 row 生成与 power rail 对齐 |
| 位移健康但时序劣化明显 | 合法化权重没拿到时序关键度 | 检查 timing-driven 模式与权重传递 |
这张表的共同主题是「合法化报告的异常几乎都是上游的病」。这和 PnR Innovus 流程 里反复强调的「问题在哪一级产生就在哪一级解决」是同一条纪律。
取舍层面有三条经验。其一,不要追求位移的字面最小——过分约束位移会让合法化在高密度区解不动、违规清零变慢甚至失败,合理的做法是加权位移加违规清零的死线。其二,detailed placement 的轮次要预算化:每多一轮边际收益递减,而运行时间接近线性涨,典型收敛点是二到三轮。其三,为 ECO 留余量:detailed placement 把行内空隙压得太干净,后续时序 ECO 插缓冲时找不到合法位置,就得撬动邻近单元再合法化一次——PR 时序收敛 ECO 的 what-if 流程假定有可用的空位池,这个池子是在详细布局阶段攒下的。

这张检查链是全篇的收尾动作:四个问题按顺序过,任何一个的答案是否,箭头都指回上游而不是在合法化里硬拧。布局合法化的工程质量,最终体现在这份报告有多「无聊」——零违规、位移平、空位匀,后面所有阶段才能顺。
这一篇在知识体系里的位置
本篇是 eda/ 目录物理实现线的一篇算法深文,向上承接 PnR Innovus 流程 的阶段全景与 数据流之 floorplan 与 place 交接 的数据契约,横向衔接全局布局侧的 布局拥塞与 cell padding、floorplan 侧的 floorplan 与 powerplan 和 voltage area 与 floorplan、先置单元侧的 well tap 与 endcap 布局;向下接 CTS 时钟树综合(合法布局的下一个消费者)与 ECO 侧的 PR 时序收敛 ECO、STA setup 修复之换 Vt 与 sizing、STA hold 修复之插缓冲。算法谱系的更大图景见 EDA 算法总览,LEF/DEF 里行、site、placement 状态字段的格式细节见 数据流格式之 LEF/DEF。
总结
布局合法化把全局布局的连续近似解修成零违规的离散合法解,其第一目标是带时序权重的位移最小化——因为全局解已编码了线长与时序的权衡,合法化越忠实损失越小;算法上以「行内动态规划精确推挤、跨行贪心选择」的 Abacus 类骨架为主流,detailed placement 再在合法邻域内做换位、微移、压缩、镜像四类增量局部优化;实战纪律是报告里的位移与违规异常几乎全是上游(密度、floorplan、row 结构)的病,问题在哪一级产生就回哪一级解决,同时别把行内空隙压得太干净,要给 CTS 之后的 ECO 留出可落脚的合法空位池。