FPGA在内存数据库加速中的应用：综述

FPGA在内存数据库加速中的应用：综述

• 基本概念
• • 异构计算
  • • CPU
    • GPU
    • FPGA
    • DSP
    • ASIC
    • 内存数据库（重新定义一下）
• 1 背景
• • FPGA在数据库中出现的原因
  • • FPGA的缺点
    • 新技术的发展开始利好FPGA
  • 2 FPGA背景
  • • 2.1 FPGA结构
  • 2.2 FPGA的特点
  • • 2.3 FPGA的编程
• 3 基于FPGA的数据库系统
• • 标题3.1 FPGA作为带宽放大器
• 3.2 FPGA作为IO连接加速器
• • 3.3 FPGA作为协同处理器
• 5 技术趋势
• • 5.1 数据库系统趋势
  • 5.2 系统互连趋势
  • • 5.2.1 增加系统互连带宽来解决带宽问题
    • 5.2.2 使用共享内存和一致性解决IO连接瓶颈
  • 5.3 使用HBM（高带宽内存）来提高带宽和内存
• 6 查询操作符的加速
• • 6.1 解压缩算法
  • 6.2 排序
  • • 6.2.1 排序网络
    • 6.2.2 FIFO归并排序器
    • 6.2.3 归并树
  • 6.3 join（连接）
  • • 6.3.1 哈希连接
    • 6.3.2 排序归并连接
• 7 未来研究方向
• • 7.1 数据库结构
  • 7.2 加速器设计
  • 7.3 与GPU的比较
  • 参考文献

基本概念

异构计算

异构计算主要是指使用不同类型计算单元（CPU、GPU等协处理器、DSP、ASIC、FPGA等），不同类型的指令集和不同的体系结构组成的一个混合的系统。
异构计算是一种并行计算的特殊方式 ，采用分布式布局，它能将结构不同、 性能不同的各种机器部件合理的分配安排 ，充分发挥各个硬件的特性来满足计算的需求 ，并且使得代码或者代码段所支配的资源更加合理的使用，以达到性能最大化的目的。
异构就是将CPU、图形处理器（Graphics Processing Unit, GPU）、专用集成电路（Application Specific Integrated Circuit, ASIC）、数字信号处理器（Digital Signal Processing, DSP）、现场可编程门阵列（Field Programmable Gate Array, FPGA）、精简指令集计算机（Reduced Instruction Set Computer, RISC)等各种计算单元组合成一个混合的系统，充分发挥各个硬件性来满足计算的需求，并且使得代码或者代码段所支配的资源更加合理的使用，以达到性能最大化的目的。
下图是一个异构计算加速平台的结构，四片FPGA芯片同时放置在一张FPGA板卡上，四片FPGA芯片通过RapidIO互联。

CPU

英文全称：Central Processing Unit
中文全称：*处理器
功能：是一台 PC 的核心（运算核心和控制核心）。
缺点：算力最弱，处理复杂性高的计算时，计算性能不理想；核处理数（最少）
优点：

1. 主频（最高）（3G、4G以上）；
2. 管理能力（最强），擅长管理和调度，比如数据读取，文件管理，人机交互等等。

GPU

英文全称：Graphics Processing Unit
中文全称：图形处理器
功能：
传说中的 “显卡”，是一种专门在个人电脑、工作站、游戏机和一些移动设备（如平板电脑、智能手机等）上图像运算工作的微处理器，同时也是显卡的 “心脏”，专为执行复杂的数学和几何计算而设计的。
缺点：管理能力（最弱），功耗（最高）
优点：

1. 核处理数（最多）（并行处理和块处理的典型例子）；
2. 擅长浮点运算和并行计算
   

FPGA

英文全称：Field Programmable Gate Array
中文全称：现场可编程门阵列
功能：是作为专用集成电路（ASIC）领域中的一种半定制电路而出现的，既解决了定制电路的不足，又克服了原有可编程逻辑器件门电路数有限的缺点
缺点：

1. 成本高（这就是为什么全球大量生产的 iPhone7 出现了一小块 FPGA 芯片就引发了巨大的讨论）；
2. 资源贵（SRAM（静态随机存取存储器） 工艺实现的查找表结构）。
   优点：
3. 既能管理又能运算（如工业控制 FPGA）；
4. 实时性（最强！！！）：具有很强的并行计算能力，处理速度快，流水线并行和数据并行（延迟低，流处理）（而 GPU 只有数据并行）；
5. 灵活性（最强！！！）：可编程逻辑器件，可以实时地根据不同的算法做不同的硬件方面的电路优化。
6. 功耗（相比之下较低）：单位功耗下计算性能优于GPU的计算性能 ，功耗大约是GPU的十分之一 。

