Routing
布线¶
- 布线 (Routing)：在布局完成后，为网表中的组件确定之间的连线。
- 输入：布局结果，网表，引脚位置，障碍物，时序约束等。
- 输出：连线路径。
- 目标：
- 最小化总线长，过孔数（vias）等。
- 满足时序和设计规则。
Steiner 树¶
- Steiner 树：允许添加额外节点（Steiner 点）接所有节点的树。
- Rectilinear Steiner 树：仅允许水平和垂直边。
- 最小 Steneiner 树问题是 NP 难问题。
FLUTE 算法¶
- 核心思想：利用预计算的查找表，将大规模问题分解为 7 个节点以内的小问题。
- Hannan 网格：通过所有节点的水平和垂直线段构成的网格。
- 线长向量（WV）：线长可以被表示为网格中线段的线性组合。每个 WV 对应了一种 Steiner 树结构。
- 潜在最优线长向量（POWV）：为了找到最优线长，可以枚举所有可能的线长向量。但是，大多数 WV 不是最优的。
- 算法步骤：
- 将大规模问题分解为多个 7 个节点以内的小问题。
- 对每个小问题，根据节点间的相对位置关系，使用查找表找到对应的 POWV 集合。
- 计算每个 POWV 的实际线长，选择最小的。
Note
FLUTE 不关心具体坐标数值，只关心相对位置关系。它跳过了尝试在哪里增加 Steiner 点的过程，直接根据形状特征从查找表中取出答案。
迷宫布线¶
Lee's Algorithm¶
- 就是 BFS。
例子¶
- S (起点): (0, 0)
- T (终点): (4, 2)
- X (障碍物)
阶段一：波浪传播 (Wave Propagation)¶
初始状态：
第 1-2 步：
S 1 2 3
1 2 3 X
X 3 . .
. . . T
第 3-5 步 (绕过障碍)：
S 1 2 3
1 2 3 X
X 3 . .
. . . T
第 6 步 (到达终点)： T 的位置被标上了 6。这说明最短路径长度为 6。
0 1 2 3 4
1 X X X 5
2 3 4 5 6(T)
3 4 5 6 .
4 5 6 . .
阶段 2：回溯 (Retrace)¶
从终点 T (标号 6) 开始，找标号为 当前-1 的邻居，直到回到 S (0)。
- Start at T(6) -> 找邻居 5
- At 5 -> 找邻居 4
- At 4 -> 找邻居 3 (注意：这里可能有多个 3，选哪走哪，或根据规则选拐弯最少的) ... 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0
最终路径 (Path)：
S > > > v
. X X X v
. . . . T
. . . . .
. . . . .
Quiz¶
- 如果将 S 和 T 的位置互换，最短路径长度会改变吗？为什么？
- 如果将 S 和 T 的位置互换，算法执行的时间会改变吗？为什么？
Akers' Coding¶
- 目标：减少内存使用。
- 思路：我们不需要知道确切的距离，只需要知道回溯的方向。只需 1 bit 或 2 bits 的循环序列即可区分前后邻居。
例子¶
初始状态：
S . . .
. . . X
X . . .
. . . T
第 1-2 步：
S 0 1 .
0 1 . X
X . . .
. . . T
第 3-5 步：
S 0 1 0
0 1 0 X
X 0 1 0
0 1 0 T
Quiz¶
- 使用 Akers' Coding 后，内存使用量相比 Lee's Algorithm 有何变化？
- Akers' Coding 是否会影响找到的路径长度？为什么？