跳转至

Placement

布局

  • 布局 (Placement)：将逻辑单元映射到芯片上的物理位置。
  • 输入：网表，单元形状，pin 位置。
  • 输出：单元的物理位置。单元之间没有重叠。
  • 目标：最小化连线长度 (wirelength)，时序 (timing)，可绕线性 (routability) 等。

全局布局

模拟退火

  • 基本思想：通过模拟物理退火过程，逐步降低系统温度，寻找最优或近优解。
  • 关键设计：
    • 移动策略：如何生成新状态
    • 成本函数：如何评估状态质量
  • TimberWolf：
    • 成本函数：\(C = C_1 + C_2 + C_3\)
      • 线长估算 (半周长法)：\(C_1 = \sum {HPWL}\)
      • 重叠惩罚：\(C_2 = \sum(O(i, j) + \alpha)^2\), \(O(i, j)\) 为单元 \(i\) 和 \(j\) 的重叠面积。允许移动时的临时重叠，通过惩罚逐渐消除。
      • 行长平衡：\(C_3 = \sum|l(r) - d(r)|^2\)，其中 \(l(r)\) 为实际行长度，\(d(r)\) 为目标行长度。每行单元总宽度应接近行长度，避免某些行过满而其他行稀疏。
    • 移动策略：
      • M1: 选择一个单元，移动到一个新位置。
      • M2: 选择两个单元，交换位置。
      • M3: 选择一个单元，旋转方向。
  • Dragon2000
    • 优化思路：多级优化。将电路划分成多层的粗粒度的格子（bins），在格子之间使用模拟退火算法，加速超大规模电路的布局收敛。

Quiz

  1. 模拟退火算法中温度 T 的作用是什么？(单选)
    1. 控制成本函数的权重
    2. 控制算法运行时间
    3. 控制接受较差解的概率
    4. 控制单元移动的距离
  2. 为什么在移动时允许单元重叠？
  3. 为什么多级优化可以加速模拟退火收敛？

划分

  • 基本思想：将连接紧密的单元聚集在一起，反复地将电路划分为多个分区。
  • 关键设计：
    • 目标函数：最小化分区间连线数 (cut size)，保持分区平衡 (balance)。
    • 划分算法
    • 划分线（cutline）选择

Quiz

  1. 划分算法中，为什么要保持分区平衡？

解析式布局 Analytic placement

  • 基本思想：将布局问题转化为数学优化问题，通过求解优化问题得到单元位置。
  • 关键设计：
    • 目标函数
    • 约束条件
    • 优化方法

线长的估计方法

模型 描述 距离度量 精度 平滑度 特点
Min. Steiner Tree (MST) 最小斯坦纳树 曼哈顿 ⭐⭐⭐⭐⭐ ⭐ 金标准，最接近实际布线长度，但计算极其复杂且不可导。
Clique Model 团模型 (全连接) 曼哈顿/欧氏 ⭐ ⭐⭐ / ⭐⭐⭐⭐⭐ 悲观估计。将 \(k\) 个引脚两两相连。由于边数随 \(k^2\) 增长，会严重高估长度。
HPWL 半周长导线长度 曼哈顿 ⭐⭐⭐⭐ ⭐⭐ 常用。计算包围所有引脚的最小矩形。对于 2-3 个引脚完全准确，对多引脚属于乐观估计。
Star Model 星型模型 欧氏 ⭐⭐⭐ ⭐⭐⭐⭐⭐ 添加一个虚拟中心点，所有引脚连向中心。由于其高度平滑（\(C^\infty\) 连续），常用于解析式布局器。

例子

假设一个 Net 包含 4 个引脚，分别位于正方形的顶点：\(A(0,1), B(1,1), C(0,0), D(1,0)\)。

  • HPWL (最快): 计算 Bounding Box。

\(X_{span} = 1, Y_{span} = 1\) \(HPWL = 1 + 1 = \mathbf{2}\)

  • Clique Model (最悲观): 连接所有组合（AB, AC, AD, BC, BD, CD）。

边数 = \(k(k-1)/2 = 6\) 条边。长度总和远超 2，会产生巨大的“引力”将单元拉向一点。

  • Star Model (最平滑): 在中心 \((0.5, 0.5)\) 增加一个虚拟点 \(S\)。

连接 \(SA, SB, SC, SD\)。这种模型没有拐点，在数学优化（梯度下降）中表现极佳。

Quiz

  1. 举例说明，为什么 HPWL 是一种乐观估计？
  2. 举例说明，为什么 Clique Model 是一种悲观估计？
  3. 为什么 Star Model 适合用于解析式布局器？

Quadratic placement

  • 核心思想：将导线视为弹簧，通过最小化总能量（平方距离之和）来确定单元位置。
  • 目标函数：最小化所有连线的平方距离加权和。（线长模型可以选择 HPWL 或 Clique Model 或 Star Model）
  • 优点：形式简单，易于求解。适合大规模电路。
  • 缺点：单元重叠严重（所有单元倾向于挤在中心）。
  • 解决方法：
    • 去除重叠（Rough legalization）：通过线性映射，将
    • 循环迭代：优化目标->满足约束->优化目标->满足约束...

Quiz

  1. 为什么 Quadratic placement 会导致单元重叠？
  2. 为什么在去除重叠后需要重新优化目标函数？

Nonlinear placement

  • 核心思想：将布线长度和单元密度同时放入一个连续可微的函数中。
  • 目标函数：\(C = \min_{x,y} WL(x,y) + \lambda D(x,y)\)
    • WL: 平滑的线长估计
    • D: 利用类似静电场的函数替代离散的重叠计算。

Quiz

  1. 为什么要将单元密度作为目标函数的一部分？
  2. 在 Nonlinear placement 中，如果参数 λ 过大，布局结果会发生什么变化？