DSP

英文全称：Digital Signal Processing
中文全称：数字信号处理
功能：DSP 芯片，也称数字信号处理器，是一种特别适合于进行数字信号处理运算的微处理器，其主要应用是实时快速高性能地实现各种数字信号处理算法，而与通用微处理器相比，DSP芯片的其他通用功能相对较弱些。

ASIC

英文全称：Application Specific Integrated Circuit
中文全称：专用集成电路
功能：在集成电路界 ASIC 被认为是一种为专门目的而设计的集成电路。是指应特定用户要求和特定电子系统的需要而设计、制造的集成电路；ASIC 的特点是面向特定用户的需求，ASIC 在批量生产时与通用集成电路相比具有体积更小、功耗更低、可靠性更高、性能更高、保密性增强、成本降低等优点。

内存数据库（重新定义一下）

In-memory database（IMDB）,即内存数据库，是一种依赖于主存作为数据存储介质的一种数据库管理系统。相比传统的基于磁盘的数据库管理系统，IMDB速度快得多。这取决于CPU能够直接访问IMDB，在I/O路径与延迟方面有了质的飞跃。另外，CPU本身提供的原子操作，内存栅障以及高速缓存冲刷指令可以为IMDB提供简单高效的原子性，一致性服务。

1 背景

FPGA在数据库中出现的原因

1. CPU：传统的数据库系 统 中 ，CPU是核 心 ，负责整个数据库系统的管理 、 调 度 、 运算等工作 。 然而，CPU的 性能瓶颈主要是计算能力弱。提升CPU时钟频率和内核数量来提高计算能力时，遇到了散热和能耗瓶颈。
2. GPU：GPU虽然工作频率较低，具有更多的内核数和并行计算能力，总体性能/芯片面积的比，和性能/功耗比都很高。
3. FPGA：因其高并行性、可重构性和低功耗而被数据库社区认可，并可作为IO设备连接到CPU上，来加速数据库分析。
4. 许多研究已经证明FPGA可以作为加速器来实现高吞吐量。例如：IBM Netezza 把FPGA部署在硬盘驱动器（hdd）和CPU之间的数据路径中，执行解压缩和预处理，减轻了CPU中的计算压力，间接地放大了硬盘的带宽以提高数据库的分析性能。

FPGA的缺点

1. 通信开销大：FPGA加速器的接口带宽很低，成为高带宽内存数据库的瓶颈。在主存和FPGA之间传输数据的成本已经超过FPGA的计算成本。
2. GPU可替代性：GPU也可以提供高吞吐量，且支持更大的设备内存（高达32 GB），并且更容易编程，已经成为一个强大的加速器替代方案。
3. 可编程性差：设计高效的FPGA要求开发人员具有全堆栈技能，从高级算法设计到低级电路实现。

新技术的发展开始利好FPGA

1. 新的接口技术：如OpenCAPI、加速器缓存相干互连（CCIX）]和计算快速链路（CXL），接口技术发展快可以提高加速器的接口带宽。
2. 新接口给FPGA带来的另一个特性是共享内存。FPGAs不作为IO设备连接到CPU上，FPGA和CPU共享相同的内存空间。
3. 一些FPGA现在包含了高带宽内存（HBM），并具有更大的本地内存容量以及更高的（本地）内存带宽。与带有HBM的GPU类似，这种大容量的高带宽内存允许FPGA在本地存储大量数据，从而减少主机内存的访问量，可以加速一些需要内存多次访问的数据密集型应用程序。
4. FPGA开发工具链也在不断改进：
5. HLS工具： Vivado HLS，OpenCL，HLS是高层综合（High level Synthesis），是将C或者c++语言编译为FPGA能够读懂和运行的RTL级别的语言，会自动生成硬件电路；
6. SNAP 框架：为开发人员自动化了CPU-FPGA界面的设计；
7. 编译器：Glacier，可以将SQL查询直接编译为FPGA实现。

2 FPGA背景

2.1 FPGA结构

如下图所示，一块 FPGA 芯片由可配置逻辑模块（CLB）、互连结构和本地内存构成，每个 CLB 都包含特定的结构，如：查找表（LUT）、多路复用器、进位链、触发器等。

每个LUT是一个n个输入和一个输出的表，根据n个输入的组合产生一个期望的输出。多个LUT可以通过可配置的互连结构连接在一起，形成一个更复杂的模块。LUT如下图：

