软硬协同优化 (1)：高层综合编译技术

1. 引言

随着摩尔定律逐渐失效，以增加晶体管数量换取性能提升的通用处理器发展模式已经显出颓势。为了在晶体管数量限制下获得更多算力，就必须跳出通用处理器的设计框架，提高单位晶体管的利用效率，这使得领域专用加速器（Domain-Specific Accelerator，DSA）成为一个热门研究方向，并在数字信号处理、视频编解码、AI训练/推理等特定领域大放异彩。

从算法及其实现方式的角度来看，通用处理器实现的是被编码为程序指令流的算法，而专用加速器实现的是被固化为硬件电路的算法。尽管抛弃通用性换来了性能和晶体管利用率的提升，但是专用加速器的电路设计过程却远不及通用处理器的程序设计过程便捷高效。按照传统的电路设计模式，即便是经验老道的硬件工程师也需要耗费可观的时间完成设计，大部分软件工程师更是无从下手。

那么，是否能够实现算法到硬件电路的自动转换，让只熟悉算法的工程师也能享受到领域专用加速器的红利呢？本文所介绍的高层综合（High-Level Synthesis，HLS）技术给出了答案。

2. 什么是HLS技术？

HLS技术是一种将高层次语言（如C、C++、SystemC等）描述的逻辑结构，自动转换成RTL语言（如Verilog、VHDL等）描述的电路模型的过程，其目的是让硬件设计人员在更高的抽象层次上工作，提高设计效率和验证效率，同时也让软件和算法工程师能够利用FPGA实现软件的硬件加速。

下图展示了使用HLS生成RTL代码的典型流程[1]。HLS的输入是用高级语言描述的算法逻辑结构，由于C语言贴近底层硬件的特性，目前绝大部分HLS实现都采用了类C语言作为高层描述语言，并使用pragma标记提供额外的编译指示。高层描述需要通过前端编译生成更接近硬件的中间表达（Intermediate Representation，IR），这一过程与通用编译器中的前端编译完全相同，因此通常都会复用成熟的编译器前端，例如LLVM、GCC。接下来资源分配步骤根据器件参数和用户参数确定后续流程需满足的时钟、面积、功耗等约束条件，并计算所需功能单元、存储单元、总线等硬件资源的类型和数量。然后进行时序调度，为IR中的每个运算操作分配具体的执行时钟周期。这些运算操作在资源绑定阶段会被分配给具体的功能单元执行，同时运算操作的输入输出变量也会被分配给具体的存储单元。经过上述步骤生成的调度和绑定信息最后被用于产生RTL代码，后续逻辑综合、仿真验证过程则回归传统硬件设计流程。

3. HLS中的编译技术

3.1 前端编译

前端编译对于了解通用编译器架构的读者来说并不陌生，HLS中的前端编译与通用编译器中的前端作用并无不同，都是将C语言等高级语言转化为更加形式化、更接近硬件的中间表达。转化的过程通常需要词法分析、语法分析、语义分析这3个步骤。以下面这段C语言编写的FIR滤波算法为例：

y[n] = 0;
for (i = 0; i < 8; i++) {
    y[n] += coeff[i] * x[n - i];
}

词法分析的作用是分析源代码中的字符序列，并将其转换为词素（Token）序列。Token是被赋予特定类型的字符串，上述代码中的部分Token和其对应的类型如下表所示：

词法分析可以生成Token序列，但不检查Token序列是否符合相应语言的语法约束。而检查诸如左右括号是否匹配等语法问题则需要语法分析完成。语法分析根据预先定义的语法，判断Token序列是否能够通过该语法生成，如果可以则产生对应的抽象语法树（Abstract Syntax Tree，AST）。例如语句y[n] += coeff[i] * x[n-i];对应的抽象语法树可以表示如下：

