布图规划

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

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

该问题的各种数学抽象已有研究。

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

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

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

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

 整数规划（Integer Programming） 
当小矩形的大小和朝向固定时，可将矩形打包问题建模为一个整数线性规划（ILP）。进一步可以加入约束和变量以最小化包围盒网长（bounding-box-netlength）。设有小矩形，宽度、高度以及网表 ，以及大矩形宽度和高度，整数规划可表示为：

 目标：最小化包围盒网长



 不重叠约束



 相对放置的析取条件



 网的包围盒覆盖约束



 二元变量



 矩形位置变量



 网的包围盒变量



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

并非所有的空间关系选择都对应一个可行的放置。包含所有可行放置的关系集合称为完备（complete）。目前已知对完备关系集合规模的上界由Silvanus和Vygen给出：他们证明了当空间关系数为时，完备集合的规模至多为；并给出下界，其中。

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

 可切分与不可切分布图 
可切分布图（sliceable floorplan） 是指可以按下面递归定义的布图。"The Electrical Engineering Handbook", Richard C. Dorf (1997) 

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

可切分布图曾在早期的一些電子設計自動化工具中被广泛使用。可切分布图可以方便地用二叉树（更具体地说是K-d树）表示，这些树对应于切分的顺序。更重要的是，当问题限制为可切分布图时，许多对布图来说NP困难的问题可以得到多项式时间的算法。Sarrafzadeh, M, "Transforming an arbitrary floorplan into a sliceable one ", Proc. 1993 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-93), pp. 386-389.

 外部链接 
 The Chip Planner of the PLAYOUT System 

 参考 

Category:電子設計自動化