【EDA】Steiner Routing（斯坦纳布线）

第五章：Steiner Routing（斯坦纳布线）

在VLSI物理设计中，斯坦纳布线（Steiner Routing）的目标是在给定一组引脚（Pins）的情况下，找到连接它们的最小线长或最小延迟的路径，允许引入额外的斯坦纳点（Steiner Points）以优化性能。第五章聚焦五种经典算法，涵盖线长优化、延迟优化和约束驱动布线，以下是详细介绍：

1. L型斯坦纳布线算法（L-Shaped Steiner Routing）

核心目标

将初始最小生成树（MST）转换为L型路径，通过旋转边的方向最小化线长，确保无交叉且结构规则。

核心思想（Ho et al., 1990）

• ** separable MST构建**：使用Prim算法构建MST，权重优先选择更短、更高且靠右的边，确保树结构适合L型转换（图5.2-5.4）。
• 自底向上处理：对每个子树计算两种可能的L型方向（上L和下L），选择重叠最大（线长减少最多）的方向（图5.6-5.10）。
• 自顶向下确定方向：根据根节点的最优方向，递归确定子树的L型方向，生成无交叉的布线树（图5.11）。

关键步骤

1. 构建 separable MST：以节点b为根，按权重3元组（距离、y差、x坐标）选择边，生成初始MST（图5.2-5.4）。
2. 子树方向计算：
   • 对每个节点v，计算子树在两种L型方向下的重叠面积（图5.6：(\Phi_l(v))为下L，(\Phi_u(v))为上L）。
   • 合并时选择重叠最大的方向，例如节点c选择下L型以最大化与父边的重叠（图5.6a）。
3. 生成最终布线树：通过方向优化，将初始MST的欧几里得边转换为L型，线长从32减少到28（图5.11）。

优势与应用

• 优点：结构规则，易于实现，适合标准单元布线；保证线长优于直接MST。
• 缺点：依赖初始MST质量，可能无法找到全局最优斯坦纳点。
• 典型场景：FPGA布线，需规则化路径以适配互连资源。

2. 1-Steiner点插入算法（1-Steiner Routing）

核心目标

通过迭代插入单个斯坦纳点，逐步优化MST的线长，分为Kahng-Robins的精确法和Borah的启发式法。

核心思想

• Kahng-Robins算法（穷举法）：
  1. 在Hanan网格上枚举所有可能的1-Steiner点，计算插入后的MST线长（图5.14c）。
  2. 选择线长减少最大的点，重复直到无改进（图5.15-5.17，线长从20→18→17→16）。
• Borah启发式算法：
  1. 计算（节点，边）对的增益：(gain = \text{最长边长度} - \text{斯坦纳点到节点距离})（图5.13）。
  2. 按增益降序插入斯坦纳点，删除最长边，更新MST（图5.23，线长从20→17）。

关键步骤（以Borah算法为例）

1. 增益计算：对每条边和每个节点，计算插入斯坦纳点后的线长减少量（图5.18：({b, (a,c)})对增益为2）。
2. 迭代插入：每次选择最大增益对，插入斯坦纳点并更新树结构（图5.23b-c）。
3. 终止条件：所有（节点，边）对增益≤0时停止。

优势与应用

• 优点：启发式算法复杂度低（O(n²)），适合大规模网络；精确法保证局部最优。
• 缺点：穷举法复杂度高（O(n⁵)），启发式法可能陷入局部最优。
• 典型场景：ASIC全局布线，快速优化长距离互连的线长。

3. 有界半径布线算法（Bounded Radius Routing）

核心目标

在给定半径约束下构建最小线长的斯坦纳树，平衡最长路径（半径）和总线长，包括BPRIM和BRBC算法。

核心思想

• BPRIM（Bounded Prim）：
  • 扩展Prim算法，每次添加节点时检查是否违反半径约束（(dist(s, x) + dist(x, y) ≤ (1+\epsilon)R)），否则寻找“合适边”（图5.26-5.28）。
• BRBC（Bounded Radius Bounded Cost）：
  • 基于深度优先遍历（DFS）扩展MST，添加边以确保半径≤(1+2ε)R，线长≤(2+2/ε)MST线长（图5.31）。

关键步骤（BPRIM为例，ε=0）

1. 初始化：以源点s为根，半径 bound=12（图5.25）。
2. 迭代扩展：
   • 选择最近邻节点，若距离超界则回溯寻找合适边（如节点d通过s直接连接而非经c，图5.26d）。
