综述02 布线与布局算法

这一篇在干嘛？

布线（routing）要回答”所有信号能不能在预制的导线资源里连起来、怎么连最快”；布局（placement）要回答”每个逻辑块放芯片哪个位置最好”。这两个问题是 FPGA 编译流程里最耗时也最影响质量的环节，本篇讲它们各自的经典算法框架。

布线：戴着镣铐跳舞

为什么 FPGA 布线更难

ASIC 布线可以自由铺新导线，FPGA 布线只能使用出厂时就做好的资源：现成的线段、可编程开关、多路选择器。目标是 100% 布通（routability），但资源是死的，所以”布得通”本身就是挑战。

FPGA 布线流程一般分三步：布线资源图生成 → （可选）全局布线 → 详细布线。

布线资源图：把芯片抽象成一张图

所有布线算法的起点是把 FPGA 建模成一张布线资源图（routing-resource graph）：

• 顶点：逻辑块的输入/输出引脚 + 布线通道里的线段；
• 边：连接两个顶点的可编程开关。单向开关（缓冲器）画成有向边，双向开关（传输晶体管）画成一双向边对。

为了处理等价引脚（逻辑块上功能相同的多个引脚，用哪个都行），图中引入 source 顶点（连到所有等价输出引脚）和 sink 顶点（连到所有等价输入引脚）。

现代 FPGA 有上百万个逻辑块，整张图巨大。实际做法是：为架构的基本 tile 建一张图，然后复制拼接成全芯片的图。VPR 工具的一大贡献就是提供了一套架构描述语言，用户给出架构参数（引脚数、F_c、线段类型分布等），工具自动生成布线资源图——这在”芯片还没造出来、先给架构做定量评估”的场景里特别关键。

全局布线：协商式迭代路由

全局布线用的是粗粒度资源图：每个通道（而不是每根线段）是一个顶点，容量就是通道里的轨道数。算法要给每个网络找一条路径，满足 (i) 通道容量不超载、(ii) 时序约束。

最成功的框架是 PathFinder/VPR 使用的协商式（negotiation-based）迭代布线，思想可以概括成”先乱连，再吵架，吵着吵着就理顺了”：

1. 每轮把所有网络都按当前代价最短路布一遍，允许超载（congestion）；
2. 超载的通道”涨房租”——被占用的资源代价变高；
3. 下一轮重布时，抢不到资源的网络会主动改道；
4. 反复迭代直到没有超载。

VPR 的代价函数：

$$\mathrm{Cost}(n)=b(n)\cdot h(n)\cdot p(n)+\mathrm{BendCost}(n,m)$$

白话解释：$b(n)$ 是基础成本（这根资源本身贵不贵），$h(n)$ 是历史拥堵惩罚（这根资源过去被抢过多少次，欠的账越滚越多），$p(n)$ 是当前拥堵惩罚（这一轮有没有超载），BendCost 惩罚拐弯（拐弯意味着换线段、加开关、变慢）。三个连乘的设计意图是：只要一项为 0 就不惩罚——历史欠账归零的资源重新变得有吸引力，避免网络在坏路径上”锁死”。

多引脚网络用迷宫扩展（maze expansion，即 Dijkstra/广度优先式搜索）逐个接入最近的引脚。

详细布线：两条路线

全局布线给出粗路径后，详细布线要把它”落地”成具体用哪根线段。两条经典路线：

路线一：两步法。 CGE/SEGA 布线器先为每条全局路径枚举所有可行详细路径（放进一张 expansion graph），再反复”选当前代价最低的详细路径、删同网络的其他候选、删与它冲突的其他网络候选”。注意：如果某条详细路径成了某条全局路径的唯一选择（essential route），必须优先布它，否则可能把别的网络逼死。路径代价综合考虑用了几段线、有没有”大材小用”（短连接占用长线段）、剩余替代路径多少等。

路线二：SAT 精确求解。 把详细布线写成一堆布尔约束交给 SAT 求解器：连通性约束保证每个网络有路可走（比如”网络 N 可以用竖直通道 i 的 0/1/2 号任意轨道”），互斥性约束保证两个网络不共用同一资源（比如”通道 m 里网络 A 不能与 B、C 同轨道”）。SAT 有解就得到合法布线，无解就证明这个全局方案在该架构上必然布不通——这是精确判定。缺点是 NP-complete，规模大了慢，但 SAT 求解器的进步在持续缓解这个问题。

全局+详细一步走

