综述04 物理综合

这一篇在干嘛？

传统流程里综合（决定逻辑长什么样）和物理设计（决定逻辑放哪里）是两段分离的：综合时不知道互连延迟，布局时又改不了综合的决定。如今关键路径上 70~80% 的延迟来自互连，这堵墙必须拆——物理综合就是拆墙的一系列技术。

为什么要”物理”综合

两个尴尬事实构成了动机：

• 综合阶段：映射算法只能用粗糙延迟模型（很多干脆假设互连零延迟），“好”的映射解放到真实位置上可能变差；
• 物理设计阶段：手里只有综合给的网表，早期”坏决定”（烂的结构、多余的逻辑级数）已经无法纠正。

FPGA 还有个特殊限制：不能像 ASIC 那样给单元调大小（sizing）来换时序，所以 FPGA 物理综合更依赖改结构这一类手段。主要技术分四类：逻辑聚类、布局驱动映射、布局驱动复制、其他（重定时/重布线/映射聚类一体）。

逻辑聚类：打包进逻辑块

现代 FPGA 的逻辑块内含 N 个逻辑单元，聚类（clustering）就是把映射后的 LUT 网表装进一个个逻辑块。聚类质量直接影响跨块互连的数量——而跨块连线比块内连线慢得多。

VPack：按吸引力装盒

VPack 的思路像装电梯：一次装一个块。每轮选出”已用输入最多”的未聚类单元当种子放进当前簇，然后按吸引力（该单元与当前簇共享的输入输出数）依次吸入不违反容量约束的单元，装满或吸不动了就开新簇。目标是最小化簇的总数（省面积）。

T-VPack：给吸引力加上时序

T-VPack 用三级延迟模型（单元延迟、块内延迟、块间延迟，后者远大于前者），核心目标变为减少关键路径上的跨块连接。差异在种子和吸入的选择都按时序紧迫度加权：

• 连接紧迫度：$\mathrm{Criticality}(i)=1-\mathrm{slack}(i)/\mathrm{MaxSlack}$——slack 越小越紧迫；
• 种子选”被最紧迫连接驱动”的单元；
• 吸引力公式变成时序与面积的双头权衡：

$$\mathrm{Attraction}(B)=\alpha \cdot \mathrm{Criticality}(B)+(1-\alpha )\cdot {\mathrm{Attraction}}_{\text{area}}(B)/G$$

白话解释：单元 B 的吸引力 = 时序紧迫度项（权重 $\alpha$，推荐 0.75）+ 面积项（权重 $1-\alpha$），$G$ 是归一化因子。时序紧迫度本身还带一个小尾巴 $\epsilon \cdot \text{total\_path\_affected}$——涉及的关键路径越多，平票时越优先。T-VPack 时序远好于 VPack，连最终面积都更好（因为它倾向把低扇出网络整体吸收进簇，减少了跨簇网络数）。

更进一步

• 聚类+布局一体化：T-VPack 的软肋是延迟模型太糙（没有真实互连延迟）。解法是把单元在簇之间的搬移做成退火布局引擎里的一种移动——布局的同时随时重组簇。在高利用率、大量”无关打包”（为了塞满把不相干的逻辑也装一起）的场景下特别有效。
• 布通性驱动聚类：不是塞得越满越好——基于 Rent 规则的算法会故意让一些簇不满，让簇网表和器件结构”空间上均匀匹配”，减轻布线压力。
• 多级聚类：对 APEX 这类两级层次架构，两级性能驱动聚类平均降低 15% 延迟。

布局驱动映射：映射时看着地图选

映射时的单位延迟模型在布局后经常失灵。除了少数”映射布局同时做”的尝试（受限于组合问题的复杂度，往往两头都做不精），更成功的是迭代式：映射 → 布局 → 把布局信息回注 → 重新映射 → 合法化 → 布局精修，循环往复。

关键技术点：

• 边延迟查表：给定两个位置，从预存的表里查出这两点间互连的估计延迟——比”固定互连延迟”假设真实得多。
• 重分解：把已映射网表拆回门级（dmig 的扩展，分解过程中把互连延迟算进到达时间传播），再用割枚举映射器重映射，打标阶段同样计入互连延迟。
• 拥塞控制：新映射解可能出现多个单元挤在同一位置。算法分 bins（不同粒度）统计面积溢出并给惩罚，用前几轮积累的拥塞信息引导下一轮映射决策。
• 时序驱动合法化：把重叠单元按可用 slack 挪到附近空位，最后退火精修。

实验：时序改善超过 12%，重映射带来的面积代价很小。

布局驱动复制：把弯路拉直

逻辑复制（logic replication）是简单粗暴但极其有效的招：把一个单元复制一份，让扇出分流。好处是能摊薄负载、隔离关键路径；如果只用目标器件上的空闲单元，面积零成本。

一个直观例子

设 A、B、D、E 四个 pad 位置固定，单元 C 为它们服务。若 C 只有一份，为最小化最大路径延迟，它得放在四个 pad 围出的区域的中心——每条路径都绕路经过中心，时序糟糕。但若复制 C 成两份，分别挪到靠近 A/E 的位置，路径全部拉直。

迭代复制算法

核心概念是局部单调性：对单元 C（扇入 P、扇出 N），定义

$$\mathrm{deviation}(C)=\mathrm{distance}(P,C)+\mathrm{distance}(C,N)-\mathrm{distance}(P,N)$$

白话解释：绕行量 = （P 到 C 的距离 + C 到 N 的距离）− P 到 N 的直线距离。大于 0 就说明”P→C→N”这段路在绕远——C 站错了位置。算法反复挑关键路径上绕行量大的单元复制，把副本放到能减小绕行量的位置，扇出在原件与副本间重新分配（极端情况下全部扇出走副本，等于搬了家），再用”ripple move”合法化。对 VPR 结果有明显改善。