除此之外，一块 FPGA 卡上还有 BRAM（Block RAM）来作为本地存储器，存储中间结果的寄存器。最近，FPGA芯片配备了更强大的资源，如内置的CPU核、数字信号处理器（DSP）块、UltraRAM（URAM）、高带宽内存（HBM）、预配置的I/O块和内存接口控制器。

2.2 FPGA的特点

1. FPGA是一种可编程的设备，可以配置为一个定制的电路来执行特定的任务。
2. 流水线并行和数据并行（延迟低，流处理）（而 GPU 只有数据并行）
3. CPU、GPU 都属于冯·诺依曼结构，指令译码执行、共享内存。FPGA 之所以比 CPU 甚至 GPU 能效高，本质上是无指令、无需共享内存的体系结构带来的福利。
   2.3 FPGA的带宽
4. 与CPU内存层次结构类似，FPGA内部内存（Internal）具有最低的延迟和最高的带宽，但容量最小。
5. on-board DRAM（动态随机存取存储器）设备可以提供数十GB/s的带宽，HBM有数百GB/s的带宽，两者都需要数十到几百纳秒的延迟来获取数据。
6. 访问主机（host）内存的带宽是最低的带宽，但提供了最大的内存容量。
   

2.3 FPGA的编程

FPGA中的用户定义逻辑通常是使用硬件描述语言（HDL）进行编程：VHDL or Verilog。HDL是电子系统硬件行为描述、结构描述、数据流描述的语言。利用这种语言，数字电路系统的设计可以从顶层到底层（从抽象到具体）逐层描述自己的设计思想，用一系列分层次的模块来表示极其复杂的数字系统。然后，利用电子设计自动化（ EDA ）工具，逐层进行仿真验证，再把其中需要变为实际电路的模块组合，经过自动综合工具转换到门级电路网表。接下去，再用专用集成电路 ASIC 或现场可编程门阵列 FPGA 自动布局布线工具，把网表转换为要实现的具体电路布线结构。

3 基于FPGA的数据库系统

标题3.1 FPGA作为带宽放大器

• 在基于存储和延迟敏感的数据库系统中，瓶颈通常来自于存储的数据传输，特别是硬盘（HDD）。与DRAM支持的数百个Gbit/s带宽相比，HDD设备的数据速率保持在1 Gbit/s水平，这限制了系统的性能。在这些系统中，FPGA可以用来放大存储带宽。
• 如图1所示，FPGA用作数据源（磁盘、网络等）和CPU之间的解压和滤波器来提高有效带宽。在这种体系结构中，压缩数据存储在磁盘上，并将直接通过SCSI、SATA、光纤通道或NVMe等接口传输到FPGA，或者间接用于网络附加存储或以太网上的NVMe或协议。
• 在FPGA中，根据某些特定的条件对数据进行解压缩和滤波，然后将数据发送到CPU进行进一步的计算。由于压缩后的数据小于原始数据，需要从存储传输的数据较少，间接提高了有效存储带宽。
  

3.2 FPGA作为IO连接加速器

对于计算密集型数据库，cpu是其瓶颈。计算密集型任务的例子包括连接、排序、分组和聚合、压缩等。这类任务一般是 FPGA被用作IO设备，CPU 把任务卸载（offload）给 FPGA 去执行。

• 图2说明了使用FPGA作为IO连接加速器的体系结构。在这种体系结构中，FPGA通过PCIe等总线连接到CPU，而FPGA和CPU都有自己的内存空间。

• 当FPGA从CPU接收到任务时，它首先将数据从主机内存（host memory）复制到设备内存（device memory）中。然后，FPGA从内存中获取数据，并在处理完数据后将结果写回设备内存，最后将结果复制回主机内存中。
  

• 缺点：需要反复的复制（从主机内存到设备内存），这会导致更长的处理延迟。

3.3 FPGA作为协同处理器

FPGA可以直接访问主机内存，CPU和FPGA之间的通信是通过共享内存来实现的。

5 技术趋势

5.1 数据库系统趋势

传统数据库的操作都在纯CPU上进行，计算压力大====>需要更强大的处理器，GPU或者FPGA

• 传统数据库由HDD存储转为内存或NVM存储，需要更大带宽，但FPGA-CPU互连带宽较低，加速困难；使用FPGAs作为io连接的加速器复制数据的成本很高====>加速FPGA需要克服这些限制。

5.2 系统互连趋势

5.2.1 增加系统互连带宽来解决带宽问题

• 为解决带宽问题：DRAM、PCIe、网络和存储的带宽都在逐年增加
  