语义分析则进一步对抽象语法树进行类型检查和上下文相关的分析，例如检查变量是否在使用前进行了声明、每个表达式的类型是否正确、函数调用与函数定义是否一致。通过语义分析获得的信息会附加到抽象语法树上，构成带有标注信息的抽象语法树。

完成词法分析、语法分析并通过语义分析之后的抽象语法树就可以线性化为IR，这是一种不依赖具体的高层语言和硬件架构的表示方法，有利于后续分析和优化。以LLVM IR为例，示例中的C源码可以转化为如下的IR。IR由若干基本块组成（例如示例中的entry、bb1、return），基本块之间通过分支跳转关系构成控制流图（Control-Flow Graph, CFG），基本块内通过数据依赖关系构成数据流图（Data-Flow Graph）。在IR层面也可以进行一些对软硬件都适用的优化，例如死代码消除、公共子表达式合并等。

1:  entry: 
2:    %y.addr = getelementptr i32* %y, i32 %n 
3:    store i32 0, i32* %y.addr 
4:    br label %bb1 
5:  bb1: 
6:    %i = phi i32 [ 0, %entry ], [ %i.new, %bb1 ] 
7:    %coeff.addr = getelementptr [8 x i32]* %coeff, i32 0, i32 %i 
8:    %x.ind = sub i32 %n, %i 
9:    %x.addr = getelementptr i32* %x, i32 %x.ind 
10:   %0 = load i32* %y.addr 
11:   %1 = load i32* %coeff.addr 
12:   %2 = load i32* %x.addr 
13:   %3 = mul i32 %1, %2 
14:   %4 = add i32 %0, %3 
15:   store i32 %4, i32* %y.addr 
16:   %i.new = add i32 %i, 1 
17:   %exitcond = icmp eq i32 %i.new, 8 
18:   br i1 %exitcond, label %return, label %bb1 
19: return:
      ......

3.2 资源分配

从资源分配阶段开始，HLS编译与通用编译逐渐产生区别。这一阶段需要为后续的时序调度和资源绑定等优化问题设置约束条件，约束条件的来源通常有2类：

由目标硬件对应的数据库所指定的器件特性，例如FPGA开发板的器件类型、可用的功能单元类型和数量、功能单元的时延估计、存储器接口数量和访存时延等；
由用户在高层描述中提供的参数，例如电路的预期工作频率、循环展开次数、循环体的流水级数等。如果做一个类比，那么前者相当于通用编译器中的指令集架构，而后者相当于通用编译器中-O3、-Os等优化选项。

通过资源分配，IR中的每个运算操作都会被映射到一个功能单元，并被赋予相应的功能单元参数，如下图所示。资源分配后的运算操作拥有了时延和面积属性，于是后续的时序调度等优化过程可以结合这些属性计算最佳的电路结构。

另一方面，用户输入的参数也影响着资源分配过程。当用户希望优化电路面积时，HLS会尝试给多个同类型的运算操作分配同一个功能单元，通过硬件资源复用减少面积；当用户希望优化电路性能时，HLS会尝试分配更多的流水级间寄存器，通过缩短关键路径时延提升整体工作频率和性能。

最后，资源分配过程通常不是一次性完成的，在后续的时序调度和资源绑定过程中也会进行资源分配。

3.3 时序调度

时序调度是HLS编译过程的核心技术，其目的是为IR中的每一个运算操作赋予时间信息，即指定一个运算操作在哪个时钟周期执行[2]。时序调度必须保证所有运算操作的数据依赖关系正确，并且在满足资源约束的同时尽可能减小所有运算消耗的总时钟周期。

时序调度的实现可以分为2个层面。首先是CFG层面的粗粒度调度，如果将CFG中的每个基本块节点视为1个状态，将基本块之间的跳转条件视为状态转移条件，那么一个CFG就可以用一个有限状态机表示。将这些状态信息和状态转移条件提取出来转化成逻辑电路，就构成了一个控制器，从而控制电路在不同运行状态间切换，执行不同基本块中的运算。