3. 结果对比：ε=0时半径严格为12，线长56；ε=0.5时半径18，线长49（图5.29）。

优势与应用

• 优点：可调参数ε平衡半径和线长，适合时序驱动布线（小ε控制半径）。
• 缺点：BPRIM可能遗漏更优解，BRBC复杂度较高。
• 典型场景：高速电路布线，需限制最长路径以满足时序约束。

4. A-tree算法（最小最短路径斯坦纳树）

核心目标

构建斯坦纳树，确保每个源到汇的路径为最短路径（无冗余长度），同时最小化总线长。

核心思想（Cong et al., 1993）

• 安全移动（Safe Moves）：
  1. Type-1：合并两棵树，选择西北/东南方向最近节点（图5.34）。
  2. Type-2/3：向下/向左扩展树，避免阻塞（图5.35-5.36）。
• 节点阻塞计算：
  • 计算节点在西北（NW）、东南（SE）方向的阻塞节点，确定移动方向和距离（图5.33）。

关键步骤

1. 初始森林：每个汇点为独立根节点（图5.37：(R(F_0)={a,b,c,d,e,f})）。
2. 安全移动迭代：
   • 计算dx/dy/df值（水平/垂直距离、支配节点距离），选择合法移动（如节点a的Type-2移动，图5.35）。
   • 逐步合并根节点，最终形成单根树（图5.39i，线长18）。

优势与应用

• 优点：保证所有路径为最短路径，适合延迟敏感设计（如时钟树）。
• 缺点：复杂度高，依赖精确的阻塞计算。
• 典型场景：时钟网络布线，要求零延迟偏差（Zero Skew）。

5. Elmore延迟优化算法（ERT/SERT）

核心目标

直接最小化Elmore延迟（考虑RC寄生参数），分为ERT（无斯坦纳点）和SERT（含斯坦纳点）。

核心思想

• Elmore延迟公式：
  [
  t_{\text{elmore}}(n_i) = r_d \cdot C_{n_0} + \sum_{e_v \in \text{path}(n_0,n_i)} r_{e_v} \left( \frac{c_{e_v}}{2} + C_v \right)
  ]
  其中 (r_d) 为驱动电阻，(C_{n_i}) 为子树电容，(r_{e_v}/c_{e_v}) 为边的电阻/电容。
• ERT算法：
  • 迭代添加最近邻节点，选择使最大Elmore延迟增加最小的连接（图5.41-5.43）。
• SERT算法：
  • 允许插入斯坦纳点，评估边-节点对的延迟增益，选择最优连接（图5.45-5.47）。

关键步骤（ERT为例）

1. 初始树：仅含源点s（图5.40）。
2. 迭代扩展：
   • 计算每个候选节点的Elmore延迟，选择使最大延迟最小的连接（如第二步选择s→c而非a→b，图5.41b）。
3. 结果：最终树最大延迟4630ps（图5.44），优于传统MST的线长优化。

优势与应用

• 优点：直接优化时序指标，适合深亚微米电路（RC延迟主导）。
• 缺点：依赖精确的RC参数，计算复杂度高。
• 典型场景：高速互连线布局，如片上网络（NoC）的关键路径优化。

6. 算法对比与总结

核心技术对比

1. 线长vs延迟：
   • L型、1-Steiner、BPRIM聚焦线长；A-tree保证最短路径；ERT/SERT直接优化延迟。
2. 精确vs启发式：
   • Kahng的1-Steiner和A-tree为精确法，BPRIM/BRBC和Borah为启发式，适合不同规模电路。
3. 约束处理：
   • BPRIM/BRBC处理半径约束，A-tree处理路径最短约束，ERT/SERT处理延迟模型。

实际应用选择

• 快速布线：L型算法或Borah的1-Steiner，适合早期布局规划。
• 时序关键：A-tree或SERT，确保路径最短且延迟最低。
• 大规模电路：BPRIM结合ε参数，平衡半径和线长，避免局部最优。

7. 关键贡献与局限

• L型算法：首次将MST转换为规则化路径，奠定斯坦纳布线的工程化基础。
• 1-Steiner：证明迭代插入斯坦纳点的有效性，启发后续启发式算法。
• A-tree：理论上保证最短路径，为时钟树综合提供关键技术。
• Elmore算法：推动从几何优化到电学性能优化的转变，适应深亚微米设计需求。

第五章的算法覆盖了从几何线长优化到电学延迟优化的完整 spectrum，为VLSI布线提供了从基础结构到高性能约束的解决方案，是现代EDA工具（如Synopsys StarRC）的核心技术支撑。