一种芯片设计语言 Spatial的简介 (基于scala的方言)

Spatial：一种面向应用加速器的语言与编译器

大卫・科普林格（David Koeplinger）、马修・费尔德曼（Matthew Feldman）、拉古・普拉巴卡尔（Raghu Prabhakar）、张亚奇（Yaqi Zhang）、斯特凡・哈迪斯（Stefan Hadjis）、鲁本・菲塞尔（Ruben Fiszel）、赵天（Tian Zhao）、路易吉・纳尔迪（Luigi Nardi）、阿尔达万・佩德拉姆（Ardavan Pedram）、克里斯托斯・科济拉基斯（Christos Kozyrakis）、昆勒・奥卢科通（Kunle Olukotun）

斯坦福大学（美国）、瑞士联邦理工学院洛桑分校（EPFL，瑞士）

摘要

工业界正越来越多地采用现场可编程门阵列（FPGA）和粗粒度可重构架构（CGRA）等可重构架构，以提升性能和能效。然而，这些架构的应用普及受到了其编程模型的限制：硬件描述语言（HDL）缺乏提升开发效率的抽象机制，且难以适配高层级语言；高级综合（HLS）工具虽能提高开发效率，但采用软件与硬件抽象混合的临时方案，使得性能优化难度较大。

本文提出一种名为 Spatial 的新型领域特定语言（DSL）与编译器，用于对应用加速器进行高层级描述。文中阐述了 Spatial 中以硬件为核心的抽象机制 —— 该机制既有助于提升程序员开发效率，又能保障设计性能；同时总结了支持这些抽象机制所需的编译器过程，包括流水线调度、自动内存分块以及由主动机器学习驱动的自动设计调优。实验表明，通过通用源代码，Spatial 语言能够适配 FPGA 和 CGRA 架构。在亚马逊 EC2 F1 实例的赛灵思（Xilinx）UltraScale+ VU9P FPGA 上进行测试，结果显示：与 SDAccel HLS 工具相比，用 Spatial 编写的应用代码长度平均缩短 42%，且平均速度提升 2.9 倍。

关键词

领域特定语言、编译器、硬件加速器、高级综合、可重构架构、现场可编程门阵列（FPGA）、粗粒度可重构架构（CGRA）

1 引言

技术缩放的最新趋势、海量数据的可用性以及算法领域的突破性进展，推动了加速器架构研究的发展。现场可编程门阵列（FPGA）和粗粒度可重构架构（CGRA）等可重构架构，凭借其相较于传统 CPU 在性能和能效方面的潜在优势，重新受到学术界研究者和工业界从业者的关注。目前，FPGA 已被微软（Microsoft）和百度（Baidu）用于数据中心的网页搜索加速 [29, 34]；亚马逊（Amazon）在 AWS 服务中提供 FPGA 实例 [4]；英特尔（Intel）也发布了封装内至强 - FPGA 系统 [18] 和 FPGA 加速存储系统 [21] 等产品。此外，近期多项研究原型 [17, 30-32, 40] 和初创企业 [6, 7] 也在探索不同粒度的 CGRA 架构。可重构架构的应用日益广泛，使得程序员比以往更容易接触到这类技术。

可重构设备之所以能实现应用加速，部分原因在于其通过自定义数据流水线和内存层级结构，充分利用了多级嵌套并行性和数据局部性。然而，正是这些让可重构架构具备高效性的特性，使其编程难度大幅增加。加速器设计不仅要考虑流水线信号的时序，以及目标设备上物理资源有限的计算和存储单元，还需合理划分本地高速缓存与片外内存间的数据，以实现良好的数据局部性。这些复杂问题交织在一起，导致加速器设计空间的探索变得极具挑战性 [13]。

上述挑战使得可编程性成为 CGRA 和 FPGA 广泛应用的关键限制因素 [10, 15]。CGRA 的编程模型呈现碎片化特征，不同架构的编程模型互不兼容；而当前 FPGA 编程的主流方式，是结合厂商提供的知识产权（IP）模块、通过低层级寄存器传输级（RTL）或高级综合工具编写的手工调优硬件模块，以及与动态随机存取存储器（DRAM）等片外组件通信的架构专用粘合逻辑。Verilog 和 VHDL 等硬件描述语言（HDL）专为硬件的显式描述设计，要求用户自行解决将算法转化为硬件实现过程中的各类复杂问题。

与 HDL 相比，SDAccel [42]、Vivado HLS [3] 和英特尔 OpenCL SDK [5] 等高级综合（HLS）工具显著提升了抽象层级。例如，HLS 工具允许程序员基于无时间约束的嵌套循环编写加速器设计，并提供 CPU 主机与 FPGA 间数据传输等通用操作的库函数。但现有商用 HLS 工具均基于 C、OpenCL 和 Matlab 等软件语言开发，而这些软件语言的设计初衷是适配 CPU 和 GPU 等基于指令的处理器。因此，尽管现有 HLS 工具提升了可重构架构编程的抽象层级，但其采用的是软件与硬件抽象混合的临时方案，且通常缺乏明确规范。以 SDAccel 为例，它虽能将嵌套循环转化为硬件状态机，但该语言无法识别架构的内存层级结构，也不能对任意嵌套层级的循环进行流水线处理 [2]。这就要求程序员在使用软件编程抽象的同时，必须采用硬件而非软件的优化技术，导致编写能生成完全优化设计的 HLS 代码难度极大 [26]。

本文首先总结了从头构建新型高级综合语言所需的高层级语言抽象机制，包括可重构架构中内存、控制和加速器 - 主机接口管理的语法规则。研究表明，这种 “从零开始” 的高级综合语言设计方法，能使语言在适配可重构架构（尤其是针对数据局部性和并行性优化）时语义更清晰。这些抽象机制不仅有助于提升程序员的开发效率，还能让用户和编译器更轻松地优化设计以提升性能。

