布局合法化

Placement Legalization

把候选位置调整为满足行、站点和不重叠约束的放置。

进阶出处 4 份资料

报告问题

速览

约 1 分钟

把单元中心点拉开还不够。合法化要考虑整个单元宽度、兼容行和可用空间，并尽量保留全局布局；位移指标不能替代线长和布线检查。

系统理解

约 2 分钟

全局候选可含连续坐标与残余重叠，标准单元实现却要求落在允许的行和站点中。贪心合法化依序选择最近可用位置；Abacus等方法还会在同行内联动调整已放单元，以减少累计移动。约束可行、位移小和互连目标好是不同判断，增量改尺寸或插缓冲后还需复查。

在全局布局之后恢复离散可行位置，再进入更局部的优化和布线；复用既有DRC解释，不将合法化当作签核。

关键参数

关键参数
参数	单位	含义
行与站点	—	允许放置的位置和兼容几何约束
单元宽度	μm	决定行内占用区间
移动代价	μm或μm²	相对全局目标位置的位移度量

常见误区

最近的空中心点就是合法位置。
移动最少就保证最终线长最小。
已经合法化一次，改网表后就不需要再检查。

工程深入

12 条结论 · 1 道例题

合法性与位置约束

定义

合法化把候选位置转换为行内无重叠放置

合法化要把标准单元安排到允许的行和位置，并去除相互重叠，同时尽量保留全局布局已经形成的分布；其目标不只是让中心点各不相同。^{1, 2}

成立条件 本页基本模型为矩形、单行高标准单元；其他高度需额外兼容规则。

公式

同一行按序相邻单元需满足宽度约束

若同一行中单元i排在j之前，以左边界为坐标，则无重叠至少要求xj≥xi+wi；检查中心点距离而不考虑单元宽度会漏掉重叠。^{1, 2}

x_j\ge x_i+w_i

xi: 前一个单元左边界坐标，单位 μm
xj: 后一个单元左边界坐标，单位 μm
wi: 前一个单元宽度，单位 μm

成立条件 矩形单元采用同一坐标和长度单位。；这个不等式只检查同一行的相邻区间，不替代其他位置与工艺约束。

边界

最近位置必须同时属于可行的行内空间

离目标位置几何上最近的点可能已经被占用或使单元越出行边界；合法化应在可放下整个单元的候选中选位置，而不是先按最近点固定再忽略冲突。^{1, 2}

成立条件 给定行边界、已占区域和单元尺寸后判断可行性。

移动代价与算法选择

机制

按横坐标排序是贪心合法化的一种处理顺序

Tetris式方法按全局位置的横坐标排序，再依次安排单元；先处理的对象会占用后续对象可用的空间，因此排序规则属于算法输入的一部分。^{1, 2}

成立条件 只说明这一类算法，不把横坐标排序写成全部合法化算法的必要步骤。

边界

只追求短位移仍需检查网络代价

位置移动较少有助于保留原布局，但不能仅靠位移指标判断互连结果；应同时查看合法性、线长或布线表现等不同指标。^{1, 2}

成立条件 不把某一算法论文的特定基准改善百分比推广为通用性能。

机制

Abacus在插入新单元时可重调同行已放单元

与把已放对象完全固定的贪心方式相比，Abacus会在试放新单元时重新优化同一行中的已有对象，以降低该行累计移动。²

成立条件 限定ISPD2008 Abacus原始模型，不声称所有现代合法器都采用该机制。

公式

固定行内顺序时可最小化加权平方位移

Abacus的PlaceRow子问题在给定同行单元顺序后，最小化相对全局横坐标的加权平方位移，同时满足无重叠约束；这不是直接优化原网表线长。²

J=\sum_i e_i(x_i-x_{i0})^2

J: 水平加权平方移动代价，单位 μm²
ei: 第i个单元的无量纲移动权重，单位 1
xi: 合法化后的左边界横坐标，单位 μm
xi0: 全局布局给出的目标横坐标，单位 μm

成立条件 本条限定原始PlaceRow水平优化模型；权重为非负，行兼容与边界另行满足。；例题进一步限定整数站点，结果通过枚举核验，不据此声称原论文解决全部离散变体。

例题：动手算一次教学假设，可复算

教学单行宽6μm，两个宽2μm单元保持a在b前，目标左边界为0.5μm和1.5μm。允许左边界落在1μm整数站点，等权平方位移最小的合法位置是什么？

已知

全部数值为教学假设。
单元位于同一兼容行，行边界[0,6]μm；只考虑宽度、不重叠与整数站点。

步骤

xb≥xa+2 μm，0≤xa、xb≤4 μm，把宽度、不重叠和行边界转成候选约束。
(xa,xb)=(0,2) μm，枚举满足约束的整数站点对并比较平方位移。
J=(0−0.5)²+(2−1.5)²=0.50 μm²，两单元各移动0.5μm，权重均为1。

结果最小代价合法位置为(0,2)μm，J=0.50μm²。

本例说明无重叠约束会使两个目标位置必须联合调整。

不能外推到 这不是对多行、障碍、不同高度或真实线长目标的通用解。

机制

行内重叠可通过合并相邻簇联动消除

PlaceRow按行内顺序处理单元，遇到重叠时将有关单元合并成簇，更新簇的宽度与目标位置，再检查是否与更左侧簇冲突。²

成立条件 限定原始Abacus模型；簇是优化中间结构，不是修改网表连接。

边界与实现检查

