茶年 · 中文维基百科

布图规划

Wikipedia · 2026-01-19 维基百科 👁 1 阅读

布图规划（）指的是在布局中用图形表示电路主要功能模块，還要指定诸如长宽比（aspect ratio）或核心利用率（core utilization）等高级参数，是物理设计后续过程，即精确布线的前提。

创建布图的设计步骤称为布图规划阶段（floorplanning），是集成电路设计设计流程中的早期阶段。

布图规划设计阶段
布图规划设计阶段包含若干步骤，目标是寻找既能让时序（timing）易于收敛的走线布局，又能在整个芯片上均匀分布功耗的布图。

  • 芯片面积估算（Chip Area Estimation）：确定芯片区域的尺寸和长宽比。估算要考虑放置宏单元（macros）、标准单元（standard cells）和I/O引脚所需的空间，同时留出足够的走线资源以保证放置与布线流程成功。通常目标核心利用率U = \frac{A_ + A_}{A_}在60%–70%左右。
  • I/O引脚定位（I/O Pad Positioning）：输入/输出引脚通常需要布置在芯片的外围。靠近I/O引脚处需要为线驱动器（line drivers）预留空间，以最小化延迟和信号劣化。
  • 宏单元放置（Macro Placement）：在宏单元放置阶段，需要将具有固定尺寸和固定引脚的大功能模块（例如存储阵列、时钟发生器或定制模块）放置在布图轮廓内。有效的宏单元放置可最小化时序关键路径长度、避免布线拥塞并保证热平衡。在放置阶段，标准单元被强制与标准单元行对齐，尽管它们可能具有多行高度。标准单元行的高度决定了每行可用的布线资源，同时也会影响功耗。
  • 电源/接地结构（Power / Ground Structures）：布图规划阶段不总是包含生成电源/接地网络过程。不过，也有一些方法基于这样的思想：如果宏单元和I/O引脚已固定，就可以进行电源网格分析，从而共同综合（co-synthesize）布图和电源/地网络。

数学模型与优化问题
在数学中，布图规划指的是将若干较小的矩形（其方向可以固定或可变）打包进一个较大的矩形的问题。大矩形和小矩形的尺寸可能是固定的（硬约束），也可能需要被优化（软约束）。此外，还可以优化一个度量，用来表示该布图对走线质量的影响。

由于各种问题都是NP困难的，若存在一个对一般布图问题的多项式时间算法，则将存在P = NP。

整数规划（Integer Programming）
当小矩形的大小和朝向固定时，可将矩形打包问题建模为一个整数线性规划（ILP）。进一步可以加入约束和变量以最小化包围盒网长（bounding-box-netlength）。设有小矩形R_1,...R_n，宽度w_1,...,w_n、高度h_1,...,h_n以及网表 \mathcal{N}_1,...,\mathcal{N}_n，以及大矩形宽度W和高度H，整数规划可表示为：

  • 目标：最小化包围盒网长

::
\min \sum_{N \in \cup_{i=1}^n\mathcal{N}_i} y_{N,t} - y_{N,b} + x_{N,r} - x_{N,l}

  • 不重叠约束

::
\begin{matrix}
x_i + w_i \leq x_j + W(1 - R_{j,i}) \\
y_i + h_i \leq y_j + H(1 - A_{j,i})
\end{matrix}
\quad \forall\ 1 \leq i \ne j \leq n

  • 相对放置的析取条件

::
R_{j,i} + R_{i,j} + A_{j,i} + A_{i,j} \geq 1 \quad \forall\ 1 \leq i \ne j \leq n

  • 网的包围盒覆盖约束

::
\begin{matrix}
x_{N,r} \geq x_i + w_i \\
x_{N,l} \leq x_i \\
y_{N,t} \geq y_i + h_i \\
y_{N,b} \leq y_i
\end{matrix}
\quad \forall\ i \in {1, \ldots, n},\ N \in \mathcal{N}_i

  • 二元变量

::
\begin{matrix}
R_{i,j} \in {0, 1} \\
A_{i,j} \in {0, 1}
\end{matrix}
\quad \forall\ 1 \leq i \ne j \leq n

  • 矩形位置变量

::
\begin{matrix}
x_i \in {0, \ldots, W - w_i} \\
y_i \in {0, \ldots, H - h_i}
\end{matrix}
\quad \forall\ i \in {1, \ldots, n}

  • 网的包围盒变量

::
\begin{matrix}
x_{N,l},\ x_{N,r} \in {0, \ldots, W} \\
y_{N,b},\ y_{N,t} \in {0, \ldots, H}
\end{matrix}
\quad \forall N \in \cup_{i=1}^n\mathcal{N}_i

对于固定的空间关系变量R_{i,j}, A_{i,j}，上面的整数规划是一个最大流问题的对偶，因此可在多项式时间内求解。

启发式方法（Heuristics）
使用不同的表示方法来描述矩形之间的空间关系（例如 O-tree、B*-tree或序列对sequence pairs），实践中提出了多种启发式算法来求解布图问题。其中一些算法通过仅考虑可切分（sliceable）布图来限制解空间，从而降低问题复杂度。

可切分与不可切分布图
可切分布图（sliceable floorplan） 是指可以按下面递归定义的布图。

  • 由单个矩形模块组成的布图是可切分的。
  • 若一个可切分布图中的某个模块被一条垂直或水平线切成两个模块，则所得的布图仍为可切分的。

可切分布图曾在早期的一些電子設計自動化工具中被广泛使用。
File:Flo-01.png|link=https://en.wikipedia.org/wiki/File:Flo-01.png|可切分布图
File:Flo-02.png|link=https://en.wikipedia.org/wiki/File:Flo-02.png|不可切分布图

外部链接

参考

#電子設計自動化

评论 (0)

  • 还没有评论，来抢沙发吧。