3.4 布局规划：模拟退火与表示模型
3.4 布局规划：模拟退火与表示模型
本节摘要：布局规划（floorplanning）决定大模块（硬核 IP、存储、模拟块、大宏单元）在芯片上的骨架位置，是物理实现里组合优化味道最浓的一环。本节讲清问题的双目标结构（面积与线长）、切片结构为何表达力不足，重点拆解 sequence pair 这一表示如何用两个排列编码任意非重叠布局，以及它如何与 2.4 节的模拟退火严丝合缝地拼装成完整算法。SVG 图展示表示模型的解码过程。
一块地怎么分：双目标问题
布局规划的输入是十几到几百个矩形模块（含长宽已固定的硬模块与面积固定、长宽比可调的软模块），输出是一个互不重叠的摆放方案。目标函数通常是两项加权和：包络面积（所有模块的外包矩形）与互连线长（模块间连线的估计长度，布局阶段用包围盒周长近似，见 3.5 节的展开）。两项天然冲突：为了线短把强通信的模块挤在一起，轮廓可能变得狭长、碎片面积浪费；为了省面积码得整齐，通信最近的模块可能被甩到对角。另外还有约束项：某些模块必须贴边（IO 附近的宏）、必须共线、必须避开电源环。问题的自由组合空间是模块数量的阶乘级，精确算法只对个位数模块可行。
切片与切片树：第一代表示
最早的工程表示是切片布局（slicing）：整个可用区域反复递归地"一刀竖切或横切"，每次切出的两半再各自继续切。切片结构可以用一棵二叉树（切片树）编码，树叶是模块、内部节点是切刀方向。它的最大优点是评估极快：给定树与叶子顺序，包络面积可用简单递归算出，软模块的长宽比也能在此框架里连续优化（经典的 stockmeyer 算法在树上一遍合并出最优尺寸组合）。退火在切片树上的移动算子是"旋转切刀、交换子树、调整模块顺序"三种，天然适配。
切片的致命限制是表达力：并非所有非重叠布局都是可切的。经典的五个方块拼成的风车布局（pinwheel）就无法由任何切片序列产生——而它恰恰可能是某组模块的最优解。可切布局只占所有布局空间的极小份额，用它当搜索空间意味着最优解可能根本不在场。这一教训在 EDA 算法史上反复出现：表示决定了搜索空间的边界，选错表示，再好的搜索引擎也是空转。突破来自 1990 年代中期的两个"完备表示"：BSG（bounded-sliceline grid）与 sequence pair，以及稍后的 O 树。本节重点讲 sequence pair，因为它与退火的组合最干净。
sequence pair：两个排列装下所有布局
sequence pair 用两个长度为 n 的排列（正序 S+、逆序 S−）编码任意模块互不重叠的布局。解码规则只依赖两模块在两个排列中的相对顺序：若模块 a 在 S+ 与 S− 中都排在 b 之前，则 a 在布局上严格位于 b 的左侧；若 a 在 S+ 中在前、S− 中在后，则 a 位于 b 的上方。一组满足这两种关系的偏序约束必然可行（无环即可），最长路径计算给出每个模块的坐标：x 坐标 = S+ 与 S− 同序关系构成的 DAG 上到该点的最长路长度，y 坐标同理在反序 DAG 上计算。解码一次是 O(n log n)（用最长递增子序列技巧），n 是模块数——几百个模块的解码在微秒级。
这个表示的三种性质使它成为退火的天作之合。第一，完备性：任何非重叠布局都存在对应的 sequence pair，最优解必然在搜索空间内。第二，邻域移动的自然性：交换 S+ 中两个元素、交换 S− 中两个元素、旋转一个模块，三种简单移动就能覆盖整个空间——这正是 2.4 节退火所需的 moveSet。第三，评估的解析性：线长目标函数对解码结果可直接计算，无需任何修补步骤。三者合起来，退火的每一步都是"轻扰动、快速解码、精确评估"。
图：sequence pair 的解码机制
从骨架到全局布局的交接
布局规划产出的是大模块骨架，之后标准单元的百万级布局（3.5 节）会围绕这个骨架展开——宏单元的位置作为固定障碍参与全局布局，密度地图上它们的占地被直接扣除。工程上布局规划与全局布局往往是同一工具里交替迭代的两步：全局布局发现某个宏的落点引发拥塞，反馈给规划阶段重新微调宏位置。另外两个实用话题：软模块定形（长宽比在规划阶段初步确定，细布局阶段允许微调）；电源规划（电源环与电源条的走线通道要在规划阶段预留，否则布线阶段无处下笔）。这些细节共同的教训是：规划阶段省下的十分钟，会让布线阶段多熬十个钟头——约束的引入宁早勿晚。
表示族的版图再补一块拼图。与 sequence pair 同期的 O 树（B*-tree）用一棵有序二叉树编码紧凑布局，解码 O(n) 比 sequence pair 更快，轮廓计算天然增量，在纯面积目标上常跑得更快；BSG（bounded-sliceline grid）用网格占位思想先给完备性、后处理零散空间。三者的选择经验：目标以面积为主、模块数百量级，O 树顺手；线长与约束复杂、需要交换类移动算子，sequence pair 更稳。再补一个工程数字：几百宏单元的布局规划，退火几十万次移动、单机分钟到十分钟级收敛——这与后续百万标准单元的全局布局（分钟级连续优化）在规模与算力上相差悬殊，也是两层流程并存的现实理由。
退火在这类问题上的实效数字再给一组：宏单元几十到三百个的设计，退火迭代通常在十万到百万次移动量级收敛，每次移动的解码与评估在微秒级，总耗时分钟级；同样的模块数，若用穷举或整数规划求解器精确求解，时间预算直接爆炸。工程折中还有一个常见动作：先用退火跑多个随机种子取最优，再用确定性局部交换精修——随机搜索负责全局形状，确定性交换负责最后一成的质量，两者分工明确。这套"随机找形、确定性收尾"的组合模式在布局规划之外（时钟树、引脚排列）同样通用。
本节要点回顾
- 双目标结构：包络面积与互连线长此消彼长，外加贴边、共线、避让等工程约束。
- 切片表示的教训：评估快但表达力不足，风车布局不可编码——表示错了搜索引擎空转。
- sequence pair：两个排列加同序异序规则完备编码布局，解码 O(n log n)。
- 与退火严丝合缝：三种移动算子覆盖全空间，解码与评估解析可算。
- 骨架交接：宏位置作为固定障碍喂给全局布局，拥塞反馈触发规划微调。
- 约束宁早勿晚：电源通道与软模块定形在规划阶段处理，晚处理代价数量级上涨。