5.2.2 使用共享内存和一致性解决IO连接瓶颈

• 仅仅增加带宽并不能解决我们所有的问题，因为传统的IO连接模型是瓶颈，这迫使业界推动跨CPU核和连接设备之间的一致性和共享内存。
• 使用共享内存，系统允许FPGAs从主机内存中读取一小部分数据，而无需将整个数据块复制到设备内存。

FPGAs使用高带宽和低延迟的互连进行连接，并且由于共享内存编程模型而易于编程，这使得FPGAs在数据库加速方面再次具有吸引力。

5.3 使用HBM（高带宽内存）来提高带宽和内存

DRAM带宽改善有限===>新的高带宽内存技术HBM提供了更多的带宽和更低的功耗，这使得FPGA也适用于数据密集型的工作。

6 查询操作符的加速

尽管还没有一个商业的FPGA加速内存数据库，但大量关于加速数据库操作符或组件的工作正在推动这个方向的进展。FPGA能够加速一些数据库操作符，如解压、聚合、算术、排序、连接等。

6.1 解压缩算法

解压缩算法广泛应用于数据库中，以节省存储和减少带宽。解压缩器读取由tokens组成的压缩流，将tokens转换为数据，并输出解压缩流。

• 在数据库系统中，最流行的两种类型的无损压缩算法是运行长度编码（RLE）和Lempel-Ziv（LZ）系列。
• 基于FPGA的解压缩算法实现可以帮助实现高吞吐量。

6.2 排序

排序是数据库系统中用于对记录进行排序的一种常用操作。它可以在SQL中和更复杂的查询中使用，以提高性能。大规模排序性能是衡量数据库性能的关键指标。传统的基于cpu的排序算法，不仅算法速度较慢，且抢占cpu系统资源。近年提出了很多基于FPGA的排序算法或系统，充分利用FPGA的并行处理能力，极大的提升算法的速度，解决了传统的基于cpu的排序算法的缺点。

6.2.1 排序网络

• 排序网络是一种高吞吐量的并行排序，可以同时对N个输入进行排序。比较和交换单元是排序网络中的核心元素。比较和交换单元比较两个输入，并将它们排列成选定的顺序（升序或降序），如果它们不按照期望的顺序排列，则通过交换它们来保证。使用一组这些比较和交换单元，并按特定的顺序排列它们，我们可以按照所需的顺序对多个输入进行排序。
• 排序网络可以通过将不同的数据集保存在不同的阶段，同时对多个数据集进行排序。N个输入排序网络能够每FPGA周期处理N个元素。

6.2.2 FIFO归并排序器

FIFO合并排序器可以将两个预先排序好的数据流进行合并，如图7(a)。FIFO合并排序器的缺点是从小数据流合并到最终排序流需要多次经过合并，数据需要在内存和FPGA之间移动多次，数据传输开销大。
这个问题可以通过级联多个FIFO合并排序器来解决。如图7b所示，FIFO较小的FIFO在早期放置，而较大的FIFO在后期插入。

6.2.3 归并树

归并树可以在一次将几个排序的流合并。

上述所有三种排序方法都可以通过制造更强的引擎或部署更多的引擎来充分利用接口带宽。但是，大的排序可能需要多次传递，每次传递都需要访问主机内存。通过这种方式，整个排序的总体吞吐量取决于通过次数和每个通过的吞吐量，或者总体吞吐量不超过带宽除以通过次数的带宽。通过更广泛的合并，合并更多的流，可以减少通过的数量。但是，由于每个输入流都需要缓冲，因此构建一个更广泛的合并树需要大量的分支，这使得设计分支受到了限制。

6.3 join（连接）

连接是数据库系统中常用的一种操作，它在特定的约束下将两个或多个表组合成一个复合表。最常见的一个是等连接，它通过一个公共字段组合两个表。在本文的其余部分中，我们将等式连接称为连接。有许多不同的连接算法，包括嵌套循环连接、哈希连接（HJ）和排序-合并连接（SMJ）。在本文中，我们主要关注HJ和SMJ，因为它们的算法复杂度较低，因此对数据库社区更感兴趣

6.3.1 哈希连接

哈希连接是一种用于关系型数据库中的连接算法，只能用于有等连接条件的连接中（on a.b = c.b）。它通常比嵌套循环算法更高效（探测端非常非常小除外），尤其是在没有命中索引的情况下。
简单来说，哈希连接算法就是先把一张小表加载到内存哈希表里，然后遍历大表的数据，逐行去哈希表中匹配符合条件的数据，返回到客户端。