随后，本文介绍了一种名为 Spatial 的新型领域特定语言（DSL）与编译器框架。该框架通过实现上述抽象机制，支持更高层级、面向性能的硬件加速器设计。图 1 展示了用 Spatial 实现矩阵乘法的基础示例。如图所示，Spatial 代码与现有 HLS 语言类似，均采用无时间约束的编程方式，且鼓励以嵌套循环的形式描述加速器设计。但与现有 HLS 工具不同的是，Spatial 通过片上和片外内存模板库（如图 1 中的 DRAM 和 SRAM），为用户提供了对内存层级结构更明确的控制。默认情况下，Spatial 会自动对任意嵌套循环进行流水线处理，并根据并行访问模式对内存进行分块、缓冲和复制操作；而现代 HLS 工具大多需要用户在代码中添加显式编译指示（pragma）才能实现这些优化。此外，Spatial 还支持通过自动设计空间探索（DSE）对参数化设计进行调优。与以往采用易受方差影响的启发式随机搜索的方法 [22] 不同，Spatial 采用名为 HyperMapper [11] 的主动机器学习框架驱动探索过程，使得单个加速器设计能轻松快速地适配不同目标架构和厂商的设备。

在适配 FPGA 时，Spatial 会生成经过优化的可综合 Chisel 代码，以及可在主机 CPU 上运行的 C++ 代码 —— 后者用于初始化和执行目标 FPGA 上的加速器。目前，Spatial 支持亚马逊 EC2 F1 实例上的赛灵思 UltraScale+ VU9P FPGA、赛灵思 Zynq-7000 和 UltraScale+ ZCU102 片上系统（SoC），以及阿尔特拉（Altera）DE1 和 Arria 10 SoC。Spatial 中的结构对可重构架构具有通用性，这意味着 Spatial 程序也可适配 CGRA 架构。本文通过适配近期提出的 Plasticine CGRA [32]，验证了这一特性。

本文的贡献如下：

1. 探讨了为可重构架构描述与目标无关的加速器设计所需的抽象机制（第 2 节），随后阐述了 Spatial 对这些结构的实现（第 3 节），以及这些抽象机制在 Spatial 编译器中支持的优化（第 4 节）；
2. 提出一种基于 HyperMapper 的快速自动设计参数空间探索方法（第 4.6 节），并在第 5 节对该方法进行评估；
3. 评估了 Spatial 高效描述各类应用以及通过同一源代码适配多种架构的能力，验证了 Spatial 对两种 FPGA 和 Plasticine CGRA 的适配效果；
4. 在 VU9P FPGA 上，通过多种基准测试对 Spatial 与 SDAccel 进行定量对比（第 5 节），结果显示 Spatial 的几何平均速度提升 2.9 倍，且代码长度减少 42%；在第 6 节对 Spatial 与其他相关研究进行定性对比。

2 语言设计标准

对于旨在简化硬件设计抽象的语言而言，关键在于在提升开发效率的高层级结构与用于性能调优的低层级语法之间找到平衡。本节通过明确实现开发效率与性能平衡所需的要求，为 Spatial 语言的设计提供依据。

2.1 控制

对于大多数应用，控制流可通过抽象形式表达。数据依赖分支（如 if 语句）和嵌套循环几乎存在于所有应用中，且在常见场景下，这些循环的启动间隔（initiation interval）可静态计算。这些循环对应层级化流水线，编译器在多数情况下可对其进行自动优化。因此，控制结构的定义应由编译器负责，仅当编译器缺乏优化循环调度所需信息时，才需用户干预。

2.2 内存层级结构

在大多数可重构架构中，内存层级结构至少包含三个层级：片外内存（DRAM）、片上高速缓存（如 FPGA 的 “块 RAM”）和寄存器。与 CPU 将内存呈现为统一可访问地址空间不同，可重构架构要求程序员显式管理内存层级结构。Sequoia [16] 等早期语言已证实，在编程语言设计中明确内存层级结构概念具有显著优势。此外，循环展开和流水线处理对性能和面积利用率至关重要，而这些优化需要对片上内存进行分块、缓冲和复制，以满足并发访问所需的带宽。这些决策需通过静态分析内存访问模式与循环迭代器的关系来确定。因此，加速器设计语言应向用户呈现目标内存层级结构，并引入循环迭代器概念，以支持针对片上带宽的自动内存分块、缓冲和复制优化。

除片上内存管理外，加速器设计还需显式管理片外与片上内存间的数据传输，这需要构建用于管理片外内存的软内存控制器。不同目标架构和厂商的内存控制器实现差异较大，但所有架构都需要根据访问模式优化内存控制器：与可预测的线性访问相比，不可预测的数据依赖请求需要更专用的内存控制器逻辑。因此，语言不应聚焦于目标专用细节，而应允许用户基于访问模式优化每次数据传输，在尽可能抽象化这些传输过程的同时，提供根据访问模式进行专用化处理的结构。

2.3 主机接口

可重构架构通常用作卸载式应用加速器。在这种执行模式下，主机负责内存分配、数据结构准备，以及与大型异构网络交互以接收和发送数据。数据准备完成后，主机调用加速器，可选择等待加速器完成（“阻塞式” 执行），或通过轮询或中断方式与持续运行的加速器交互（“非阻塞式” 执行）。尽管通信和加速器执行管理已得到广泛支持，但不同平台和厂商的相关库与函数调用差异极大，导致代码难以移植和对比。对于与 CPU 主机的通信，加速器设计的高层级语言应提供能最大程度抽象化目标架构的结构。

2.4 设计空间探索

与所有硬件设计一样，加速器的设计空间可能极为庞大，探索过程繁琐。虽然循环流水线和内存分块等自动化优化有助于提升开发效率，但这些转换会使编译器在资源分配方面面临众多选择。这些决策与应用复杂度相结合，会形成庞大的性能 / 面积权衡空间。以通用矩阵乘法的固定实现为例，其设计空间包含片上存储矩阵部分数据的块大小、块迭代循环的并行化决策，以及块内迭代循环的并行化决策等多个维度。图 1 中第 17-21 行所示的参数，仅揭示了众多设计空间参数中的一小部分。已有研究 [22] 表明，让编译器识别流水线深度、展开因子和块大小等设计参数，有助于加快并自动化参数空间探索。因此，硬件抽象语言应同时在语言和编译器层面支持设计空间参数。

3 Spatial 语言

