An introductory walk-through of how High-Level Synthesis bridges the gap between behavioral C/C++ code and cycle-accurate RTL, covering CDFG, scheduling, resource allocation, and binding.
HLS (High-Level Synthesis, 高层次综合) 的目标是让人们能够用 C/C++ 这样的高级语言来描述硬件的行为, 然后由工具自动地把它翻译成可以在 FPGA 上运行的电路. 这中间跨越的鸿沟其实非常大: 一段 C 代码只是描述了"要算什么", 而一份硬件设计需要精确地描述"每一个时钟周期在做什么". 前者我们称之为行为级描述 (Behavioral Description), 后者我们称之为时序级描述 (Timed / Register-Transfer Level Description).
这篇文章不涉及任何具体的算法或优化技巧, 只是把 HLS 工具内部到底做了哪些事情, 从一段普通的 C 代码, 一步步变成一份带时序的 Verilog 的流程梳理清楚. 我们假设读者没有编译器相关的背景知识, 尽量把每一个概念都解释清楚. 后续文章中涉及到的调度算法, 流水线优化等, 都建立在这篇文章介绍的框架之上.
首先来看这两种描述到底差在哪里. 考虑一个非常简单的计算, 我们想算 z = a * b + c * d. 用 C 语言写出来就是一行:
int z = a * b + c * d;这就是一段典型的行为级描述. 它告诉我们的信息只有: z 的值等于两个乘积之和. 它没有说这两个乘法是同时做还是分开做, 没有说用几个乘法器, 没有说加法在第几个时钟周期发生, 也没有说这中间需不需要寄存器来暂存中间结果. 这些是硬件才需要关心的细节, 但 C 语言把它们统统隐藏掉了.
现在看看同样一件事情, 用时序级描述 (这里用 Verilog) 大概会长成什么样子. 假设我们只有一个乘法器可用, 那这个计算就没法一步做完, 需要分成好几个时钟周期:
// assume we have only one multiplier
always @(posedge clk) begin
case (state)
S0: begin t1 <= a * b; state <= S1; end // cycle 1: mul 1
S1: begin t2 <= c * d; state <= S2; end // cycle 2: mul 2
S2: begin z <= t1 + t2; state <= S0; end // cycle 3: add
endcase
end显然时序级描述里面出现了一些 C 代码里不存在的东西:
always @(posedge clk) 表示这段逻辑在每个时钟上升沿触发一次, 时间被离散化成了一个个时钟周期.t1, t2 用来存放中间结果, 因为一个乘法算完到下一个乘法开始之间隔了一个周期, 结果必须被存起来.state 变量记录了"现在进行到第几步了", 它决定了每个周期具体该做哪个操作.可以看到, 从行为级到时序级, 本质上就是把一段"没有时间概念"的计算, 强行安排进一个个具体的时钟周期里, 并且明确每个周期用哪些硬件、把结果存到哪里. 这个映射过程就是 HLS 工具的核心工作.
大概总结一下行为级和时序级之间缺失的信息如下, 或者说是 HLS 工具需要推断出来的东西:
HLS 工具的整个流程就是围绕怎么系统性地填平这几个 gap 而设计的. 它可以拆成下面几个阶段:
前端编译这一步和普通的 C 编译器 (比如 GCC/Clang) 做的事情差不多, 就是把源代码解析成一种统一的、便于分析的中间表示 (Intermediate Representation, IR). 这个过程里会把复杂的表达式拆解成一个个不可再分的原子操作 (Atomic Operation). 例如 z = a * b + c * d 会被拆成:
t1 = a * b // atomic op 1: mul
t2 = c * d // atomic op 2: mul
z = t1 + t2 // atomic op 3: add这一步对 HLS 来说没有太多特殊之处, 真正 HLS 特有, 也是最关键的工作是后面的 CDFG 构建、调度、分配和绑定. 下面我们逐个来看.
前端把代码拆成了一堆原子操作之后, 面临的第一个问题是: 这些操作之间是什么关系? 哪些必须按顺序来, 哪些可以并行? 遇到 if 分支和 for 循环又该怎么表示? 为了回答这些问题, HLS 工具会把程序组织成一种图结构, 叫做 CDFG (Control Data Flow Graph, 控制数据流图).
使用图结构的原因是图能把操作之间的依赖关系显式地表达出来. 代码是一维的、线性的, 一行接一行, 但操作之间的真实依赖关系其实是网状的. 只有把这个网状结构画出来, 工具才能分析出来哪里可以并行、哪里必须串行.
CDFG 由两部分组成, 分别捕捉程序的两个不同侧面:
在硬件里, 这两个侧面恰好对应到两块物理结构: 控制通路 (Control Path) 和 数据通路 (Data Path). 数据通路是真正干活的部分 (乘法器、加法器、寄存器等等), 而控制通路负责指挥数据通路, 告诉它每个周期该做什么. 而控制通路的核心是一个有限状态机.
有限状态机 (Finite State Machine, FSM) 是时序硬件最基本的模型, 也是理解"时序级描述"的关键. 我们回过头看看前面那段 Verilog, 里面那个 state 变量在 S0 -> S1 -> S2 -> S0 之间循环跳转, 这就是一个最简单的 FSM.
一个 FSM 由三样东西构成:
a*b"、"这个周期把结果写进寄存器 t1"、"选择 mux 的第 0 路输入"等等.前面 z = a*b + c*d 那个例子, 它的 FSM 画出来就是这样一条简单的链:
FSM 之所以重要, 是因为它就是"时间"这个概念在硬件里的落脚点. 行为级描述里没有时间, 而 HLS 一旦决定了每个操作放在哪个周期 (也就是调度), 这些周期就自然变成了 FSM 的一个个状态. 换句话说, 调度的结果最终会以 FSM 的形式呈现在生成的 RTL 里. 数据通路只是被动地摆在那里的一堆运算单元, 是 FSM 每个周期发出的控制信号, 让整个电路"活"起来、按正确的时序运转.
后面讲到控制通路和数据通路的时候, 我们会看到 CFG 是如何映射成这个 FSM 的, 以及 FSM 又是如何驱动数据通路的.
控制流图 (Control Flow Graph, CFG) 描述的是程序的执行路径. 它的基本单位是基本块 (Basic Block). 一个基本块指的是一段"一进一出"的连续代码: 从第一条语句进入, 中间没有任何跳转, 一直顺序执行到最后一条语句, 然后才可能跳转到别处. 换句话说, 只要进了一个基本块, 里面的所有语句就一定会全部执行, 不存在中途跳走的可能.
基本块之间用有向边连接, 边表示可能的控制转移. 分支 (if) 会让一个基本块指向两个不同的后继, 循环 (for/while) 则会产生一条指回前面的边. 我们看一个带循环的例子:
sum = 0;
for (int i = 0; i < N; i++) {
sum += a[i];
}
return sum;它的 CFG 大概长这样:
这里有 4 个基本块. BB1 是循环的判断, 它有两个后继: 条件成立就进循环体 BB2, 不成立就跳到出口 BB3. BB2 执行完之后又跳回 BB1, 形成了循环. 这条指回去的边 (BB2 -> BB1) 就是循环的本质.
CFG 到硬件的映射, 就是前面说的控制通路. 具体来说, HLS 会为整个 CFG 生成一个 FSM, 让这个 FSM 按照 CFG 描述的路径在各个基本块之间"走"。上面这个循环, 它对应的控制器 FSM 大致是:
注意到 FSM 的结构和 CFG 几乎是一一对应的. 分支条件 i < N 从代码里的一个比较运算, 变成了 FSM 的一个状态转移条件. 硬件里会有一个比较器实时计算 i < N, 它的输出直接接到 FSM 上, 决定下一个周期是进循环体还是退出. 这就是控制通路干的活: 它不负责算真正的结果, 只负责根据各种条件信号, 决定整个电路每个周期该往哪走.
数据流图 (Data Flow Graph, DFG) 关心的就是一个基本块内部, 那些原子操作之间的数据依赖. DFG 是一个有向无环图 (DAG): 节点是原子操作 (或者数据), 边表示数据依赖, 即某个操作的输出是另一个操作的输入.
还是拿 z = a * b + c * d 举例, 它是一个基本块内部的计算, 对应的 DFG 是:
这张图一眼就能看出关键信息: 两个乘法 M1 和 M2 之间没有任何边相连, 说明它们互不依赖, 完全可以并行执行; 而加法 ADD 依赖两个乘法的结果, 所以它必须等两个乘法都算完之后才能开始. 这种"谁依赖谁"的信息, 在原始的一维代码里是隐含的, 只有画成 DFG 才变得一目了然. 挖掘并行性 (前面提到的第 4 个 gap) 靠的就是分析这张图.
DFG 到硬件的映射就是数据通路. 数据通路是真正做计算的部分, 由三类东西组成:
DFG 只告诉我们操作之间的依赖关系, 但它没有回答两个问题: 这两个互不依赖的乘法, 到底是同时做 (用两个乘法器) 还是分开做 (共用一个乘法器)? 每个操作具体在哪个周期发生? 回答这些问题, 就要靠接下来的调度、分配和绑定了. 换句话说, DFG + CFG 提供的是"约束", 而后面几步是在这些约束下做"决策".
有了 CDFG, HLS 就掌握了所有操作以及它们之间的依赖关系. 接下来最核心的一步就是调度 (Scheduling): 为每一个原子操作确定它执行的具体时钟周期 (也就是分配到哪个控制步). 前面反复提到的第一个 gap——"没有时间", 就是在这一步被填平的.
调度需要同时兼顾几方面的约束:
我们用 z = a*b + c*d 感受一下资源约束是怎么影响调度的. 假设一个乘法、一个加法各占一个周期.
情况一: 只分配 1 个乘法器, 1 个加法器. 两个乘法只能一前一后:
| 周期 | 操作 |
|---|---|
| 1 | t1 = a * b |
| 2 | t2 = c * d |
| 3 | z = t1 + t2 |
总共需要 3 个周期. 这正是文章开头那段 Verilog 对应的调度.
情况二: 分配 2 个乘法器, 1 个加法器. 两个乘法可以并行:
| 周期 | 操作 |
|---|---|
| 1 | t1 = a * b (乘法器 1), t2 = c * d (乘法器 2) |
| 2 | z = t1 + t2 |
只需要 2 个周期. 用更多的硬件, 换来了更短的延迟——这是硬件设计里最典型的面积换性能的权衡, 也直接引出了下一步"资源分配"要解决的问题.
调度是整个 HLS 里学问最深的一步, 直接决定了最终设计的 PPA (Performance, Power, Area). 上面演示的只是最朴素的按依赖顺序排的思路, 实际的调度算法 (ASAP、ALAP、列表调度、力导向调度、SDC 调度等) 要复杂得多, 我们在 FPGA HLS: Scheduling Algorithms 里做了专门的介绍. 而针对循环这种特殊结构的流水线调度, 则在 FPGA HLS: Pipelining 里讨论. 这篇文章里我们只需要知道: 调度的产物, 就是每个操作被钉在了某个具体的周期上, 而这些周期最终会变成前面讲的那个 FSM 的一个个状态.
上一节的两种情况其实已经点出了资源分配 (Resource Allocation) 要做的事: 决定每种运算单元 (以及存储、端口等) 各实例化多少个. 这是在填平第二个 gap——"资源无限". 分配得多, 能支持更高的并行度, 调度出来的周期数更少, 但占用的芯片面积也更大; 分配得少则相反.
这里有一个"先有鸡还是先有蛋"的问题: 你要知道分配多少个乘法器, 得先知道调度长什么样 (同一周期最多几个乘法并行); 可你要做调度, 又得先知道有多少个乘法器可用 (资源约束). 调度和分配是相互纠缠的, 谁也离不开谁.
实际工具处理这个矛盾的方式通常是迭代式的, 或者由用户通过约束来引导. 比如用户设定一个目标: "我希望这个设计的延迟不超过 100 个周期", 工具就在满足这个延迟约束的前提下, 尽量少分配资源 (省面积); 反过来, 用户也可以说"我最多只能用 8 个 DSP", 工具就在这个资源上限下尽量把延迟做低. 这两种方向, 分别对应了不同类型的调度算法所擅长解决的问题.
分配的粒度也不只是"几个乘法器"这么简单. 比如一块 BRAM 通常只有两个读写端口, 如果某个循环体一个周期内要访问同一块 BRAM 四次, 那端口就不够用, 必须把数据拆到多块 BRAM 里 (也就是分配更多的存储端口资源). 这类因为端口/资源不足导致无法进一步并行的情况, 在流水线优化里非常常见, 具体可以参考 FPGA HLS: Pipelining 里关于资源冲突的讨论.
调度决定了"每个操作在哪个周期", 分配决定了"每种单元有几个", 最后还剩一个问题: 具体哪个操作用哪个物理单元? 这就是资源绑定 (Resource Binding).
绑定之所以有意义, 是因为互不重叠的操作可以共享同一个物理单元. 回到情况一的调度: t1 = a*b 在周期 1, t2 = c*d 在周期 2, 这两个乘法发生在不同的周期, 永远不会撞车, 所以完全可以用同一个乘法器分时完成. 这样一来, 虽然代码里有两个乘法, 硬件上却只需要一个乘法器, 面积直接省了一半. 这就是资源共享 (Resource Sharing).
不过共享不是白来的. 一旦一个乘法器要服务多个操作, 就得有办法在不同周期给它喂不同的输入, 这就需要在它的输入端插入 mux. 情况一共享一个乘法器的数据通路大致是这样:
周期 1 的时候, FSM 让两个 mux 都选左边一路 (a 和 b), 乘法器算 a*b; 周期 2 的时候, FSM 让 mux 切到右边 (c 和 d), 算 c*d. 可以看到, 绑定产生的 mux 又反过来需要 FSM 来控制——数据通路和控制通路就是这样咬合在一起工作的.
这里有个微妙的权衡: 共享省下了一个乘法器, 但代价是多了两个 mux 和相应的控制逻辑. 在 FPGA 上, mux 是用 LUT 搭出来的, 如果被共享的单元本身很小 (比如一个几位的加法器), 那省下的面积可能还不如 mux 和布线带来的开销大, 这种情况下强行共享反而得不偿失. 所以绑定并不是"能共享就共享", 而是一个需要权衡的优化问题.
除了运算单元, 绑定同样适用于寄存器. 一个中间变量只在它"诞生"到"最后一次被使用"这段周期区间内 (称为它的生命周期, Lifetime) 才需要占用寄存器, 过了这段时间, 这个寄存器就能腾出来给别的变量用. 两个生命周期不重叠的变量就可以共用同一个寄存器. 判断哪些操作/变量可以共享, 本质上是一个图着色 (Graph Coloring) 或者区间调度的问题——把有冲突 (时间上重叠) 的对象连边, 然后用尽量少的颜色 (物理单元) 去染色. 这一步对硬件设计的读者来说, 和软件编译器里的寄存器分配 (Register Allocation) 其实是同一类问题.
走完调度、分配、绑定这三步, HLS 手里就攒齐了生成时序级 RTL 所需要的全部信息. 我们把前面 z = a*b + c*d (情况一, 单乘法器共享) 的完整结果, 用一段 Verilog 写出来, 就可以看到前面每个概念都对应到了代码的哪个部分:
module mac (
input wire clk,
input wire start,
input wire [15:0] a, b, c, d,
output reg [31:0] z,
output reg done
);
// ---- 控制通路: FSM (来自调度) ----
localparam S_IDLE = 2'd0, S_MUL1 = 2'd1, S_MUL2 = 2'd2, S_ADD = 2'd3;
reg [1:0] state;
// ---- 数据通路: 寄存器 (来自寄存器绑定) ----
reg [31:0] t1, t2;
// ---- 数据通路: 共享的乘法器 + 输入 mux (来自资源分配 + 绑定) ----
wire [15:0] mul_x = (state == S_MUL1) ? a : c; // mux, 由 FSM 状态选择
wire [15:0] mul_y = (state == S_MUL1) ? b : d; // mux
wire [31:0] mul_r = mul_x * mul_y; // 唯一的一个乘法器
always @(posedge clk) begin
done <= 1'b0;
case (state) // FSM 状态转移 = 调度出的各个周期
S_IDLE: if (start) state <= S_MUL1;
S_MUL1: begin t1 <= mul_r; state <= S_MUL2; end // 周期 1: a*b
S_MUL2: begin t2 <= mul_r; state <= S_ADD; end // 周期 2: c*d
S_ADD: begin z <= t1 + t2; done <= 1'b1; state <= S_IDLE; end // 周期 3: 加
endcase
end
endmodule对照着看, 每一样东西的出处就很清楚了:
state 这个 FSM 以及它的四个状态, 来自调度——调度把三个操作排进了三个周期, 这三个周期就成了 FSM 的状态.mul_r 乘法器, 来自资源分配——我们决定只实例化一个乘法器.mul_x/mul_y 那两个三元表达式 (就是 mux), 以及它们由 state 来选择, 来自资源绑定——两个乘法共享一个乘法器, 于是需要 mux 分时切换输入, 而切换的时机由 FSM 控制.t1/t2 这两个寄存器, 来自数据依赖分析和寄存器绑定——中间结果必须跨周期保存.这份 Verilog 就是一份彻头彻尾的时序级描述了: 有时钟、有寄存器、有明确的每周期行为, 可以直接拿去综合、布局布线, 变成 FPGA 上真实的电路. 我们从一行没有任何时间概念的 C 代码出发, 经过 CDFG、调度、分配、绑定, 最终得到了它.
回过头看整条路径, HLS 做的事情可以概括成一句话: 把行为级描述中缺失的时间、资源、存储、并行性等信息, 通过一系列自动化的决策逐步补齐, 最终落实成一份由数据通路和 FSM 控制器组成的时序级 RTL.
这几步在真实工具里并不是严格的流水线, 而是相互影响、反复迭代的 (尤其调度和分配几乎无法完全分开). 后续文章里介绍的各种调度算法、流水线技术、内存优化, 都可以放回到这个框架里来看它们究竟在优化哪一个环节.