总体布线

Global Routing

在粗粒度资源图上协调线网拓扑与共享容量。

进阶出处 3 份资料

报告问题

速览

约 1 分钟

总体布线先确定连接经过哪些区域，再检查资源是否被超额预订。各网独立最短并不保证能同时布通；排序、候选树选择和拆线重布共同协调全网。

系统理解

约 2 分钟

把芯片分为区域后，可将可用通路表示成带容量的图。连接树提供多端线网的拓扑，容量限制决定不同线网是否能共同采用这些路径。图解能暴露资源瓶颈，但省略局部导体与过孔几何，所以还须通过详细布线验证。

接在布局合法化之后，把物理位置转为粗粒度连接方案，再交给详细布线。

关键参数

关键参数
参数	单位	含义
方向容量	条	不同方向或层的可用连接资源
溢出	条	需求超过容量的正部分
线网顺序	—	顺序求解中的资源占用次序

常见误区

所有线网各自最短就一定全网最优。
总体零溢出代表已经完成工艺签核。
不同图模型中的节点具有相同物理含义。

工程深入

12 条结论 · 1 道例题

图模型与资源

定义

总体布线为线网分配粗粒度连接区域

给定放置和网表，总体布线选择线网经过哪些区域以及如何连接端点；具体轨道、金属形状和过孔的实现留给详细布线。^{1, 2}

成立条件 总体解必须保留原网表要求的连通关系。；粗网格可用于标准单元实现；不是把每个网格点当成实际引脚。

机制

图的节点和边含义必须随模型说明

网格图通常把区域作为节点、相邻区域通路作为边；通道交点图则把交点作为节点、通道作为边。容量放在哪个对象上取决于模型，不能混用两张图的标注。^{1, 2}

成立条件 比较算法前先明确节点、边与容量的物理对应。

边界

水平和垂直容量应分别核算

同一区域中两个方向的布线需求与可用资源可以不同。把它们加成一个总数，可能掩盖某一方向已经耗尽而另一方向仍有余量的情况。¹

成立条件 限定具有方向性资源的区域或分层图。；容量来自选定层、障碍和规则模型，不从芯片面积直接推定。

公式

边溢出量只统计超过容量的正部分

对一条布线图边，把需求减去容量，负值按零计，得到该边的溢出。零溢出说明没有超额预订这一资源，不等于完成全部详细设计规则检查。^{1, 2}

O(e)=\max\left(0,u(e)-c(e)\right)

O(e): 图边e的溢出资源数量，单位条
u(e): 图边e的布线需求，单位条
c(e): 图边e的可用容量，单位条

成立条件 需求与容量采用相同资源单位。；此式是对容量不等式的直接改写，不是新的经验工艺公式。

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

教学网格三条边的容量为[4,3,5]条，需求为[6,2,5]条。求各边及总溢出。

已知

全部数值为教学假设，各条需求使用同一资源口径。
只考察容量，不模拟真实轨道和间距规则。

步骤

O1=max(0,6−4)=2 条，第一条边超出容量2条。
O2=max(0,2−3)=0 条；O3=max(0,5−5)=0 条，空余容量不作为负溢出来抵消其他边。
ΣO=2+0+0=2 条，逐边溢出求和。

结果各边溢出为[2,0,0]条，总溢出2条。

总剩余容量不能替代逐边容量检查。

不能外推到 不从本例推出实际制造层的轨道数或保证可布性。

路径与拓扑

边界

所有线网各自最短不保证能够同时布通

若多个最短连接争用同一有限资源，独立最短路可能相互冲突。全网解需要在容量限制下协调，有的线网应绕行而不是全部保持各自最短。^{1, 2}

成立条件 线网共享同一固定容量图。

机制

Steiner点是连接树允许加入的分支位置

多端线网的直角连接树可以在原引脚之外引入分支点，以改变总线长；它与只用原引脚作树节点的生成树模型不同。^{1, 2}

成立条件 本条为无障碍平面曼哈顿模型。；实际层分配、绕障和时序目标可能改变优选拓扑。

边界

最小线长树不自动满足时序和障碍要求

无障碍几何模型中的最短连接树，只优化该模型的长度。真实连接还受障碍、容量以及关键端点的路径性能限制，不能把几何最短直接当成电气最优。^{1, 2}

成立条件 明确所比较的树属于同一端点集合。

机制

顺序布线中的先后次序会改变后续可用空间

逐网布线时，先完成的线网占据资源，后续线网只看到更新后的剩余容量。因此线网优先级和重排策略属于求解过程，而不是结果展示顺序。^{1, 2}

成立条件 容量在每次连接后更新。；本条不主张某一种固定排序对全部设计最好。

求解与反馈

机制

并发规划可以把候选连接放进共同约束

整数规划可为线网列出候选连接，并用共享的容量不等式约束它们的选择。目标最优只针对列出的候选集合，不说明未列入的全部布线拓扑也已遍历。^{1, 2}