在cpu中，哈希函数很难同时具有很强的鲁棒性和高速性。在FPGA允许在一个电路中实现复杂的代数函数，计算速度比CPU快。
分区哈希连接可以通过将数据划分为小的分区来避免随机访问，这样每个分区的哈希表就可以存储在FPGA内存中。
设计一个基于FPGA的哈希连接算法的关键之一是有一个有效的哈希表结构。一方面，哈希表结构会影响哈希连接引擎的性能。不适当的散列表设计可能会导致停顿，从而降低吞吐量。另一方面，由于FPGA内部有有限数量的分支，为了确保多引擎实例在一个FPGA中可行，哈希表不应该消耗太多的分支。

6.3.2 排序归并连接

• 排序合并连接 (Sort Merge Join)是一种两个表在做连接时用排序操作(Sort)和合并操作(Merge)来得到连接结果集的连接方法。
• 通常情况下，排序合并连接的执行效率远不如哈希连接，但前者的使用范围更广，因为哈希连接只能用于等值连接条件，而排序合并连接还能用于其他连接条件(如<,<=,>.>=)
• Sort Merge主要的开销在于对两表连接的排序，已经在连接关联列上已经进行了排序，则该连接操作就不需要再进行 sort 操作，这样可以大大提高这种连接操作的连接速度，特别是对于较大的表。
• 研究进展：Ren等人[20]提出了一个异构CPU-FPGA平台中的排序连接方法。在FPGA中执行前几个排序，并将部分结果流到cpu，进行合并连接。其他人则研究哈希连接和排序-合并连接之间的比较，在CPU中的对比研究较多，FPGA中的对比研究较少。

7 未来研究方向

7.1 数据库结构

内存中的数据库应该被设计为支持多种类型的计算元素（CPU、GPU、FPGA）的结构。

7.2 加速器设计

• 对于几个关键操作符，基于FPGA的加速做的很多。但同时利用CPU和FPGA，以及CPU、FPGA和GPU的组合的设计上所做的工作较少。
• 给FPGA带来的另一个机会是数据库开始支持新兴的机器学习。一些数据库集成了对查询优化的机器学习方法。这所需的大量计算都给数据库系统带来了计算挑战，而FPGA可能会有所帮助。因此，针对这些新兴的方法新加速器值得研究。
• 从系统的角度来看，单个FPGA只能提供有限的性能，而多FPGA架构应该会带来显著的加速。一方面，可以在不同的FPGA中实现不同的功能，来实现更多的功能和更复杂的工作。另一方面，多个FPGA可以一起工作，以提高性能。
• 使用FPGAs作为云资源可以进一步提高云和分布式数据库系统中的FPGA利用率。与此相关的重要挑战包括如何将FPGA与cpu连接起来，以及如何分配工作负载。

7.3 与GPU的比较

• GPU现在已经成为数据库系统的一个重要加速器，因为GPU有数千到数万个线程，能够提供高吞吐量。除了高并行性，集成HBM使其拥有大容量内存和快速访问。虽然FPGA现在也集成了HBM，但FPGA通常不能提供和GPU相同数量级的线程。
• 什么类型的数据库应用程序在FPGA上比GPU工作得更好：
  • 第一个可能是对延迟敏感的流媒体处理应用程序，如网络处理。流处理中高吞吐量和低延迟的要求给GPU带来了挑战。由于GPU需要格式化良好的数据，并以批处理方法来处理数据以获得吞吐量，格式化可能会引入额外的延迟。然而FPGA的数据流设计的特性可以完美的满足要求。
  • FPGA可能在需要特殊功能的特定领域，在吞吐量方面击败GPU。例如，如果希望构建在加密层下运行的数据库，需要将加密与其他操作符相结合。FPGAs可以在硬件中有效地实现这些特殊功能，而通过在管道中组合两个功能组件，其对吞吐量的影响通常可以忽略不计。

• 我们还可以考虑探索使用CPU-GPU-FPGA组合来构建更多异构性的数据库系统。不同的处理器有不同的特性和不同的优点。cpu擅长于复杂的控制和任务调度，GPU擅长在大量数据量的并行性批处理模式下工作，而FPGAs可以通过数据流和管道设计提供高吞吐量和低延迟。将这些处理器集成在一个系统中，并将工作负载分配给最适合的处理器，很可能会带来优势。然而，构建这个系统需要解决一些挑战，包括如何将任务划分为软件和硬件，如何管理系统中的计算资源，以及如何支持不同类型的处理器之间的数据一致性。

参考文献

In-memory database acceleration on FPGAs: a survey
FPGA: What’s in it for a Database?