Spatial 是一种面向可重构空间架构（包括 FPGA 和 CGRA）加速器设计的领域特定语言。该语言旨在简化加速器设计流程，使领域专家能够快速开发、测试、优化和部署硬件加速器 —— 既可以直接实现高层级硬件设计，也可以通过其他高层级语言适配 Spatial。

本节将阐述 Spatial 中用于平衡开发效率与性能细节的抽象机制。由于篇幅限制，无法完整阐述语言规范，表 1 列出了 Spatial 核心语法子集的概述。

3.1 控制结构

Spatial 提供多种控制结构，帮助用户更简洁地表达程序，同时便于编译器识别并行化机会。这些结构可无限制地任意嵌套，方便用户定义层级化流水线和嵌套并行性。表 1a 列出了该语言中的部分控制结构。除 Foreach 循环和状态机外，Spatial 还借鉴并行模式 [35, 39] 的思想，为归约（reduction）操作提供简洁的函数式语法。虽然归约可用纯命令式方式表达，但 Reduce 结构能告知编译器归约函数具有结合性；类似地，通过 MemReduce 对一系列内存进行归约，相比命令式实现可挖掘更多并行性。例如，在图 1 中，第 45 行的 MemReduce 允许编译器根据参数 PAR_K 进行并行化处理，从而实现多个 tileC 块的并行填充，随后通过归约树将其合并到累加器 accum 中。

通过为 Foreach、Reduce 和 MemReduce 的相应计数器设置并行化因子，可实现这些结构的并行化。当请求循环并行化时，编译器会分析循环并行化是否能保证与顺序执行等效的行为；若分析失败，编译器会报错。Spatial 保证并行化的循环体在开始下一轮并行迭代前完全执行完毕，但不保证单轮展开迭代中各操作的相对时序。

Spatial 控制结构的循环体无时间约束，编译器会自动调度操作，并保证功能行为不变。编译器选择的调度方式可分为流水线执行、顺序执行或流式执行：

• 流水线执行：循环迭代的执行过程重叠。对于最内层循环，重叠程度取决于控制器的平均启动间隔；对于外层循环，重叠程度由控制器的 “深度” 决定（深度定义为在消费阶段开始执行前，外层循环迭代允许执行的最大次数）；
• 顺序执行：在开始下一轮循环迭代前，完全执行完当前轮循环体。顺序调度等效于启动间隔等于循环体延迟的流水线调度，或深度为 1 的外层控制器调度；
• 流式执行：通过允许内层控制器在输入可用时异步运行，进一步实现阶段重叠。仅当控制器间通过流式接口或队列通信时，流式调度才是定义明确的控制方案。

3.2 内存

Spatial 提供多种内存模板，支持用户以抽象但明确的方式控制加速器异构内存中的数据分配。Spatial 编译器可识别所有这些内存类型，并对其进行自动优化。

Spatial 中的 “片上” 内存表示创建静态大小的逻辑内存空间，支持的内存类型包括只读查找表（LUT）、高速缓存（SRAM）、行缓冲（LineBuffer）、固定大小队列和栈（FIFO 和 LIFO）、寄存器（Reg）以及寄存器文件（RegFile）。这些内存均使用加速器上的资源分配，默认情况下主机无法访问。尽管编译器保证每种内存对程序员而言具有一致性，但对实现每种内存所用的资源数量和类型不做限制。除具有显式初始值的 LUT 和 Reg 外，内存分配时其内容未定义。这些规则使 Spatial 编译器能在整个应用范围内，最大限度地优化内存访问延迟和资源利用率。根据访问模式，编译器可在保证最终逻辑内存行为不变的前提下，自动对内存进行复制、分块或缓冲处理。

“共享” 内存由主机 CPU 分配，且主机和加速器均可访问。这类内存通常在卸载模式下用于主机与加速器间的数据传输。DRAM 模板代表内存层级中速度最慢、容量最大的层级。为帮助用户优化内存控制器，DRAM 的读写需通过与片上内存的显式传输实现，且这些传输会根据可预测访问（加载和存储）和数据依赖访问（散列和聚集）的模式进行专用化处理。

3.3 接口

Spatial 提供多种专用接口，用于加速器与主机及其他外部设备的通信。与内存模板类似，Spatial 可对这些接口上的操作进行优化。

ArgIn、ArgOut 和 HostIO 是在 CPU 主机上具有内存映射的专用寄存器：ArgIn 仅允许主机在设备初始化期间写入；ArgOut 仅允许主机读取，不允许写入；HostIO 允许主机在加速器执行期间随时读写。此外，在 Accel 作用域内使用的标量（包括 DRAM 大小）会隐式创建 ArgIn 实例。例如，在图 1 中，矩阵 A、B 和 C 的维度通过隐式 ArgIn 传递给加速器，因为这些维度用于生成循环边界（如 A.rows、B.cols）。

Spatial 中的 StreamIn 和 StreamOut 用于创建与外部接口的连接。通过指定目标设备上的输入 / 输出引脚总线，可创建流接口；采用面向对象方式实现与外部外设的连接，所有支持的 Spatial 目标设备均定义一组常用外部总线，可用于分配 StreamIn 或 StreamOut。

Spatial 允许用户在同一程序中编写主机和加速器代码，以便于两者通信。该语言的数据结构和操作分为 “可加速” 和 “主机” 两类：仅可加速操作具有在空间架构上的明确映射。Spatial 通过这种区分，帮助用户以最适合可重构架构的方式构建算法。例如，严重依赖动态内存分配的程序通常在可重构架构上性能不佳，但通过算法层面的转换，往往可显著提升性能。

Spatial 程序通过 Accel 作用域明确划分主机与加速器的任务。如表 1e 所示，Accel 调用可指定为阻塞式或非阻塞式。图 1 展示了阻塞式调用的示例：在加速器中计算两个矩阵的乘积，完成后再将结果传递给主机。该作用域内调用的所有操作均分配给目标硬件加速器，而作用域外的所有操作均分配给主机。因此，Accel 作用域内的所有操作必须是可加速的。

主机操作包括分配主机与加速器间的共享内存、在主机与加速器间传输数据，以及访问主机文件系统。通过图 1 中所示的 sendMatrix 和 getMatrix 等操作，可实现数组与 DRAM 共享内存间的复制；通过 setArg 和 getArg，可实现标量与 ArgIn、ArgOut 间的传输。