边界

合法化和全局扩展针对不同尺度的问题

全局扩展处理大范围的分布与密度，而行合法化通常以已经大致分散的全局布局为起点，修复离散行位置及残余重叠；不宜把严重堆积留给最后一步。^{1, 2}

成立条件 阶段分工不意味着工具实现必须采用固定次数的串行流程。

关联

改尺寸或插入缓冲之后应重新检查位置合法性

原放置合法不意味着网表变化后仍合法；单元变宽或新增缓冲会改变行内占用，因此需再次检查并按需合法化。^{1, 3}

成立条件 只说明几何与容量变化，不把重新合法化当作功能、时序或DRC签核。

边界

工具接受的行类型和区域约束决定适用范围

实际合法化还可能受多高度单元、区域限制或被障碍切开的行影响；使用算法前应确认实现支持哪些约束，不能把单高度完整行示例直接推广到全部版图。³

成立条件 本条以OpenROAD文档列出的支持范围为具体工程例，不使用其默认参数作工艺规则。

关联

合法解仍可在保持约束的局部操作中改进

得到合法放置后，可以尝试相邻交换或小范围移动以改善目标，但接受的新候选仍必须保持行与不重叠约束；合法性是可行性条件，不是目标已经最小的证明。^{1, 4}

成立条件 仅讨论保持合法性的局部邻域；不是所有交换都会改善线长。

出处

4 份资料 · 20 处引用

1
超大规模集成电路物理设计：从图分割到时序收敛
Andrew B. Kahng 等著；于永斌, 张徐亮, 徐宁等译
- §4.4；PDF pp.126；，第 112 页 支持：合法化把候选位置转换为行内无重叠放置；改尺寸或插入缓冲之后应重新检查位置合法性；合法解仍可在保持约束的局部操作中改进
- §4.4；PDF pp.126–127；，第 112–113 页 支持：同一行按序相邻单元需满足宽度约束
- §4.4 Tetris；PDF pp.127；，第 113 页 支持：最近位置必须同时属于可行的行内空间；按横坐标排序是贪心合法化的一种处理顺序
- §4.4；PDF pp.127；，第 113 页 支持：只追求短位移仍需检查网络代价
- §4.3.4、§4.4；PDF pp.125–126；，第 111–112 页 支持：合法化和全局扩展针对不同尺度的问题
查看这个来源 →
2
Abacus: Fast Legalization of Standard Cell Circuits with Minimal Movement
Peter Spindler; Ulf Schlichtmann; Frank M. Johannes · 2008
- Background：row structure、no overlap、minimal movement；PDF pp.3 / slide 3 支持：合法化把候选位置转换为行内无重叠放置
- PlaceRow：相邻单元不重叠约束；PDF pp.12 / slide 12 支持：同一行按序相邻单元需满足宽度约束
- Overview和试插入各行示例；PDF pp.5–7 / slide 5–7 支持：最近位置必须同时属于可行的行内空间
- Abacus Overview与Sorting；PDF pp.5–6 / slide 5–6 支持：按横坐标排序是贪心合法化的一种处理顺序
- Movement与Results的不同质量指标；PDF pp.21–23 / slide 21–23 支持：只追求短位移仍需检查网络代价
- Abacus Overview与已放单元重调示例；PDF pp.5、8–10 / slide 5、8–10 支持：Abacus在插入新单元时可重调同行已放单元
- PlaceRow目标与动态规划说明；PDF pp.12–13 / slide 12–13 支持：固定行内顺序时可最小化加权平方位移
- PlaceRow聚簇、更新和回查过程；PDF pp.14–20 / slide 14–20 支持：行内重叠可通过合并相邻簇联动消除
- Background：在global placement与legal placement之间的任务；PDF pp.3 / slide 3 支持：合法化和全局扩展针对不同尺度的问题
查看这个来源 →
3
OpenROAD Documentation: Detailed Placement
SangGi Do; Mingyu Woo; James Cherry; OpenROAD contributors
- Detailed Placement介绍；网页无固定页码，核对2026-10-22 支持：改尺寸或插入缓冲之后应重新检查位置合法性
- Detailed Placement支持列表；网页无固定页码，核对2026-10-22 支持：工具接受的行类型和区域约束决定适用范围
查看这个来源 →
4
EECS 357: Placement
Hai Zhou
- Neighborhood Structure与Cost Function；PDF pp.11–13（课件无独立书籍印刷页码） 支持：合法解仍可在保持约束的局部操作中改进
查看这个来源 →

关键参数

常见误区

合法性与位置约束

#合法化把候选位置转换为行内无重叠放置

#同一行按序相邻单元需满足宽度约束

#最近位置必须同时属于可行的行内空间

移动代价与算法选择

#按横坐标排序是贪心合法化的一种处理顺序

#只追求短位移仍需检查网络代价

#Abacus在插入新单元时可重调同行已放单元

#固定行内顺序时可最小化加权平方位移

已知

步骤

#行内重叠可通过合并相邻簇联动消除

边界与实现检查

#合法化和全局扩展针对不同尺度的问题

#改尺寸或插入缓冲之后应重新检查位置合法性

#工具接受的行类型和区域约束决定适用范围

#合法解仍可在保持约束的局部操作中改进

超大规模集成电路物理设计：从图分割到时序收敛

Abacus: Fast Legalization of Standard Cell Circuits with Minimal Movement

OpenROAD Documentation: Detailed Placement

EECS 357: Placement