综述03 工艺映射：逻辑怎么切成 LUT

这一篇在干嘛？

工艺映射（technology mapping）是把与工艺无关的门级网络”切”成目标 FPGA 的逻辑单元（K 输入 LUT）的过程。它是设计流程中最后一次变换，切法直接决定最终的面积、速度和功耗。本篇讲映射问题的标准框架——cut 枚举 + 动态规划，以及面积/时序两条优化路线。

问题定义：用 K-LUT 盖住一张图

映射的输入是逻辑门网络（有向图：节点是门，边是连接，边上可以带权重表示中间隔了几个寄存器），输出是 K-LUT 网络。主流算法是**结构式（structural）**的：不改逻辑功能，只做”覆盖（covering）“——用一个个 K-可行锥（K-feasible cone） 盖住网络，每个锥装进一个 LUT。

先记三个关键概念：

• fanin cone（扇入锥）$O_{\nu }$：以节点 $\nu$ 为根、连同它一部分前辈构成的子网络，锥内所有路径都汇到根。可以想成”从 $\nu$ 往源头看的势力范围”。
• MFFC（最大无扇出锥）：$\nu$ 的最大一个扇入锥，锥内除根之外所有节点的扇出都留在锥内。把它整体替换成一个 LUT 时，不会漏掉锥内节点在外面的用户——这是映射的基本积木。
• cut（割）：一组节点，从这些节点”剪断”就能把根和输入隔开；如果割里节点数 ≤ K，就叫 K-可行割，正好对应一个 K-LUT 的输入集合。

注意图里一个重要现象：节点 x 同时出现在两个锥里，会被复制——复制是映射算法提高质量的重要手段，也是面积估算变难的根源（后面会反复出现）。

另一类是**函数式（functional）**映射：把映射当成布尔变换/分解来解，解空间更大但太慢，只适合小电路；近年趋势是在结构式框架里嵌入函数式探索，两全其美。

结构式映射的标准框架

整个流程三段：先用与工艺无关的技术（节点提取/替换、don’t-care 优化等）优化网络 → 分解成两输入网络（dmig 等类 Huffman 树算法）→ 覆盖。覆盖这一步绝大多数算法共享同一个动态规划骨架，分四步：

1. cut 生成/枚举
2. cut 排序（打分）
3. cut 选择
4. 生成最终映射解

排序通常按拓扑序（从输入到输出）推进，选择通常按逆拓扑序（从输出往输入）推进——先定输出端的选择，再往回铺。

Cut 枚举：全部 K-cut 一网打尽

K 是个很小的常数（3~7），所以现代算法干脆枚举每个节点的所有 K-cut，选择时灵活度最大。枚举是个自底向上的合并过程：对两输入的节点 $\nu$（扇入 $u_1,u_2$）：

$$\Phi (\nu )=\{\{\nu \}\}\cup \{c_1\cup c_2\mid c_1\in \Phi (u_1),c_2\in \Phi (u_2),|c_1\cup c_2|\le K\}$$

白话解释：节点 $\nu$ 的所有割 = 自己的平凡割（只有自己），加上两个扇入的割两两求并集，并把超过 K 个元素的丢掉。反复用这个公式、自 PI 向 PO 推一遍，每个节点的全部 K-cut 就都有了。支配割（是其他割超集的）可以删掉，不影响质量。

更早的 FlowMap 算法不是枚举所有割，而是用最大流计算直接给每个节点找一个深度最优的单割——它是第一个在多项式时间内求出深度最优映射的算法，是本领域的里程碑。

Cut 打分：面积与深度

面积打分：有效面积（effective area）

LUT 映射的面积 = LUT 总数，最小化是 NP-hard 的，只能用启发式打分。难点在于**多扇出节点与重汇聚（reconvergence）**让”局部贪心”算不准全局面积。

有效面积的思想很直观：把每个节点的面积成本平摊给它的各个扇出，这样信号被多个 LUT 共享时成本自动分摊。对割 $c$：

$$a(c)=\sum _{u\in c}\left[a(u)/|\mathrm{output}(u)|\right]+A_c$$

白话解释：割 $c$ 的面积成本 = 割内每个节点 $u$ 的累计成本除以它的扇出数（因为它被几个用户共享，每人摊一份），加上本 LUT 自身的面积 $A_c$。节点自身的成本取其所有割中最小的那个。

有效面积在”不复制节点”的映射下是精确的；一旦允许复制就会低估——下图里 LUT(u) 顺带盖住了 w，w 的 LUT 实际完全是为 $\nu$ 服务的，但平摊公式只给它记了一半的账。

结论：有效面积是真实面积的下界，算法实际结果离下界的距离是衡量映射器好坏的标尺。

时序打分：标签（label）

映射阶段没有布局信息，所以时序目标通常就是最小化 LUT 级数（映射深度）。FlowMap 引入的动态规划打标法：PI 的标签为 0，对节点 $\nu$ 的每个割：