Spatial 编译后，主机操作会生成 C++ 代码。从主机角度看，Accel 作用域同时充当 “黑盒”，用于生成运行加速器的目标专用库调用。这种语法可完全抽象化初始化和运行加速器过程中繁琐的目标专用细节。

目前，Spatial 假设系统仅包含一个目标可重构架构。若程序定义多个 Accel 作用域，则会按照声明顺序依次加载和运行这些作用域。不过，这一限制在未来的研究中可轻松放宽。

3.4 参数

Spatial 中的参数采用表 1f 所示的语法创建。由于编译器生成代码时每个参数必须具有固定值，因此参数的取值范围必须可静态计算。参数可用于指定可寻址片上内存和 DRAM 的维度，也可在创建计数器时用于指定参数化步长或并行化因子，还可用于指定外层控制器的流水线深度。应用的隐式和显式应用参数共同定义了编译器后续可自动探索的设计空间。

3.5 示例

最后，通过两个示例进一步说明 Spatial 语言。图 2 展示了有限脉冲响应（FIR）滤波器的流式实现，该示例表明：使用 Stream (*) 时，Spatial 的语义与其他面向数据流的流式语言类似。第 24 行循环体在 StreamIn 输入出现有效元素时执行，Spatial 通过对该循环体进行流水线处理以最大化吞吐量。

尽管在 HDL 中编写和调优基础 FIR 滤波器相对简单，但 Spatial 能更轻松地扩展简单设计。例如，该示例中权重和抽头的数量可在设备初始化时设置，无需重新综合设计；滤波器中并行合并的元素数量定义为参数，通过设计空间探索可自动调优设计，以实现最小面积或最低延迟。

图 3 展示了 Spatial 中固定大小归并排序的简单实现：将数据加载到片上高速缓存中，完成排序后再存储回主内存。该语言对片上和片外内存类型的区分，使得编写和理解此类分块设计更为自然。该实现使用静态大小的 SRAM 和两个 FIFO，对本地数据中逐步增大的块进行拆分和排序；块大小由第 8 行最外层循环决定，并以 2 的幂次递增，这种行为在 Spatial 中用 FSM（有限状态机）表达最为合适。

4 Spatial 编译器

Spatial 编译器通过源到源转换，将 Spatial 语言编写的应用转换为 Chisel RTL [9] 格式的可综合硬件描述。本节将阐述编译器的中间表示（IR）及其关键过程，如图 4 所示。除 Chisel 代码生成外，这些过程对 FPGA 和 Plasticine CGRA 的适配均通用；关于 Plasticine 适配的细节，可参考前期研究 [32]。

4.1 中间表示

在编译器内部，Spatial 程序以层级化数据流图（DFG）表示：图中的节点代表控制结构、数据操作和内存分配，边代表数据和效应依赖。控制器的嵌套结构直接映射为中间表示中的层级结构；设计参数作为图的元数据存储，可独立更新而无需修改图结构本身。

在讨论数据流图转换和优化时，将图视为控制器 / 访问树会更直观。图 5 展示了图 1 中 Spatial 代码示例中内存 tileB 的控制器树。需注意，片上与片外内存间的传输会扩展为控制节点，该节点通过迭代器（如 e 和 f）对片上内存进行线性访问。此树抽象掉了大多数基本操作，仅保留相关的控制器层级结构和特定内存的访问操作。

在 Spatial 的可加速子集中，节点正式分为三类：控制节点、内存分配节点和基本节点。控制节点代表第 3.1 节所述的 Foreach 和 Reduce 等状态机结构；基本节点代表可能消耗但不会生成控制信号的操作，包括片上内存访问。基本节点进一步细分为 “物理” 操作（需占用资源）和 “临时” 操作（仅用于编译器记账）。例如，位选择和将字组合为结构体等操作无需硬件资源，但可用于跟踪生成代码中所需的连线。

4.2 控制插入

为简化控制信号的分析，Spatial 要求控制节点不能同时包含物理基本节点和其他控制节点（条件 if 语句除外：若 if 语句不包含控制节点，则可与基本节点处于同一作用域）。为满足这一要求，需通过数据流图转换在同时包含控制节点和基本逻辑的控制循环体中插入 DummyPipe 控制节点。DummyPipe 节点是一种记账控制结构，逻辑上等效于仅执行一次的循环。此后，包含基本节点的控制节点称为 “内层” 控制节点，包含其他嵌套控制节点的控制节点称为 “外层” 控制节点。

4.3 控制器调度

控制插入完成后，编译器会对每个控制器内的操作进行调度。默认情况下，编译器会尝试对所有嵌套层级的循环进行流水线处理；用户可通过表 1b 列出的编译指示覆盖编译器的调度行为。

内层流水线调度基于其启动间隔：编译器首先根据目标相关的内部查找表，为给定控制器中的每个基本节点收集资源启动间隔（大多数基本操作的资源启动间隔为 1）；随后基于数据流图计算流水线内所有循环携带依赖。对于非可寻址内存，总启动间隔为所有依赖读操作与写操作间路径长度的最大值；对于可寻址内存，循环携带依赖的路径长度还需乘以写地址与读地址的差值。若地址与循环无关：若地址可能相等，则启动间隔为路径长度；若可证明地址不相等，则启动间隔为 1；若无法静态确定地址间的距离，则启动间隔为无穷大，即循环必须顺序执行。总启动间隔定义为所有循环携带依赖的启动间隔与所有资源启动间隔的最大值。

编译器也会以类似方式尝试对外部控制节点的循环体进行流水线处理，但数据流调度的计算对象是内层控制节点和阶段数，而非基本节点和周期数。例如，图 1 第 34 行的外层 MemReduce 包含 4 个子控制器：tileA 的加载（第 41 行）、tileB 的加载（第 42 行）、内层 MemReduce（第 45 行）以及合并中间块的归约阶段（第 53 行）。基于数据依赖，编译器可推断两个加载操作可并行执行，随后执行内层 MemReduce 和块归约操作；同时，编译器还能确定该外层循环的多轮迭代也可通过这些阶段进行流水线处理。

4.4 内存分析

