导读
本篇博客次要解说公布于 Microprocessors and Microsystems 的文章《Semi-static Operator Graphs for Accelerated Query Execution on FPGAs》，介绍它所提出的算法与试验后果，并结合实际状况给出一些思考。
一、背景介绍
在当今的数据化场景越来越丰盛的大环境下，涌现出的非结构化数据存储剖析被利用于少数畛域。为了使机器可能主动剖析数据，语义网络的概念被创立，元数据被用来形容和链接任何类型的数据和资源。
面对存储和解决大规模的数据，除了一直被优化的数据结构外，硬件也是须要被极大优化的。海量数据的继续存储在当今硬件环境下是没有问题的，然而要实现在一个能够被承受的、被容许的工夫范畴内进行解决和剖析则变得愈发艰巨。
因而，许多数据库系统逐步偏向于异构，由专门的计算内核来无效地执行特定的工作。
那么不得不提的，便是高性能计算罕用到的 GPU（图形处理器）。GPU 最突出的长处是高性能，即高密度运算和高效并行性，非常适合解决计算密集型的工作；同时，其易于连贯到处理器端的属性也是它能够被广泛应用的起因。然而，其毛病也是不言而喻的，就是高功耗。
在 GPU 之外，还存在为特定工作设计的专有硬件加速器，其对于指定的工作领有较高的性能，然而其应用十分的不灵便，只能解决特定的工作，从新扩大的性能简直为零。
最初，则是最近被宽泛应用的 FPGA，它具备动静局部重配置的能力，能够放大 CPU 的灵活性和专用硬件加速器的性能之间的差距，并且还领有低功耗、高并发的劣势。
FPGA 卡的外围局部示意图
如上图所示，一块 FPGA 芯片由可配置逻辑模块（CLB）形成，每个 CLB 都蕴含特定的构造，如：查找表（LUT）、多路复用器、进位链、触发器等。除此之外，一块 FPGA 卡上还有 BRAM（Block RAM），能够将其设想成 CPU 中 cache 的角色，以及 DSP (数字信号处理器）和一些通信接口（PCIe 等）。
这篇文章通过引入半动态操作符图，设计了一个 FPGA-CPU 异构的图数据库系统，减速了在大规模语义数据集上的查问性能。
二、相干工作
上图为一个 FPGA-CPU 混合解决运算的根本架构，客户端应用程序向混合数据库服务器发送查问，该服务器应用基于 FPGA 的硬件加速器通明地确定后果。
文中次要援用的内容为：
Dennl 等人提出了关系型数据库 MySQL 中 SQL 查问的实时硬件加速的概念，但他们次要关注限度和聚合操作符，因而无奈在 FPGA 上执行残缺的查问。
Becher 等人增加了更简单的运算符（例如：归并连贯、小数据集上的排序）。对于一个蕴含一个 Join 的简略的查问，它们的性能与规范的基于 x86 的零碎相当，不过能源效率更高一些。
Woods 等人提出了 Ibex，一种用于关系数据库 MySQL 的智能存储引擎，能够反对应用 FPGA 卸载简单的查问操作符。
Wang 等人应用 OpenCL high level synthesis(HLS) 将数据库操作符实现为 FPGA 的 Kernel。然而查问只用到了范畴检查和一个 Join，绝对简略。
Heinrich 等人提出了一种混合索引构造，它在 FPGA 上存储包含根节点在内的高层 B+ 树，在主机上存储包含叶子节点在内的低层。
而本文是第一个针对语义 Web 数据库齐全集成的基于 FPGA 的查问引擎。
在介绍本文的混合数据库系统之前，先介绍一下本文用到的图数据库根底。论文的工作是基于一个开源的图数据库系统 LUPOSDATE，它反对残缺的 SPARQL 1.0 和 SPARQL 1.1 规范查询语言。论文通过引入基于 FPGA 的查问引擎，与 LUPOSDATE 零碎联合在一起。
LUPOSDATE 应用 RDF 三元组作为根本数据格式来形容 Web 资源，RDF 三元组示意为 <s，p，o>，其中 s 是 subject (主语)、p 是 predicate (谓词)、o 是 object (宾语)。
相应的，LUPOSDATE 存储的 B+ 树索引构造有六种：SPO、SOP、PSO、POS、OSP、OPS，能够在检索时不便的失去有序的三元组。除此之外，LUPOSDATE 还保护一个 ISTree 和一个 SITree，用于 RDF 字符串和整数 id 之间的映射，这有利于 FPGA 模块的设计，因为 FPGA 无奈解决不定长度的字符串。
如下图所示，对于给定的一个 SPARQL 查问：
LUPOSDATE 语法分析器会产生相应的变量数组和操作符图：
三、论文解决的问题
本文实现的混合数据库系统是一个 LUPOSDATE 的扩大，由 CPU 主机和 FPGA 异构而成，如上图所示。主机提供更高层级的性能，如用户界面、查问优化、评估指标保护等，而 FPGA 被用作查问执行时的自适应加速器。主机和 FPGA 之间的通信是基于外设原件 PCIe 的。
FPGA 区域被划分为动态逻辑和许多个小 RP，每个 RP 能够配置任意类型的运算符，每个运算符作为一个可配置模块是提前生成的。动态逻辑蕴含与理论查问构造独立的模块，包含 PCIe 接口、一个治理模块和查问协调器（QC）。
QC 的次要工作是将传入的三元组交给最上层的 RP 进行相应索引构造的导入，以及检索和序列化变量数组用以生成最终后果。此外，每个 RP 之间的互联也位于动态逻辑中。每个实现的查问操作符都应用了如下图所示的一个公共模板：
每个操作符至少有两个前向操作符和一个后向操作符，如果一个操作符只须要一个前向操作符，那么只有右边的输出被启用。每一个输出或输入都有如下参数：一个 data 向量对应输入输出的数组，一个 valid 信号示意数据的有效性，一个 finished 参数指定数据的结尾，一个反向 read 信号告诉前向操作符数据曾经被读取，并且在新数据到来之前不会进行操作。最初，数据的宽度也必须作为一个参数传入，因为 FPGA 无奈反对变长的数据类型。
上面介绍一下论文实现的操作符：
RDF3XIndexScan：RDF3XIndexScan 是 QC 和外部操作符之间的分割。这个操作符的次要指标是从 QC 中接管三元组，并将它们所需的组件映射到变量数组的某个地位。它保护三个 one-hot 编码的向量，每个向量的第 i 位代表第 i 个变量，如果某一个元素是常量，那么就将其所有地位为 1。
Join：Join 操作符是天然连贯，本文应用的是 MergeJoin 的形式。它保护一个 one-hot 编码的向量，向量的第 i 位代表第 i 个变量，指代要 Join 的变量。
Filter：Filter 操作符是用于执行条件查问。简单的 Filter 表达式将被合成为多个简略的 VALUE COND VALUE 的 Filter 操作符。其中，VALUE 能够是一个值、一个变量或一个式子，COND 是比拟条件。但因为 FPGA 无奈解决字符串的问题，所以通过将字符串映射为整数 id 之后，零碎只能反对相等和不相等的比拟。
Projection：Projection 操作符是用于将须要的变量后果从变量数组中投影进去。
Union：Union 操作符就是简略的将两个前向操作符失去的后果做一个并集操作。
Limit 和 offset：Limit 操作符会转发特定数量的后果给变量数组。而 offset 操作符会跳过特定数量的后果。它们个别作为操作符图的最初几步。
从混合系统结构图中能够看到，每个 RP 之间并不是间接输入输出互联，而是通过了一个上图所示的半动态路由元素（SRE）构造。论文以一个两路复用 SRE 为例，当 succ_sel 信号为 0 时，数据流会间接向下路由，为 1 时，会向另一侧路由。SRE 的存在使得能够用更少的 RP 组成一个反对查问范畴更大的半动态操作符图。
四、混合系统工程流程
上图给出了混合系统的工作流程图，能够将其分为部署阶段和零碎运行时。在部署阶段，除了须要导入数据之外，整个动态逻辑必须部署在 FPGA 上，每个操作符对应的 RM 也须要提前生成并存储在 RM 库中。
在零碎运行时，主机通过剖析输出的 SPARQL 查问，将其解析成相应的操作符图，检测其是否能够用配置在 FPGA 上，如果有不反对的操作符存在，那么会间接 CPU 端执行查问，如果所有操作符都反对，那么 ICAP 会抉择对应操作符的 RM 配置在 FPGA 的半动态操作符图上。主机通过 PCIe 向 FPGA 端提供输出三元组，并接管 FPGA 端发回的后果进行后处理，FPGA 端负责具体的计算工作。
五、试验后果
本文应用的是 Xilinx 的 Virtex-6 FPGA 卡和 PCIe 2.0 八通道通信接口，在 SP2Bench 三个不同大小的数据集（66M，131M 和 262M 个三元组）上进行了试验。下图是他们采纳的 SPARQL 查问示例：
Query 1 是用到了 Filter 操作符的查问，Query 2 是用到了 Union 操作符的查问，Query 3-5 别离是用到了不同数量的 Join 操作符。他们在 FPGA 端部署的半动态操作符图如下：
最初的试验结果表明，退出了 FPGA 的混合系统比原来的 LUPOSDATE 零碎的查问执行速度更快。并且随着数据规模的增大，减速比会更大，阐明混合系统更加适宜大规模的数据集上的查问。
六、总结
在这篇文章中，作者在 FPGA 上引入了半动态运算符图（SOG）的概念，为语义网数据库中的查问执行提供灵便的硬件加速器。作者没有为给定的查问零碎运行时生成一个 FPGA 配置，而是以肯定水平的灵活性部署了通用查问构造。
SOG 由多个具备公共接口的 RP 组成。在为每个 RP 部署零碎期间，会生成一组局部位文件的 RM，并将其存储到存储库中。在零碎运行时，作者的混合系统针对给定的 SPARQL 查问抉择 RM，并通过 ICAP 将其配置为 RP，RP 设置 FPGA 上运算符图的最终构造。作为这项工作的次要奉献，耗时的 RM 生成在零碎运行时之前执行，并且信号大大减少了查问执行期间的重新配置。