$$l(c)=\max \{l(u)+D_c\mid \forall u\in c\}$$

白话解释：如果用割 $c$ 把 $\nu$ 盖成一个 LUT，那么信号到达 $\nu$ 的时间 = 割内所有输入节点的标签取最大值，再加这一级 LUT 的延迟 $D_c$——关键路径由最慢的那个输入决定。节点的标签取所有割中的最小值，从 PO 往回选割并追踪，就得到深度最优解。

面积优化算法

PRAETOR：让扇出共享同一个割

在有效面积打分之上加两招：

• 鼓励公共子割：同一节点的不同扇出如果给该节点”指定”了不同的割，就会被迫复制该节点。PRAETOR 给节点编号，对有效面积并列的割按字典序统一排序，保证大家选得一致——扇出们指向同一个割，复制自然就少了。
• 两遍 cut 选择：第一遍找出”不可复制”的节点（non-duplicable），宣布它们为割边界，第二遍时把包含它们的割全部剔除。下图例子里，第一遍得到 4 个 LUT（$\nu$ 被复制），第二遍禁止包含 $\nu$ 的割后，逼着 $u_1$ 选择包含 $a$ 的割，最终只要 3 个 LUT。

PRAETOR 的结果离有效面积下界只差 14%。

IMap：用迭代反馈修正扇出估计

有效面积公式里的 $|\mathrm{output}(u)|$ 用的是初始网络的扇出数，而真正该用的是最终映射解里的扇出数——后者映射完才知道。IMap 的解法是迭代：每轮映射后，用上一轮的真实扇出数修正估计值：

$$estimated\_fc(\nu )=\frac{{estimated\_fc}_{\text{prev}}(\nu )+\alpha \cdot |\mathrm{output}({\mathrm{LUT}}_{\nu })|}{1+\alpha }$$

白话解释：新估计 = 旧估计与上轮实际值的加权平均（$\alpha$ 取 1.5~2.5）。估计越准，面积打分越准，下一轮选割越聪明——类似”先按地图走一遍，再用实测路况修正地图”。

离最优还有多远？

LEKO/LEKU 实验给出了一面镜子：学术和商业映射器在已知最优解的例子上平均差 15%；在需要”逻辑优化+映射”联合解题的 LEKU 例子上更是差出 70 倍以上——说明这个领域的提升空间还很大。

DAOmap：保深度、砍面积

DAOmap 在保证最优延迟的同时大幅减面积，三招：增强的有效面积公式（对潜在复制加惩罚修正项 $P_{u_1},P_{u_2}$，鼓励”小割盖大锥”）、利用非关键路径上的富余 slack 换面积（只要延迟增加不超 slack 就选面积更小的割）、多轮迭代选割并基于输入共享调整代价。平均比以往延迟最优算法省 13% 面积，还因高效的割枚举比流计算算法快好几倍。

一体化映射：和上下游一起做

单独把每步做到最优，整体未必最优。三大联合方向：

分解 + 映射

分解成两输入网络的方式会影响映射深度，但两输入网络的深度并不能准确预测最终映射深度。**choice node（选择节点）**方案：把一个节点所有”功能等价但结构不同”的分解都编码进映射图（每对互补的选择节点叫一个 ugate），割枚举和打标都扩展到选择节点上（取各分支的并/最小值），映射时再从中挑出最好的分解。

逻辑综合 + 映射：无损综合（lossless synthesis）

更激进的思想：不做选择，攒着选项。逻辑优化的中间网络不丢弃，全部合并进一张 choice network（用 SAT + 仿真找功能等价点来压缩），映射时才统一拍板——时序关键段可以取自”为速度优化”的版本，非关键段取自”为面积优化”的版本，逐段混搭。基准测试上面积和时序同时改善 7%。

重定时 + 映射

**Retiming（重定时）**在不改变功能的前提下搬移触发器位置来提高时钟频率。看例子：每个门延迟 1，原设计时钟周期为 3，重定时后变成 1，触发器还从 4 个减到 3 个。

先映射再重定时？映射时优化的路径重定时后可能不再是关键路径——优化错了对象。先重定时再映射？重定时用的是没映射前的粗糙时序。所以必须联合。做法是把割扩展成”跨时间帧”的顺序割：割元素记作 $u^d$（门 u 加上到根之间经过的 d 个触发器），割生成的合并公式把 d 一路累加：

$$\Phi (\nu )=\{\{{\nu }^0\}\}\cup \{c_1^{d_1}\cup c_2^{d_2}\mid c_1\in \Phi (u_1),c_2\in \Phi (u_2),|c_1^{d_1}\cup c_2^{d_2}|\le K\}$$

顺序电路有环路，割集合互相依赖，用逐次逼近解决：从平凡割开始反复合并，直到不再出现新割（实测 K=4 时最多 5 轮就停）。标签公式也相应变成顺序到达时间：