只有当存在足够的片上带宽支持复制后的计算时，循环并行化才能真正提升性能。Spatial 的内存分析通过对片上内存进行分块和缓冲，最大化可用的片上读写带宽。内存分块（也称数据分区）是将内存地址空间分配到多个物理实例的过程，旨在为同一控制器内的并发访问创建额外端口。当访问模式可静态预测且能保证不会冲突访问同一端口 / 块时，即可实现分块。尽管单个端口可通过时分复用实现访问，但这会增加整个流水线的所需启动间隔，完全抵消并行化的优势。需注意，虽然通过内存复制可轻松实现分块，但 Spatial 的目标是同时最小化内存资源总消耗量。

Spatial 基于 Wang 等人 [41] 提出的冲突多面体空集测试，采用内存分块策略。本文通过考虑随机访问模式和嵌套循环中的内存访问，对该策略进行扩展：将随机访问视为冲突多面体中的额外维度（如同额外的循环迭代器）；通过识别随机值的仿射组合，最小化此类随机访问符号的数量（例如，对内存地址 x 和 x+1 的访问仅需一个随机变量 x，因为后者是前者的可预测仿射函数）；Spatial 还支持按维度分块，以应对仅部分维度访问可预测的场景。

将 FIFO 和 FILO 等非可寻址内存视为可寻址内存建模：此类内存的每次访问均表示为相对于内存定义的所有循环迭代器的线性访问。Spatial 禁止围绕非可寻址访问的外层循环并行化，因为这会破坏与顺序执行等效的行为保证。

为处理外层循环内跨阶段的多个流水线访问，Spatial 还会自动对片上内存进行缓冲。缓冲通过创建同一内存的多个副本来维护重叠循环迭代间的数据版本；若无此优化，粗粒度流水线不同阶段对同一内存的流水线并行访问将无法并发执行。有关分块和缓冲计算的详细信息，可参考附录 A.1。

例如，如图 5 所示，tileB 存在两次并行化访问（第 42 行的加载和第 48 行的读取）。若所有（隐式和显式）并行化因子均设为 2，则每轮循环对应 4 次访问。此时，Spatial 会构建各循环所有访问对应的访问多面体，并确定同时适用于两个循环的分块策略。在该示例中，SRAM 会以 2×2 块为单位进行分块，使每个 2×2 块内的元素存储在不同物理块中，从而支持完全并行访问。若第 34 行的 MemReduce 采用流水线处理，则 tileB 会采用双缓冲机制，以避免外层循环当前迭代的读取（第 48 行）与下一轮迭代的写入（第 42 行）产生冲突。

4.5 面积与运行时估算

Spatial 通过两轮估算过程评估给定参数集，近似计算应用的面积和运行时。这些过程基于与前期 Delite 硬件定义语言（DHDL）[22] 类似的解析资源和运行时模型，但 Spatial 扩展了该模型，以支持流吞吐量、任意控制流和有限状态机。运行时和面积利用率模型均基于每个目标平台约 2000 次一次性特征化运行构建。

4.6 设计空间探索

编译器确定的调度和内存分块选项，与循环并行化和块大小参数共同构成应用的设计空间。设计调优过程是编译器的可选过程，通过快速探索该设计空间，实现性能 / 面积的权衡。启用设计调优后，编译器会反复选择设计点，并通过重新运行控制调度、内存分析和估算分析过程对其进行评估；探索结果是帕累托前沿（Pareto frontier）上的一组参数。

然而，应用设计空间通常极为庞大， exhaustive 搜索（穷举搜索）往往不可行。在第 5 节讨论的基准测试中，仅 BlackScholes 的设计空间相对较小（约 80,000 个设计点），Spatial 可在几分钟内完成穷举搜索；而其他设计空间规模可达106至1010个设计点，穷举搜索需数小时甚至数天。例如，即使图 1 代码中仅暴露少数显式设计参数，结合隐式流水线和并行化参数，该代码的潜在设计数量已达约2.6×108个。DHDL [22] 采用启发式剪枝后随机搜索的方法，将设计空间规模减少 2-3 个数量级，但这种方法在较大设计空间上的方差较大，且可能意外剪枝掉优质设计点。

为降低较大设计空间上的方差，Spatial 的设计空间探索流程集成了名为 HyperMapper [11, 27, 36] 的基于主动学习的自动调优器。HyperMapper 是一种多目标无导数优化器（DFO），已在 SLAMBench 基准测试框架 [28] 中得到验证。HyperMapper 使用随机森林回归器构建代理模型，预测参数空间的性能；该回归器最初仅基于数百个随机设计点样本构建，并在后续主动学习步骤中迭代优化。

4.7 展开

确定设计参数值后，Spatial 通过单次图转换完成参数最终确定：根据前期分析过程的结果，对循环进行展开并复制内存。Reduce 和 MemReduce 模式也会转换为命令式实现，并根据给定的归约函数实例化硬件归约树。例如，图 1 中的两个 MemReduce 循环会分别转换为具有显式分块内存访问和显式复制乘法操作的展开 Foreach 循环；相应的块归约（第 52-53 行）会转换为 Foreach 的第二阶段，并包含与循环并行化匹配的显式归约树。

4.8 重定时

展开完成后，编译器会对每个内层流水线进行重定时，确保数据和控制信号正确对齐，并满足目标时钟频率要求。具体而言，编译器基于效应和数据流顺序对每个流水线内的基本操作进行排序（通过对数据和效应依赖进行反向深度优先搜索计算）；随后通过正向深度优先搜索最小化归约循环中的延迟。基于此排序，编译器根据将每个基本节点映射到相关延迟的查找表，插入流水线和延迟线寄存器。延迟小于一个完整周期的依赖节点保留为组合逻辑，仅在最后一个操作后插入寄存器。这种寄存器插入方式可在最大化控制器可达时钟频率的同时，最小化所需的启动间隔。

4.9 代码生成

代码生成前，编译器首先为所有 ArgIn、ArgOut 和 HostIO 分配寄存器名称。在对中间表示（IR）的最后一轮处理中，代码生成器从自定义参数化 RTL 模板库（以 Chisel 编写）实例化硬件模块，并推断和生成用于连接这些模块的逻辑。这些模板包括管理应用中各类控制结构与基本操作间通信的状态机，以及分块缓冲内存结构和高效算术运算。最后，所有生成的硬件封装在目标专用的参数化 Chisel 模块中，该模块负责协调加速器与目标 FPGA 上外设的片外访问。