成立条件 候选连接及各自资源占用已知。；完整布通模型要求每网选一路；允许未布网的变体另有选择约束。

机制

拆线重布针对瓶颈重新分配已有连接

当资源冲突阻止连接时，可以拆开部分已布线网，再将受阻网和被拆网重新布线；选择哪些网、采用什么顺序都会影响结果。^{1, 3}

成立条件 只拆布线实现，不删除原网表要求的电气连接。

边界

重布迭代需要明确停止条件

拆线重布可因连接全部完成而结束，也可因时间等资源限制而停止。算法停止本身不能当作全部连接已经满足容量的证据，应另外报告未解决冲突。^{1, 3}

成立条件 将终止原因与剩余违规数量分别记录。

关联

总体容量解仍需接受详细实现反馈

总体图简化了局部几何，详细布线还要分配轨道、过孔并满足设计规则。总体无溢出是有用的阶段检查，但不是可制造版图签核。¹

成立条件 不把粗网格的容量与工艺DRC逐项等同。

出处

3 份资料 · 22 处引用

1
超大规模集成电路物理设计：从图分割到时序收敛
Andrew B. Kahng 等著；于永斌, 张徐亮, 徐宁等译
- §5.1；PDF pp.132–133；，第 118–119 页 支持：总体布线为线网分配粗粒度连接区域
- §5.4；PDF pp.139–140；，第 125–126 页 支持：图的节点和边含义必须随模型说明；水平和垂直容量应分别核算
- §5.3、§5.7；PDF pp.136、156；，第 122、142 页 支持：边溢出量只统计超过容量的正部分
- §5.1、§5.3；PDF pp.132、138–139；，第 118、124–125 页 支持：所有线网各自最短不保证能够同时布通
- §5.6.1；PDF pp.141–142；，第 127–128 页 支持：Steiner点是连接树允许加入的分支位置
- §5.6.1；PDF pp.142；，第 128 页 支持：最小线长树不自动满足时序和障碍要求
- §5.1、§5.6.2；PDF pp.133–134、147–148；，第 119–120、133–134 页 支持：顺序布线中的先后次序会改变后续可用空间
- §5.7.1；PDF pp.156–158；，第 142–144 页 支持：并发规划可以把候选连接放进共同约束
- §5.7.2；PDF pp.160–162；，第 146–148 页 支持：拆线重布针对瓶颈重新分配已有连接
- §5.7、§5.7.2；PDF pp.156、161–162；，第 142、147–148 页 支持：重布迭代需要明确停止条件
- §5.1、第 6 章导言；PDF pp.133、168；，第 119、154 页 支持：总体容量解仍需接受详细实现反馈
查看这个来源 →
2
EECS 357: Global Routing
Hai Zhou
- Lecture 5；PDF pp.1–3；讲义无独立书籍印刷页码 支持：总体布线为线网分配粗粒度连接区域
- Lecture 5；PDF pp.1–2；讲义无独立书籍印刷页码 支持：图的节点和边含义必须随模型说明
- Lecture 5；PDF pp.3；讲义无独立书籍印刷页码 支持：边溢出量只统计超过容量的正部分
- Lecture 5；PDF pp.5–6、10；讲义无独立书籍印刷页码 支持：所有线网各自最短不保证能够同时布通
- Lecture 5；PDF pp.14–16；讲义无独立书籍印刷页码 支持：Steiner点是连接树允许加入的分支位置
- Lecture 5；PDF pp.3、14；讲义无独立书籍印刷页码 支持：最小线长树不自动满足时序和障碍要求
- Lecture 5；PDF pp.9–10；讲义无独立书籍印刷页码 支持：顺序布线中的先后次序会改变后续可用空间
- Lecture 5；PDF pp.11–12；讲义无独立书籍印刷页码 支持：并发规划可以把候选连接放进共同约束
查看这个来源 →
3
EECS 357: Maze Routing
Hai Zhou
- Lecture 6；PDF pp.18；讲义无独立书籍印刷页码 支持：拆线重布针对瓶颈重新分配已有连接；重布迭代需要明确停止条件
查看这个来源 →

关键参数

常见误区

图模型与资源

#总体布线为线网分配粗粒度连接区域

#图的节点和边含义必须随模型说明

#水平和垂直容量应分别核算

#边溢出量只统计超过容量的正部分

已知

步骤

路径与拓扑

#所有线网各自最短不保证能够同时布通

#Steiner点是连接树允许加入的分支位置

#最小线长树不自动满足时序和障碍要求

#顺序布线中的先后次序会改变后续可用空间

求解与反馈

#并发规划可以把候选连接放进共同约束

#拆线重布针对瓶颈重新分配已有连接

#重布迭代需要明确停止条件

#总体容量解仍需接受详细实现反馈

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

EECS 357: Global Routing

EECS 357: Maze Routing