全局布局

Global Placement

在固定物理边界下，为大量单元优化线长与空间分布。

进阶出处 2 份资料

报告问题

速览

约 1 分钟

全局布局同时处理全网连接和区域容量。HPWL给出快速线长估计，划分或解析方法提供位置候选；候选还需检查局部拥塞，并进入行合法化。

系统理解

约 2 分钟

位置变量将逻辑网表连接到物理几何。引脚位置决定估计线长，网表划分与区域划分可递归对应；解析目标则把位置代价转成可计算函数。只降低吸引型线长容易使对象聚集，因此还要考虑密度与可布性。连续优化得到的位置是候选，不是已经完成合法化和布线的版图。

接在芯片规划之后，深化位置和线长模型；再进入行合法化与总体布线。

关键参数

关键参数
参数	单位	含义
HPWL	μm	引脚边界框半周长估计
区域面积占用	1	元胞面积与可放置空间的比较
布线需求与容量	—	评估局部连接是否拥挤的不同口径

常见误区

HPWL相同就代表布线结果相同。
面积密度低就不会有布线拥塞。
解析模型的最优位置已经是可制造位置。

工程深入

12 条结论 · 1 道例题

位置变量与线长估计

定义

全局布局优化的是全部可移动对象的相对分布

给定网表、芯片区域和固定对象，全局布局为可移动单元选择位置；它同时面对线长、密度和实现约束，不是逐个元胞各自寻找离邻居最近的位置。^{1, 2}

成立条件 固定对象和可移动对象必须在输入中区分。；本页只深化位置模型，不重复既有P&R流程。

公式

半周长用包围所有引脚的矩形估计线长

一个线网的HPWL等于其所有引脚横坐标范围与纵坐标范围之和；它计算快，但不描述实际选层、障碍和绕行。^{1, 2}

\mathrm{HPWL}=\left(\max_i x_i-\min_i x_i\right)+\left(\max_i y_i-\min_i y_i\right)

xi: 第i个引脚横坐标，单位 μm
yi: 第i个引脚纵坐标，单位 μm
HPWL: 该网边界框半周长，单位 μm

成立条件 各坐标在同一平面尺度中。；引脚位置固定于当前候选布局；同一线网只统计一次。

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

教学线网的四个引脚位于(0,0)、(10,0)、(10,6)、(0,6)μm。用HPWL估计它的线长。

已知

坐标为教学假设；忽略层与障碍。
四点属于同一个线网。

步骤

Δx=10−0=10 μm，取全体引脚的横向跨度。
Δy=6−0=6 μm，取全体引脚的纵向跨度。
HPWL=10+6=16 μm，相加得到边界框半周长。

结果 HPWL为16μm。

这是当前引脚坐标下的线长估计，不是四条边逐一布线的长度。

不能外推到 多端网的实际树形连接与障碍绕行可更长；不把16μm当成已完成布线。

边界

同一HPWL不能区分全部多端连接拓扑

不同的引脚分布可能具有相同边界框，因而具有相同HPWL；实际连接树、分支点和拥塞仍可能不同。比较布局时不能只根据一个HPWL值认定实现等价。^{1, 2}

成立条件 尤其针对四端及以上线网；不把所有多端网都视为具有相同误差。

机制

线网权重改变优化关注点而非直接测出时延

对各网估计线长乘以指定权重后求和，可以把优化注意力偏向某些连接；权重反映目标设定，不会自动把简化线长模型变成完整的寄生与时序分析。^{1, 2}

成立条件 权重在候选间保持同一口径。；电气结果仍需后续模型验证。

区域分配与外部连接

机制

最小割布局将网表划分与版图区域划分对应

递归最小割布局把子网表分配到较小子区域，再继续划分，直至局部问题足够小；每一级的容量和方向选择会影响最后位置。^{1, 2}

成立条件 网表分组须与对应物理区域的容量和固定对象约束保持一致。

机制

外部引脚信息会改变局部区域的合理解

对一个子区域继续划分时，区域之外的固定端点仍牵引内部单元的位置；端点传播用边界代表点保留这种外部连接信息，避免只优化区域内部。^{1, 2}

成立条件 边界代表点是对外部连接的模型，不是新增真实电路端口。

密度与目标函数

边界

几何占用密度和布线拥塞不是同一个量

几何密度比较元胞面积与区域可放置面积，布线拥塞比较连接需求与布线资源；低面积密度也可能出现连接集中，不能用其中一个指标替代另一个。^{1, 2}

成立条件 两种指标都取决于网格、障碍和容量建模。

机制

解析布局用可计算目标近似位置代价

解析方法把位置表示为连续变量，并为线长和扩展等目标建立可优化函数；求得的是该数学模型的解，连续坐标与目标值本身不保证单元已经落到合法站点。¹

成立条件 优化结果的含义受所选目标函数、连续变量与约束模型限制。

机制

纯吸引线长目标需要配合扩展约束

仅让互连对象相互靠近会造成过密或重叠；解析布局需结合区域容量、扩展或其他密度约束，平衡互连改善与空间占用。¹

成立条件 不把数学模型中最短线长直接当作实际可制造的放置。

候选搜索与实现反馈

机制

退火候选可以包含移动与交换等邻域操作