5 评估

本节通过以下三个方面评估 Spatial：（1）与赛灵思商用 HLS 工具 SDAccel 相比，Spatial 在开发效率和生成设计性能方面的优势；（2）HyperMapper 设计调优方法的有效性；（3）Spatial 代码在不同架构间的可移植性。

5.1 FPGA 性能与开发效率

首先评估 Spatial 在 FPGA 性能和开发效率方面相较于 SDAccel（赛灵思基于 C 的商用可编程工具，用于创建高性能加速器设计）的优势。选择 SDAccel 作为对比工具的原因在于：其性能和开发效率目标与 Spatial 相似，支持流行的 OpenCL 编程模型，且能进行循环流水线、展开和内存分块等相关优化 [42]。表 2 中基准测试的基线实现要么来自赛灵思公开的 SDAccel 基准测试套件 [45]，要么为手工编写；每个基线实现均通过添加适当的 HLS 编译指示 [43] 进行手工调优，包括选择循环流水线、展开和数组分块因子，以及启用数据流优化。Spatial 的设计点通过第 4.6 节所述的 DSE 流程选择。

开发效率通过描述 FPGA 内核的源代码行数（排除主机代码）衡量；性能通过在亚马逊 EC2 F1 实例上的赛灵思 UltraScale+ VU9P 板（结构时钟频率 125 MHz）上运行基准测试，对比运行时和 FPGA 资源利用率衡量。通过 Spatial 和 SDAccel 分别为每个基准测试生成针对 VU9P 架构的 FPGA 比特流，并从布局布线后报告中获取资源利用率数据；随后在 FPGA 上运行并验证两种设计，测量板级执行时间（排除 CPU 准备代码和 CPU 与 FPGA 间的数据传输时间）。

表 2 列出了输入数据集大小，以及 SDAccel 和 Spatial 在源代码行数、资源利用率和运行时方面的完整对比。在开发效率方面，Spatial 中的 load 和 store 等用于从 DRAM 传输密集型 / 稀疏数据的语言结构，可减少代码冗余并提高可读性；此外，通过隐式推断并行化因子和循环启动间隔等参数，Spatial 代码基本无需注释和编译指示。

在性能方面：

• BlackScholes 和 TPC-H Q6 基准测试中，Spatial 相较于 SDAccel 的速度提升分别为 1.63 倍和 1.33 倍。这两个基准测试均通过深度流水线数据通路从 DRAM 流式读取数据，非常适合 FPGA 加速；SDAccel 中的 DATAFLOW 编译指示 [44] 和 Spatial 中的流式支持，均能高效加速此类工作负载。
• K-Means 基准测试中，Spatial 通过粗粒度流水线支持，在使用 1.5 倍 fewer 块 RAM（BRAM）的情况下，实现了与 SDAccel 相近的性能。
• PageRank 基准测试中，专用的 DRAM 散列 / 聚集支持使 Spatial 的速度提升 3.48 倍。
• 计算密集型工作负载 GDA、GEMM 和 SW 中，Spatial 的速度提升分别为 8.48 倍、1.37 倍和 14.15 倍。其中，SW 的基线实现由赛灵思采用 systolic array（脉动阵列）实现，而 Spatial 实现采用嵌套控制器；GEMM 和 GDA 中存在粗粒度流水线优化机会，Spatial 可充分利用这些机会。以 GDA 为例，其包含外积操作 —— 同一缓冲中的数据会被重复访问和复用。尽管该操作可与生成数组的前序循环进行流水线处理，但 SDAccel 的 DATAFLOW 编译指示不支持此类涉及数据复用的访问模式，导致 SDAccel 需采用更大的数组分块和循环展开因子来抵消性能损失，代价是消耗更多 FPGA BRAM。此外，Spatial 中 GEMM 的嵌套控制器可独立并行化和流水线处理，而 SDAccel 若对外部循环进行并行化，会自动展开所有内层循环；因此，Spatial 可探索 SDAccel 中难以表达的设计点。最后，由于 Spatial 编译器对参数化中间表示（IR）进行分析，无需扩展 IR 图即可处理更大的并行化因子；而 SDAccel 在预处理阶段展开图，当展开和数组分块因子较大时，会生成更大的图，这对编译器的内存占用和编译时间产生显著影响，使得难以或无法找到更优设计。

综上，Spatial 为 FPGA 编程提供了高效平台：所有基准测试的代码行数平均减少 42%；相较于工业级 HLS 工具，Spatial 生成的设计在所有基准测试中的几何平均速度提升 2.9 倍。

5.2 设计空间探索

接下来初步评估 HyperMapper 在两个设计目标（设计运行时和 FPGA 逻辑利用率（LUT））上快速逼近帕累托前沿的能力。评估中，HyperMapper 采用多个初始随机样本种子，样本数量 R 范围为 1-6000 个设计点，且每轮主动学习最多包含 100 个样本，共进行 5 轮。作为对比，DHDL 研究 [22] 中提出的启发式搜索方法首先通过简单启发式剪枝，再随机采样最多 100,000 个设计点。两种方法的设计调优时间均为 1-2 分钟（因基准测试复杂度略有差异）。

图 6a 展示了 BlackScholes 基准测试中，超体积指标（HVI）随初始随机样本数量变化的情况。HVI 表示估算的帕累托前沿与通过穷举搜索得到的真实帕累托曲线之间的面积。随着主动学习阶段引导样本数量的增加，HVI 提升两个数量级；同时，总体方差随随机样本数量增加快速下降。这表明自动调优器对随机性具有较强鲁棒性，仅需少量随机样本即可启动主动学习阶段。如图 6b 所示，HyperMapper 仅需不到 1500 个设计点，即可实现对真实帕累托前沿的近似逼近。

对于 GDA 等设计空间较稀疏的基准测试，HyperMapper 需花费大量时间评估无法在 FPGA 上实现的无效设计点，导致其精度低于启发式方法。因此，未来研究计划为 HyperMapper 扩展有效设计预测机制，并在更广泛的基准测试中评估该调优方法。