两个升级

• 局部单调性管不了全局性绕行（s→a→b 和 a→b→t 各自局部单调，但 s→t 整体绕行）。增强算法先圈出时序关键区段，复制整个区段生成”复制树”（每个节点单扇出、叶子多扇出的叶 DAG），再用 S-tree 嵌入的动态规划同时考虑时序和线长来安放——延迟降低超过 14%，约是局部法的两倍。

• 把复制直接做进退火引擎：每轮退火结束时按当前布局做布局驱动复制，引入可行域/超可行域概念全局改善关键路径单调性，还能多次复制后自动去冗余。叠加路径计数的网络加权后，相对 VPR 平均降低延迟超过 25%。

其他技术

重定时 + 布局一体化

传统重定时在综合阶段做，用的是不靠谱的互连延迟估计。一体化算法三步走：

1. 重定时感知布局：把 VPR 的紧迫度公式里的 slack 换成 CycleSlack——重定时意义下，这条互连还能加多少延迟而不破坏性能目标；
2. 按布局后的真实互连延迟做重定时，代价函数刻意选”对布局扰动小”的方案；
3. 增量聚类与布局，安放重定时新引入的寄存器。

相对”先重定时后布局”的顺序流程，平均提速 19%。

SPFD 重布线：只动线、不动格子

**Rewiring（重布线）**通过删线加线改变连接而不碰单元位置——对布局零扰动，这对物理综合极具吸引力：时序上可以用不紧张的连接替换紧张的，布通性上可以把拥塞区的连接挪到宽松区。

传统 ATPG 式重布线不改变任何节点的内部功能，利用不上 K-LUT 的可编程灵活性。SPFD（Sets of Pairs of Functions to be Distinguished，待区分函数对集合）突破了这一点：它用一对对”必须被区分开的函数”来表达一个引脚的功能容许范围——任何能区分所有函数对的实现都合法。这意味着重布线时可以顺手改掉节点的内部函数，机会多得多。

局部 SPFD 重布线要求替代线的终点与目标线相同，全局版（可以接到目标的支配节点上，即所有通往 PO 路径的必经点）放得更开。数据说话：ATPG 法能给约 10% 的线找到替代，局部 SPFD 25%，全局 SPFD 36%。

映射 + 聚类一体化

分开做映射和聚类会次优。反例：3 输入 LUT、簇容量 3。延迟最优映射给出 5 个 LUT，随后延迟最优聚类的关键路径含 3 段跨簇连接；而一个多花 1 个 LUT（6 个）的映射解（靠节点复制）聚类后只有 2 段跨簇连接——因为跨簇延迟远大于簇内延迟，多花面积买更少的跨簇跳数是赚的。

联合算法用动态规划在”同时考虑映射与聚类”的延迟模型下求每个节点的最优延迟，再同时生成两份解，配合减少复制开销的启发式。相比分离流程：同延迟模型下性能提升 25%（面积多 22%），VPR 布局布线后仍好 12%。

常见坑/误区

物理综合的性能收益必须在布线后验证。多数技术只做到布局层、不关心布通性，在高利用率设计（实践中最常见）下，布局阶段预测的提速可能被布线阶段的拥塞吃光。同理，逻辑复制虽是”零面积”妙招，但前提是用空闲单元——高利用率设计里复制会挤占布线资源，反而伤布通性。

通关标准：

学完本篇你应该理解：为什么综合与物理设计分离是 FPGA 性能的大敌；VPack/T-VPack 的吸引力机制与时序扩展；布局驱动映射的”迭代回注”循环与拥塞控制；逻辑复制拉直路径的原理与 deviation 公式；SPFD 重布线为什么比 ATPG 法机会更多。

自测：T-VPack 相比 VPack 的本质改进是什么？

VPack 只按共享 IO 数（面积吸引力）装箱，目标是最少簇数；T-VPack 把时序紧迫度（基于 slack）掺进种子选择和吸引力公式（α=0.75 偏时序），目标是减少关键路径上的慢速跨块连接。副产品是把低扇出网络整体吸进簇内，跨簇网络变少，最终面积反而也更好。

自测：deviation 公式衡量什么，大于 0 意味着什么？

deviation(C) = P到C的距离 + C到N的距离 − P到N的直线距离，衡量信号从 P 经 C 到 N 绕了多少冤枉路。大于 0 说明 C 坐在 P、N 连线”之外”，这条局部子路径非单调——C 是复制/搬移以拉直路径的候选对象。

自测：SPFD 相比 ATPG 式重布线的核心优势是什么？

ATPG 法在重布线时不许改变任何节点的功能，浪费了 K-LUT”可实现任意 K 输入函数”的灵活性；SPFD 用”待区分函数对”表达每个引脚的功能容许区间，重布线时可以同时修改节点内部函数——能找到替代线的比例从约 10% 提升到 25%（局部）/36%（全局）。

自测：为什么"延迟最优映射+延迟最优聚类"的串联仍可能次优？

两个阶段各自最优≠联合最优。映射 unaware of 聚类边界时，可能选出一个 LUT 数最少（或深度最浅）但跨簇连接很多的解；而多花一两个 LUT 的解若能减少昂贵的跨簇跳数，在跨簇延迟远大于簇内延迟的现实中反而更快。

自测：重定时感知布局为什么要把 slack 换成 CycleSlack？

普通 slack 回答”这条线还能慢多少而不破坏性能”；CycleSlack 回答”考虑重定时自由度后，这条线还能慢多少”。布局阶段用 CycleSlack 加权，能让”重定时潜力大的连接”上的单元在布局时就被鼓励放在一起，为后续重定时留出最大化空间。