在基于退火的放置中，移动或交换改变候选位置，再以线长、重叠或行长度等代价评价；邻域、惩罚权重与温度共同限制搜索行为。^{1, 2}

成立条件 课程中的算法只作方法示例，不把其参数作为当前工具默认值。

边界

减少总线长不等于减少最拥挤区域的需求

总线长是跨全网的聚合目标；某个候选即使降低它，也可能把更多连接压进一小片区域。应同时检查局部可布性，而不是只比较一项全局标量。^{1, 2}

成立条件 拥塞判断必须基于指定容量模型，不能仅凭示意图的疏密。

关联

阶段质量应结合后续实现检查而非单一名次

放置候选需要在同一输入约束和估计模型下比较，并继续接受合法化与布线反馈；一个模型上的较小代价并不证明所有电气和制造目标都已满足。^{1, 2}

成立条件 把线长、密度、容量和性能指标分别报告，不相互冒充。

出处

2 份资料 · 22 处引用

1
超大规模集成电路物理设计：从图分割到时序收敛
Andrew B. Kahng 等著；于永斌, 张徐亮, 徐宁等译
- 第 4 章；PDF pp.99–100；，第 85–86 页 支持：全局布局优化的是全部可移动对象的相对分布；阶段质量应结合后续实现检查而非单一名次
- 第 4 章；PDF pp.101；，第 87 页 支持：半周长用包围所有引脚的矩形估计线长
- 第 4 章；PDF pp.101–102；，第 87–88 页 支持：同一HPWL不能区分全部多端连接拓扑
- §4.2、§4.3.3；PDF pp.103、123；，第 89、109 页 支持：线网权重改变优化关注点而非直接测出时延
- 第 4 章；PDF pp.107–110；，第 93–96 页 支持：最小割布局将网表划分与版图区域划分对应
- 第 4 章；PDF pp.111–113；，第 97–99 页 支持：外部引脚信息会改变局部区域的合理解
- §4.2、§4.3.4；PDF pp.105、125；，第 91、111 页 支持：几何占用密度和布线拥塞不是同一个量
- 第 4 章；PDF pp.113–114；，第 99–100 页 支持：解析布局用可计算目标近似位置代价
- §4.3.2、§4.3.4；PDF pp.114、124–125；，第 100、110–111 页 支持：纯吸引线长目标需要配合扩展约束
- 第 4 章；PDF pp.121–124；，第 107–110 页 支持：退火候选可以包含移动与交换等邻域操作
- §4.2；PDF pp.100、104–106；，第 86、90–92 页 支持：减少总线长不等于减少最拥挤区域的需求
查看这个来源 →
2
EECS 357: Placement
Hai Zhou
- 全局布局优化的是全部可移动对象的相对分布；PDF pp.1（课件无独立书籍印刷页码） 支持：全局布局优化的是全部可移动对象的相对分布
- 半周长用包围所有引脚的矩形估计线长；PDF pp.2–3（课件无独立书籍印刷页码） 支持：半周长用包围所有引脚的矩形估计线长
- 同一HPWL不能区分全部多端连接拓扑；PDF pp.2–3（课件无独立书籍印刷页码） 支持：同一HPWL不能区分全部多端连接拓扑
- 线网权重改变优化关注点而非直接测出时延；PDF pp.13（课件无独立书籍印刷页码） 支持：线网权重改变优化关注点而非直接测出时延
- 最小割布局将网表划分与版图区域划分对应；PDF pp.4–6（课件无独立书籍印刷页码） 支持：最小割布局将网表划分与版图区域划分对应
- 外部引脚信息会改变局部区域的合理解；PDF pp.7–9（课件无独立书籍印刷页码） 支持：外部引脚信息会改变局部区域的合理解
- 几何占用密度和布线拥塞不是同一个量；PDF pp.1、13（课件无独立书籍印刷页码） 支持：几何占用密度和布线拥塞不是同一个量
- 退火候选可以包含移动与交换等邻域操作；PDF pp.10–14（课件无独立书籍印刷页码） 支持：退火候选可以包含移动与交换等邻域操作
- 减少总线长不等于减少最拥挤区域的需求；PDF pp.1（课件无独立书籍印刷页码） 支持：减少总线长不等于减少最拥挤区域的需求
- 阶段质量应结合后续实现检查而非单一名次；PDF pp.1、13（课件无独立书籍印刷页码） 支持：阶段质量应结合后续实现检查而非单一名次
查看这个来源 →

关键参数

常见误区

位置变量与线长估计

#全局布局优化的是全部可移动对象的相对分布

#半周长用包围所有引脚的矩形估计线长

已知

步骤

#同一HPWL不能区分全部多端连接拓扑

#线网权重改变优化关注点而非直接测出时延

区域分配与外部连接

#最小割布局将网表划分与版图区域划分对应

#外部引脚信息会改变局部区域的合理解

密度与目标函数

#几何占用密度和布线拥塞不是同一个量

#解析布局用可计算目标近似位置代价

#纯吸引线长目标需要配合扩展约束

候选搜索与实现反馈

#退火候选可以包含移动与交换等邻域操作

#减少总线长不等于减少最拥挤区域的需求

#阶段质量应结合后续实现检查而非单一名次

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

EECS 357: Placement