5.3 Spatial 可移植性

首先通过适配两种不同 FPGA 架构，验证 Spatial 代码的可移植性：（1）Zynq ZC706 SoC 板；（2）亚马逊 EC2 F1 上的 Virtex UltraScale+ VU9P。VU9P 上的设计采用单 DRAM 通道，峰值带宽 19.2 GB/s；相较于 VU9P，ZC706 的 FPGA 资源更少，DRAM 带宽更低（4.26 GB/s）。对表 2 中所有基准测试，均通过同一 Spatial 代码适配 ZC706 和 VU9P，并通过针对各目标的专用模型和自动 DSE 对基准测试进行调优；两种 FPGA 的时钟频率均固定为 125 MHz。

表 3 展示了 VU9P 相对于 ZC706 的速度提升。结果表明：同一 Spatial 源代码不仅可移植到具有不同能力的架构，还能通过自动调优充分利用各目标的资源优势。BlackScholes、GDA、GEMM 和 KMeans 等计算密集型基准测试在 VU9P 上的速度提升最高达 23 倍。仅将这些设计移植到 VU9P，即可通过主内存带宽提升实现 1.2-2.5 倍的速度提升；而更大 FPGA 的主要优势在于，可通过调优并行化因子以利用更多资源。尽管 SW 也属于计算密集型，但 ZC706 的资源限制了数据集大小；在这种情况下，VU9P 更大的容量虽未提升运行时性能，但支持处理更大的数据集。

内存密集型基准测试 TPC-H Q6 受益于 VU9P 更高的 DRAM 带宽：仅移植该基准测试，即可通过主内存带宽提升实现 4.6 倍的运行时改善；进一步对控制器进行并行化处理，创建更多并行 DRAM 地址流，可更好地利用这一带宽优势。PageRank 也属于带宽密集型，但 VU9P 的主要优势在于通过专用化内存控制器，最大化稀疏访问的带宽利用率。

最后，通过将编译器扩展为支持将 Spatial 中间表示（IR）映射到前期提出的 Plasticine CGRA [32]，验证 Spatial 在 FPGA 之外架构上的可移植性。Plasticine 是由计算（PCU）和内存（PMU） tile 组成的二维阵列，具有静态可配置互连和位于外围的地址生成器（AG）（用于执行 DRAM 访问）。Plasticine 架构与 FPGA 存在显著差异，对内存分块和计算的约束更严格（如固定大小的流水线 SIMD 通道）。

Plasticine 仿真采用 16×8 阵列（包含 64 个计算 tile 和 64 个内存 tile），时钟频率 1 GHz，主内存采用 DDR3-1600 通道（峰值带宽 12.8 GB/s）。表 4 列出了部分基准测试的 DRAM 带宽、资源利用率、运行时，以及 Plasticine CGRA 相对于 VU9P 的速度提升。

TPC-H Q6 等流式带宽密集型应用可高效利用约 97% 的可用 DRAM 带宽；GDA、GEMM 和 KMeans 等计算密集型应用利用了 Plasticine 约 90% 的计算 tile。Plasticine 更高的片上带宽使其能更充分地利用计算资源，使得这些应用的速度提升分别达 9.9 倍、55.0 倍和 6.3 倍。类似地，BlackScholes 中的深度计算流水线在跨多个 tile 拆分后，占用了 73.4% 的计算资源，速度提升 1.6 倍。

6 相关工作

基于第 2 节提出的标准，本节对 Spatial 与相关研究进行定性对比。

硬件描述语言（HDL）

Verilog 和 VHDL 等硬件描述语言专为任意电路描述设计，为实现最大通用性，要求用户显式管理时序、控制信号和本地内存；循环在扁平化 RTL 中通过状态机表达。Bluespec SystemVerilog [8] 是一个例外，它支持从嵌套 while 循环推断状态机。HDL 的最新进展主要集中在元编程改进和扩展硬件模块库：Chisel [9]、MyHDL [1] 和 VeriScala [23] 等语言通过将 HDL 嵌入软件语言（如 Scala 或 Python），简化了电路的过程式生成；Genesis2 [37] 为 SystemVerilog 添加 Perl 脚本支持，以助力过程式生成。尽管这些改进相较于 Verilog 生成语句，提供了更强大的元编程能力，但用户仍需在时序电路层面编写程序。

Lime

Lime 是 IBM 基于 Java 的编程模型和运行时系统，旨在提供一种统一语言用于编程异构架构。Lime 原生支持自定义位精度，包含集合操作，编译器可从中推断并行性；通过 “任务” 表达粗粒度流水线和数据并行性；利用 connect、split 和 join 等内置结构构建粗粒度流式计算图；Lime 运行时系统负责流图的缓冲、分块和调度。然而，Lime 不支持偏离流式模型的粗粒度流水线，程序员需使用低层级消息传递 API 处理带有反馈循环的粗粒度图；此外，编译器不支持自动设计调优，且未明确说明其在多维度数据结构针对任意访问模式分块方面的能力，因此无法确定其是否能实例化分块和缓冲内存。

高级综合（HLS）工具

LegUp [12]、Vivado HLS [3]、英特尔 FPGA OpenCL SDK [5] 和 SDAccel [42] 等高级综合工具允许用户用 C/C++ 和 OpenCL 编写 FPGA 设计。借助这些工具，应用可通过数组和无时间约束的嵌套循环进行高层级描述。然而，尽管编译器会进行内层循环流水线、展开和内存分块与缓冲，但这些操作通常需要用户添加显式编译指示。虽然已有研究利用多面体工具，实现了对单个循环嵌套内仿射访问的自动分块决策 [41]，但未解决非仿射场景或同一内存在多个循环嵌套中被访问的场景。尽管 Vivado HLS 的 DATAFLOW 等编译指示支持有限的嵌套循环流水线，但尚未支持任意循环嵌套层级的流水线 [2]。Aladdin [38] 等工具可帮助自动化 HLS 程序中的编译指示调优，但 HLS 设计仍需手工进行硬件优化 [26]。

MaxJ