$$l(c)=\max \{l(u)-d\cdot \varphi +1\mid u^d\in c\}$$

白话解释：信号若经过 $d$ 级触发器才到根，相当于”晚 $d\varphi$ 个时间出发”，所以到达时间要减掉 $d$ 倍目标周期 $\varphi$。若每个 PO 的标签都 ≤ $\varphi$，就证明存在”重定时+映射”联合意义下周期为 $\varphi$ 的解。这类算法能找到所有重定时与映射组合中最好的时钟周期，且多项式时间可解。

特殊架构的映射

异构资源：多种 LUT 尺寸

商业 FPGA 常支持多种 LUT 配置（如 Stratix II 的 ALM 可配成两个 4-LUT、一个 5-LUT+3-LUT 等）。设两种 LUT 尺寸 $K_1<K_2$、延迟 $d_1<d_2$，扩展思路很简单：枚举 $K_2$ 大小的割，时序公式里的 $D_c$ 按 $|c|\le K_1$ 与否取 $d_1$ 或 $d_2$。若有大 LUT 数量上限（资源受限），用二分法调大 $d_2$（虚拟涨价）迫使算法少用 $K_2$-LUT，再迭代收敛——把”带资源约束”化归为”无约束”问题。

把逻辑塞进片上存储器（EMB）

没用完的嵌入式存储块可以配置成大 ROM，相当于超大输入的 LUT（如 11 输入 1 输出）。一把能替掉一大串小 LUT 和它们的互连，但 EMB 内部访问延迟大，得挑对地方用。SMAP 算法一次映射一个 EMB：选种子节点 → 用流计算找 d-可行割圈出尽量大的锥 → 按 MFFC 大小打分选出 w 个输出。EMB Pack 则一次选出所有候选（把 MFFC 推广成多输出的 MFFS，转化为超图聚类问题）。两者都是 LUT 映射之后的后处理。

CPLD 映射

CPLD 逻辑单元是 p-term 块，用三元组 $(k,m,p)$ 刻画：k 输入、m 个乘积项、p 个输出。PLAmap 算法沿用”打标+映射”两段式，基于 Lawler 聚类：把节点与扇入锥中同标签的节点抱团，能塞进 $(k,m,1)$ 就保持标签，否则标签 +1。有个微妙的非单调性质：即使这个团塞不进一个单元，包含它的更大超团反而可能塞得进（共享输入省了 p-term）——所以打标只是启发式。p-term 块天然适合宽扇入低密度逻辑（如状态机），与 LUT 混合的混合架构可兼得两者长处。

常见坑/误区

用”局部 LUT 数最少”评估映射质量是经典误区。有效面积这种启发式在允许节点复制时会系统性低估真实面积（记住它是下界）；更隐蔽的是只优化单个节点而不考虑扇出共享——同一节点被不同扇出指定不同割时会悄悄产生复制，面积不降反升。靠谱的评估方式是对照 LEKO 这类已知最优解的基准。

通关标准：

学完本篇你应该理解：K-可行割为什么对应一个 K-LUT、割枚举的合并公式怎么自底向上工作；有效面积”成本平摊给扇出”的思想及其低估偏差；FlowMap 标签/深度打标的动态规划本质；choice node 与无损综合”攒选项、映射时拍板”的思想；重定时与映射联合时割为什么要带上 FF 计数 d。

自测：MFFC 是什么，为什么映射算法偏爱它？

最大无扇出锥：以某节点为根、锥内其他所有节点的扇出都留在锥内的最大扇入锥。整体替换成一个 LUT 时不会影响锥外逻辑，是”可以安全打包”的基本单位。

自测：有效面积为什么是真实面积的下界？

它把每个节点的成本平摊给所有扇出，隐含假设”处处共享、永不复制”。但实际映射中多扇出节点可能被复制（每个副本独自付成本），此时实际面积会高于平摊值。所以有效面积 ≤ 真实面积，只能作为下界参考。

自测：映射深度公式 $l(c)=\max \{l(u)+D_c\}$ 为什么取 max？

LUT 的输出要等它最慢的那个输入到达才能算完。信号到达时间沿路径累加，汇聚点的到达时间由最慢路径决定——这正是关键路径的定义，所以取所有割内输入标签的最大值。

自测：为什么"先映射后重定时"和"先重定时后映射"都不好？

前者：映射时以为的关键路径，重定时挪动触发器后可能根本不关键，映射优化了错误目标。后者：重定时只能基于未映射网络的粗糙时序信息，判断不准；而且两者都看不到重定时对割/LUT 生成的跨界影响。联合算法通过顺序到达时间和跨 FF 割一并解决。

自测：无损综合的核心思想一句话是什么？

逻辑优化过程中产生的每个中间网络都不丢弃，全部合并成一张带选择节点的 choice network，把”用哪个版本的逻辑”这个决定推迟到映射阶段——映射时逐段（关键段取速度版、非关键段取面积版）混搭挑选。