通过有限状态机确定基本块间的时序关系后，就可以分别针对每个基本块进行DFG层面的细粒度调度，建立其内部指令的时序关系。如果与通用编译进行类比，那么细粒度时序调度可以看作特殊的指令调度。下图展示了不同约束条件下可能的时序调度结果。图(a)假设通过资源分配获得了1个双端口SRAM，因此每个时钟周期可以调度2次Load操作，完成所有运算需要4个时钟周期；图(b)假设通过资源资源分配获得了1个单端口SRAM，因此每个时钟周期只能调度1次Load操作，完成所有运算需要的时钟周期变为5个；当时序约束比较宽松时，2个前后依赖的操作可以被调度到同一个时钟周期内，这种优化叫做操作链合（Operation chaining），如图(c)所示。通过链合不仅可以减少完成计算所需的时钟周期数，还能减少跨时钟周期数据传递所需的寄存器数量。

在有限资源约束下，搜索最优时序调度是一个NP-Hard问题。对于局部最优的求解，列表调度是一类实用的启发式搜索方法。但在全局范围上，这些调度方法的效率不高，目前业界主要采用差分约束系统调度（SDC scheduling）解决这一问题，具体技术细节可参考相关文献[3]。

3.4 资源绑定

资源绑定的作用是将IR中的运算操作绑定到具体的功能单元，并将IR中的变量绑定到具体的寄存器[4]。除了确定绑定关系外，如何复用功能单元也是资源绑定需要解决的重要问题。考虑图(a)中的时序调度结果，若资源分配阶段获得了1个双端口SRAM和2个加法单元，对其进行资源绑定可以得到图(b)的电路。其中3次Load和1次Store被绑定到了双端口SRAM上，2次加法分别被绑定到了2个加法器上，第1次加法运算的中间结果被绑定到寄存器Reg上。而如果资源分配阶段仅获得1个双端口SRAM和1个加法器，则2次加法运算必须通过数据选择器复用1个加法器，得到图(c)中的电路。

实际实现中由于数据选择器的面积、时延、功耗不可忽略，为了降低功能单元复用的开销，在考虑复用时有以下3个目标：

位宽越大的数据选择器时延越高，因此需要避免在大位宽的功能单元上产生输入复用；
尽量使拥有相同输入数据的运算操作复用同一功能单元，减少输入数据选择器；
尽量使拥有不重叠生命周期的运算操作复用同一功能单元，减少输出数据选择器。

将上述因素量化就可以计算任意运算操作op与fu任意功能单元之间的绑定开销Cost（op，fu），为了实现最优的资源绑定，需要尽量缩小总的绑定开销。对于这个优化问题，可以用运算操作集合与功能单元集合构建如下的二分图，将绑定开销Cost（op，fu）作为边的权重。于是最优资源绑定问题就转化成了二分图的最小权匹配问题，可以使用Hungarian算法求解。

尽管资源绑定通常在时序调度之后进行，但其实际上并不依赖时序调度的结果。有时为了减少面积占用，绑定和调度也可以同时进行。

4. 总结

在领域专用加速器蓬勃发展的时代，HLS技术的出现降低了硬件设计的成本，拉近了软件与硬件的距离，在异构计算生态中扮演着重要的角色。站在编译的角度上，HLS中的编译技术与面向通用处理器的编译技术既有联系又有区别。联系在于HLS编译器可以复用通用编译器的前端和中间表达，并且使用与通用编译器中类似的调度算法。而区别在于HLS编译器面向的“后端”是没有特定指令集架构的硬件，所以需要编译器根据可用资源自行决定每个运算操作使用哪些硬件功能单元，因此具有更大的设计空间和优化难度。

由于作者水平有限，本文仅浅显地介绍了HLS编译技术的基本原理，而算法并行化、循环体流水、存储结构等更深入的优化问题并未涉及。希望本文的介绍可以让读者在了解HLS编译技术的同时，对“编译”这一概念产生新的理解。