全局/详细两步法的隐患是脱节：全局布线看不到线段类型和开关的细节分布，可能给出”图上通、实际死”的方案。FPGA 上这个问题尤其严重，于是出现了合二为一的做法：

• GBP/OGC（贪心装箱）：把多引脚网络拆成两引脚子网络，把线段归入若干”轨道域”（能用开关互连的线段集合），然后用 best-fit-decreasing 的装箱启发式把子网络塞进轨道域。简单粗暴，效果意外地好。
• Tracer-fpga（模拟进化）：先全部初布（允许违规），再按”布线树长度 + 违规数”给每个网络打分，反复掀桌子重布（rip-up and reroute）。妙处在于它用概率选择要重布的网络——偶尔把”没违规的好网络”也拿来重布，反而跳出了贪心局部最优。
• VPR：把协商式全局布线引擎直接搬到详细资源图上，一步到位。精心调校的参数让它当时在轨道使用量上全面胜过 CGE、SEGA、GBP、OGC、Tracer-fpga 等所有对手。

布线中的时序优化

布通只是及格线，还要快。FPGA 里可编程开关多，布线延迟占大头，时序优化大致四招：

1. 布线顺序：slack 小（紧张）的网络先布，免得被迫绕远路——几乎每个时序驱动布线器都用这招。
2. 布线树拓扑：对关键网络用”从源到每个汇都走最短路”的树（Steiner arborescence），牺牲总长度换源-汇延迟。
3. slack 分配：先布的网络容易把 slack 吃光，所以要提前按负载电容、扇出等因素把 slack 预分给各网络。
4. 网络加权：把时序驱动的布线问题形式化成约束优化，用**拉格朗日松弛（Lagrangian relaxation）**求解——拉格朗日乘子天然就是各源-汇对的”权重”，指导网络按重要程度抢资源。

VPR 的时序驱动版把延迟项揉进代价函数：

$$\mathrm{Cost}(n)=\mathrm{Crit}(i,j)\cdot \mathrm{delay}(n)+[1-\mathrm{Crit}(i,j)]\cdot b(n)\cdot h(n)\cdot p(n)$$

白话解释：$\mathrm{Crit}(i,j)\in [0,1]$ 是该连接的时序紧迫度，决定”要快”和”要省”各占多大权重。Crit=0 时完全不管延迟，Crit=1 时完全不管拥堵——后者很危险（可能布不通），所以 VPR 对最关键网络也只取 0.99，永远留 1% 给拥堵约束。

布局：把逻辑块摆到对的地方

布局决定每个逻辑单元的位置，而位置决定互连长度——在 FPGA 里互连是性能瓶颈（可编程开关比 ASIC 互连慢得多），所以布局对最终性能影响极大。主流方法四大流派：

流派一：模拟退火（Simulated Annealing）

VPR 的看家本领，也是研究界的事实标准。基本动作是交换两个逻辑块的位置（其中一个可以是空块），按”温度”控制接受劣解的概率，逐步降温收敛。

打个比方：模拟退火像摇一杯珍珠奶茶——高温时疯狂摇晃（接受各种乱换位，跳出局部最优），降温后轻摇慢晃（只接受小幅改善），最后珍珠均匀分布（布局收敛）。

VPR 的三个关键增强：

• 温度调度：接受率特别高或特别低时加快降温，把时间花在”最出活”的温度区间（部分移动被接受、部分被拒的阶段）。
• 移动范围限制：控制交换距离，让接受率尽量长期维持在 0.44 附近。
• 线性拥堵成本：处理通道容量不均匀的架构，计算速度与传统的半周长线框模型一样快，但布通性更好。

时序驱动版在目标函数里加了时序项，难点有二：每次移动都会改变 slack 分布，全部重算是天文开销——VPR 的办法是每个温度周期结束才重算一次 slack；时序和线长两个目标量纲不同——用自归一化（各自除以上一轮的总值）解决。

后来的 PATH 算法解决了另一个盲区：路径共享。一条连接若出现在许多关键路径上，理应获得更高权重，但路径数量是指数级的。PATH 用线性时间的方法把所有路径按 slack 加权并分摊到每条边上，等效于”枚举全部路径再统计”。配合同样的退火框架，平均降低最长路径延迟 15.6%，零运行时开销。

流派二：划分式（Partitioning-based）

思想是递归二分：把电路切成两半放在芯片左右两半，再各自细切。代表工具 PPFF 用多级划分器 hMetis 做引擎，特色是除了最小化切边数之外还做端点对齐（terminal alignment，尽量让同一网络的端点落在同一条水平/垂直通道里），并优化同一层级各区域的划分顺序（等价于一个可用贪心最优求解的线性排序问题）。最后用 legalization + 低温退火收尾。效果：质量比 VPR 略差，但快 3~4 倍。