MaxJ 是 Maxeler 公司推出的专有语言，允许用户在 Java 库中表达数据流算法，其时序关注点在于有效流元素的 “滴答数”（tick），而非周期 [24]。用户在编写嵌套循环时，需退回到扁平化、类 HDL 的状态机语法；内存基于相对流偏移推断，虽对流处理较为便捷，但向用户隐藏了有助于优化的硬件实现细节。此外，MaxJ 的可移植性有限，目前仅支持适配 Maxeler 公司的 FPGA 平台。

DHDL

Delite 硬件定义语言（DHDL）[22] 是 Spatial 的前身，允许程序员描述无时间约束、嵌套且可并行化的硬件流水线，并将其编译为硬件。尽管 DHDL 支持编译器感知的设计参数和自动设计调优，但不支持数据依赖控制流、流式处理和内存控制器专用化；同时，DHDL 不支持通用内存分块或缓冲，依赖其后端 MaxJ 进行重定时和启动间隔计算。

图像处理领域特定语言（DSL）

近期提出的图像处理 DSL 为适配 GPU 和 FPGA 等各类加速器平台提供了高层级规范。由于领域范围较窄，这些 DSL 能提供更简洁的抽象机制用于指定模板操作；在适配加速器时，通常采用源到源转换。例如，HIPACC[25] 通过 C 类前端的源到源编译器，生成 CUDA、OpenCL 和 Renderscript 以适配 GPU；Halide [35] 的近期研究通过生成中间 C++ 和 Vivado HLS [33]，实现了对异构系统（包括赛灵思 Zynq 的 FPGA 和 ARM 核）的适配；Rigel [20] 和 Darkroom [19] 生成 Verilog；PolyMage [14] 生成 OpenMP 和 C++ 用于高级综合。Rigel 和 Darkroom 支持在 FPGA 上生成专用内存结构（如行缓冲）以捕获数据复用；HIPACC可从固定访问模式集合中推断 GPU 上的内存层级结构。这些 DSL 可捕获特定模板内的并行性（通常跨图像通道和图像处理流水线）。

与图像处理 DSL 相比，Spatial 的通用性更强，抽象层级更低：Spatial 可表达任意循环层级的流水线和展开，显式暴露内存层级结构，同时能针对任意访问模式自动对内存进行分块、缓冲和复制。这些特性，结合 Spatial 的设计调优能力，使其成为图像处理 DSL 优化后端的理想选择。

7 结论

本文提出了一种名为 Spatial 的新型领域特定语言，用于可重构架构上应用加速器的设计。Spatial 包含针对控制、内存和设计调优的硬件专用抽象机制，有助于在高效开发与面向性能的加速器设计之间取得平衡。实验表明，Spatial 可通过单一源代码适配多种可重构架构，且相较于 SDAccel，平均速度提升 2.9 倍，代码长度减少 42%。

Spatial 语言与编译器是斯坦福大学正在进行的开源项目，相关文档和版本发布可在https://spatial.stanford.edu获取。

附录 A

A.1 内存分块与缓冲

图 7 给出了 Spatial 针对循环嵌套中给定内存 m 的访问进行分块和缓冲的算法伪代码。对于内存 m 的每次访问 a，首先定义该访问的迭代域 D—— 即包含 a 但不包含 m 的所有循环的迭代器可能取值构成的多维空间。

随后，将内存 m 的读访问和写访问分组为 “兼容” 集合 —— 这些访问在同一物理端口上并行发生，但可一起分块（第 1-14 行）。对于迭代域 D₁和 D₂内的两个访问 a₁和 a₂，若满足以下条件，则称它们具有分块兼容性（IComp）：
IComp(a1​,a2​)=∄i∈(D1​∪D2​)s.t.a1​(i)=a2​(i)
其中，a (i) 表示访问 a 在迭代器向量 i 取值下对应的多维地址。该判断可通过多面体空集测试实现。

分组完成后，每个组可直接映射为内存 m 的一个一致性 “实例”（副本），但这种方式通常会消耗过多资源。为最小化内存实例总数，接下来采用贪心策略合并组（第 25-39 行）：当合并实例的成本低于为该组添加单独一致性实例的成本时，进行合并。对于两组访问 A₁和 A₂，若满足以下条件，则允许合并（OComp）：
OComp(A1​,A2​)=∄(a1​∈A1​,a2​∈A2​)s.t.
LCA(a1​,a2​)∈Parallel∪(Pipe∩Inner)
其中，Parallel、Pipe 和 Inner 分别表示程序中的并行、流水线和内层控制器集合。若满足该条件，则两组实例间的所有访问要么顺序发生，要么作为粗粒度流水线的一部分发生：顺序访问可通过时分复用实现，流水线访问则通过缓冲实现。

ReachingWrites 函数返回每个集合中可能对给定读访问集合可见的所有写访问 —— 若写访问可能在读访问之前执行，且地址空间可能重叠，则该写访问对读访问可见。

BankAndBuffer 函数从内存读写访问生成单个内存实例：其中，每组访问对应内存实例单个端口的并行读写；不同组的访问保证不会同时访问同一端口。因此，需找到对所有访问组均无块冲突的通用分块策略，该策略通过 Wang 等人 [41] 所述的迭代多面体空集测试确定 —— 对每个候选策略，针对每组并行访问运行一次空集测试。

内存 m 的两个访问 a₁和 a₂所需的缓冲深度 d 计算如下：
d(a1​,a2​)={1dist(a1​,a2​)​LCA(a1​,a2​)∈Seq∪StreamLCA(a1​,a2​)∈Pipe​
其中，dist 表示最小公共祖先（LCA）的深度与包含 a₁和 a₂的 LCA 直接子节点的数据流距离中的较小值；Seq、Stream 和 Pipe 分别表示顺序、流式和流水线控制器集合。目前，Spatial 不支持跨流式访问对可寻址内存进行缓冲。读访问集合 R 和写访问集合 W 的缓冲深度计算如下：
Depth(R,W)=max{d(w,a)∀(w,a)∈W×(W∪R)}

缓冲内每个访问的端口由所有缓冲访问间的相对距离确定。Spatial 要求合并实例中最多包含一个粗粒度控制器或流式控制器。贪心搜索的最终输出是内存 m 所需的物理内存实例集合。