流派三：嵌入法（Embedding-based）

代表 CAPRI，思路很有意思：给 FPGA 量身定做一个”距离”的度量空间。先画出等延迟等高线（如下图），可以看到 FPGA 路由网格的”等距面”既不是欧氏距离的圆，也不是曼哈顿距离的菱形——它由架构里的线段种类决定。然后定义一种以”过开关的总延迟”为距离的度量，把网表图嵌入这个度量空间（二次分配问题，用矩阵投影 + 在线二分图匹配的启发式解），得到一个全局时序视角不错的初始合法布局，再用 VPR 低温退火局部打磨。

结果：相对纯 VPR，关键路径布线后延迟中位数改善 10.1%，总布局时间缩短 2 倍，而 CAPRI 本身只占总时间 4.8%。

流派四：快速布局与布局规划（Floorplanning）

芯片逼近百万逻辑块时，退火太慢，得靠多级化提速：

• UFP：先做多级聚类（每级簇大小取 2 的幂，如 64/4/4），在粗层级上做低温退火（对象少、速度快），逐级展开细化时用父簇位置的均值作为子节点的初始位置。UFP 是文献里第一个多级布局算法。
• Frontier：利用 RTL 设计的层次结构做布局规划。把芯片划成等大的 bin，宏模块聚成簇放进 bin，再用退火在 bin 之间交换，最后在 bin 内部填充式放置。bin 数远小于逻辑块数，所以飞快——当时比 Xilinx 商用流程快 2.6 倍。

布局布线一体化：曾经的热点

既然 100% 布通难保证，很自然的想法是边布边放：把路由器塞进退火内环（每步移动后增量布线，性能提升 815% 但慢 611 倍）；或在递归划分的每一层都做全局布线；或放置网络时同时考虑段数、段型、通道密度。但总体而言这条路收效有限——现代 FPGA 容量更大、布线资源更丰富后，问题变成了”是否还有必要一体计算”，而非”怎么算”。

常见坑/误区

评估布局算法别只看线长。FPGA 布通率和延迟强烈依赖”用了哪些线段、过几个开关”，半周长线长最短的布局未必布得通、更未必快。同样，协商式布线里把最关键网络的 Crit 设成 1.0（完全无视拥堵）是个经典错误——VPR 取 0.99 就是为了永远给布通性留余地。

通关标准：

学完本篇你应该理解：布线资源图怎么把 FPGA 抽象成图、source/sink 顶点为什么存在；协商式布线”涨房租”思想与 Cost 公式三项的含义；全局/详细两步法的脱节问题与一步式方案；模拟退火在布局里怎么用、四个布局流派各自的速度-质量取舍。

自测：协商式布线里 h(n) 和 p(n) 各管什么，为什么需要两个？

p(n) 惩罚当前迭代里的超载，管”这一轮谁超载了”；h(n) 累积历史各轮的拥堵惩罚，管”这根资源是不是惯犯”。只留 p 的话，资源一空出来大家又蜂拥而至、来回震荡；h(n) 让挨过挤的资源持续变贵，逼迫网络寻找新路径，保证收敛。

自测：SAT 布线器相对启发式布线器的独特价值是什么？

它是精确判定：SAT 有解即得到合法详细布线，无解则严格证明该全局方案在此架构上布不通。启发式布线器布不通时无法区分”暂时没找到”和”根本不存在”。

自测：为什么 VPR 布局中每步移动后不立即重算所有 slack？

每次移动只影响部分连接的延迟，全量静态时序分析代价太大。VPR 选择在每个温度周期结束时统一重算 slack，既省时间又避免代价函数系数频繁剧烈变化导致退火不稳定。

自测：CAPRI 为什么不用曼哈顿距离做延迟模型？

因为 FPGA 路由网格的等延迟面形状由架构的线段类型决定，与欧氏圆、曼哈顿菱形都不同。用错度量空间，嵌入出的”近”并不代表延迟低。CAPRI 用”过开关总延迟”定义度量，把网表嵌进这个专用空间。

自测：多级布局（如 UFP）提速的核心原理是什么？

把百万级对象的问题分层缩小：先聚类成 64 个大簇，在几十个对象上做退火极快；逐级展开时子节点继承父簇附近的初始位置。对象数在高层级指数级减少，而低温退火在好初始解上收敛也快——用”由粗到细”换掉”一次精细搜索”。