From Research to Proof-of-Concept: Analysis of a Deployment of FPGAs on a Commercial Search Engine

作者：Maschi Fabio; Alonso Gustavo; Hock-Koon Anthony; Bondoux Nicolas; Roy Teddy; Boudia Mourad; Casalino Matteo

@ ETH Zurich

本文解决了如何以经济高效的方式将 FPGA 集成到实际应用场景中，并保持其在算法方面的性能优势。

FPGA在性能、架构、能耗等方面有很多优势，但是利用FPGA为现有的应用提供所有的优势并不简单。很少有研究来分析 FPGA 该如何部署、需要做什么改进才能使其在实践中具有成本效益，也很少有人分析在实际计算系统中应用 FPGA 的效率。

本文报告了将研究理念转化到实际场景后，对产生的性能和可能部署的估计成本进行了评估。

---

该论文解决了什么难点，难点存在的原因是什么，作者是如何发现这些难点的？

本论文主要报告了以下难点，并进行了讨论：

1. 模型的差异：需要将在学术上使用的简化模型转变成功能完备的组件，本文讨论了这些变化对整个系统设计的影响
2. 软件到硬件要考虑的选项：当一个设计模块从一个软件设计模块迁移到一个在 FPGA 上运行的组件时，有很多选项可以选择来将它集成到整体设计中。
3. FPGA的利用率：FPGA的性能的利用率可能比较低，导致整个系统的性能达不到峰值。
4. 成本问题：使用FPGA来部署云服务，系统的成本可能不降反升。本文对系统的成本进行了简单的估计和对比。

本文的背景：

Amadeus(一个提供路径规划解决方案的公司)需要为他们的航班搜索引擎(Flight Search Engine)提供加速。

• 航班搜索引擎（大问题背景）：给定一个查询（这里称为用户查询），查询中指定出发地、目的地和相应的日期，它会响应出发地和目的地之间的一些可能航班路线，航班路线中包含航班信息和价格。
• 功能模块（架构）

1. Domain Explorer：探索满足要求的所有可能的转机机场、航空公司和航班组合；预先选择一些潜在的路线。MCT(Minimum Connection Time)：最小转机时间模块，用于搜索的早期阶段，在搜索引擎的运行性能和总成本方面起着关键作用。
2. Route Selection：该使用一些策略（用Route Scorin作为标准）进一步减小可能购买的潜在路线集。
3. Pricing Engine：估计价格

• MCT模块（加速器）

如上图所示，根据每个航线提供的航班信息来决定机场的最小转机时间，这些信息被称为“规则”。（比如r2代表ZRH机场在2021年夏天的时候，去往国内且航站楼为T1的情况下，换乘时间为有很高的可能性为40分钟）。定义 MCT 的“规则”会一天修改一次，但是基本上变动比较小。现有的MCT模块中规则条数超过160万条。

本文的问题背景是，已经在研究中利用单独的FPGA对MCT模块进行了充分的加速。接下来需要将这个模块部署到服务器上，在实际的搜索引擎中，借此来讨论FPGA在部署到实际应用场景中导致的很多普遍性问题。其中讨论了三个最主要的指标：吞吐量、处理每个请求的时间和价格

---

针对以上难点，作者各做了哪些优化，优化背后的思想是什么？

现有的FPGA加速引擎：ERBIUM

1. 离线部分

• NFA(非确定有限状态自动机)优化器：在规则集上优化 NFA 形状（实际上是调整“规则”中选项的顺序）
• Constraint Generator 约束生成器：根据规则结构（即标准数量、数据类型、运算符）和 NFA 形状定制硬件内核。
• NFA 解析器：根据当前硬件设置和规则集构建 NFA 的内存文件。

2. 在线部分

• Host Executor（CPU）：将 NFA 数据加载到 FPGA 内部存储器中，以及发送 MCT 查询并获取其结果
• FPGA Kernel：加速器

理论与现实模型的差异

理论分析

实际应用场景的的规则结构引入了选项之间的相互依赖关系，以及不同的优先级权重等级等等新的因素。对于软件来说比较好更改，但是对于硬件来说可能会导致进一步的后果。主要的更改：

• Criteria Merging：将从前的按照顺序判断选项改为了用一个范围来判断。需要采用NFA解析器模块，生成的NFA随之增大，会增加内存使用，影响延迟；
• Precision weight for ranges：新版本的规则中，预测的精度与航班号范围相关，而航班号之间可能是有范围上重叠的。需要动态地去除选项之间的重叠范围，再次使用NFA解析器模块，通过解析生成无重叠的大量新规则。但是新的规则同样会使得NFA增大，影响延迟。
• Cross-matching criteria：请求中的某一个选项不一定只匹配同一个规则中的域。需重新建模且更改硬件kernel的逻辑。与前两种情况不同，这种变化通常不会导致延迟、内存要求以及更重要的精度权重结构发生任何重大变化。

综上所述，以上的很多问题都可以通过NFA解析器来解决，这是此系统设计的一个优点，就是不需要每次改动都改变FPGA的电路，以达到最高性能。证明了原有方案具备一定的通用性。

但以上的实际场景问题确实会导致NFA模型变大，延迟提高。除此之外，在实际场景中shell是阻塞处理，与之前设计中的流式处理不同，同样会影响性能。

实验验证

实验配置：用真实场景下(MCT V2)，测试一个kernel中采用1/2/4个引擎的条件下系统的吞吐量和单条指令处理时间，以及在原有的研究场景(MCT V1)下两项指标的结果。

现象：当Batchsize增大到1024之后时，我们观察到与原始设计相比有较为显著的性能损失（吞吐量差11%）。这可以看作是原型机和需要考虑所有极端情况的系统之间差异的说明。其主要原因是由于更大的NFA模型、从流式处理接口换成了阻塞式接口导致的。

讨论

在将系统的一部分移至 FPGA 时，如果没有合适的NFA生成器，新标准引起的每一个变化都需要对 FPGA 上的电路进行彻底的重新设计，由于开发成本高，这将使整个方法非常不切实际。这说明使用适当的工具并采用易于调整的灵活设计，开发成本的可以降低到最低限度。

舍弃最高性能，换取通用性和易于维护性，这在软件中很常见，但在许多基于 FPGA 的系统中仍然需要考虑这一点。 正如我们的用例所示，设计的实际可行性不仅取决于其性能，还取决于其扩展性和鲁棒性。 在实践中，所有组件的负载往往会随着时间的推移而增长。虽然在NFA生成器中会产生更大的 NFA，影响处理请求的效率，但是频率的影响可以通过使用更大的批量大小得到补偿。

作为吸取的教训，在考虑设计时，重要的是要考虑系统如何随着时间的推移进行灵活变化和修改，需要从头开始重新设计以适应变化的超优化设计不太可能在实际部署中获得回报。

软件到硬件：需要考虑的配置

理论分析

• Injector：输入
• Domain Explorer：类似于数据管理系统中的进程池。每个进程会会触发对一到五个 MCT 查询。
• ZeroMQ：通信。用于Domain Explorer进程和router之间的同步通信，以及router和多个MCT工作线程的异步通信。
• MCT Wrapper：用循环方式在不同的工作线程之间分发传入的 MCT 查询，以支持异步通信，从而确保wrapper始终准备好来处理新查询。
• Encoder：位于MCT Wrapper，在将 MCT 查询发送到加速器之前，必须对其进行编码。因为它将软件中使用的数据表示调整为更适合 FPGA 处理的格式。 不然FPGA 上的设计会陷入处理复杂数据类型的开销中。
• XRT：处理工作线程与 FPGA 内核之间的通信。 它调度数据移动和请求的执行。
• FPGA：加速器本体。在FPGA上有多种可能的组合来充分利用计算资源。 例如，可以有一个带有四个并行引擎的内核； 或两个内核，每个内核有两个并行引擎。 第一种被调整为尽可能快地处理一批查询（从而改善延迟），第二个设置优先考虑两批查询的并行执行（从而提高吞吐量）。

实验探究

我们首先对最基本的场景进行性能评估，其中每个并行元素都减少为一个。可以看出：

• 小批量（最多 4,096 个 MCT 查询）的实际处理时间主要由数据移动开销决定。
• 大批量中编码器施加了线性增长且非常长的执行时间，甚至比 FPGA 内核的实际 MCT 查询处理时间还要长。

说明：FPGA 本身的延迟的实际贡献可能不是整个系统中的最大问题，从而消除了提出最优化设计的一些压力。

图七：固定进程和工作线程数量，测量单个内核在改变其内部的引擎数量情况下的吞吐量增益。

结果显示，虽然吞吐量呈现明显的增长，但是由于电路复杂度随着引擎数量的增加而增加，导致工作频率降低 30%。

图8：固定每个内核的引擎数量，改变内核数量的性能。每个内核都有自己的一个进程和一个工作进程作为输入。

实验结果跟上面差不多，但是和改变引擎数量对比（图7），增加内核数量的方案吞吐量要更高。

图9：在内核数量和引擎数不变的情况下，改变主机端到FPGA数据流的并行度。

左面的图显示这样的配置能够最大化全局吞吐量，可以达到每秒 4000 万次 MCT 查询。 另一方面，右边的图展示了单个请求的效率降低了，说明XRT调度器的同步开销会根据线程数量的增加而增加。

图10：探讨对MCT线程施加压力。

使用多个进程调度单一worker，可以看到单个 worker 不会被单个进程饱和，当耦合到多个进程时可以提供更大的吞吐量。当到达16个进程的时候达到饱和，不再能够提供更大的吞吐量。

讨论

在搜索引擎的每个组件上要实例化多少并行元素，不仅必须考虑并行处理元素引入的吞吐量的直接增益，还要考虑会对查询的响应时间造成多大的影响。

图 11 展示了这两个维度之间的折中。对于给定的最小吞吐量，例如每秒 2000 万次查询，可以确定具有【4进程 4线程 1kernel 4引擎】 的配置将施加最短的执行时间v；但是，如果将最大执行时间固定在500 𝜇 𝑠，则具有 【2进程 2线程 1kernel 4引擎】 的配置是产生最佳吞吐量的配置。因此，参数配置是非常多变的。

从研究的角度来看，这些结果的一个重要提示是：整体性能不仅取决于 FPGA 设计，还取决于系统的外部元素。 上图显示了延迟和吞吐量方面的性能选项选择范围很大，有许多是由 FPGA 周围的系统决定的（比如进程数、线程数），而不是由 FPGA 本身的设计决定的。 结合第一部分的讨论，这些结果证实了 FPGA 灵活性、易于维护性、扩展性以及它在系统其余部分中的集成度比起他的绝对性能来说更重要。

FPGA的利用率

理论分析

FPGA的利用率跟他的性能收益相关。事实上，与任何基于 PCIe 的设备相比，CPU 具有更大的灵活性和更少的通信开销。只有当MCT请求达到很大的量之后，FPGA相比于CPU才能有性能上的优异表现。这就需要我们考虑在实际场景中搜索引擎是否会给FPGA产生足够的请求。

搜索引擎的工作过程如下：航班搜索引擎先产生旅行解决方案 (TS)，再产生MCT请求。 在 MCT 调用之前，Domain Explorer会生成潜在 TS 的列表。 该列表首先按照内部启发式进行排序，然后按照顺序为非直航的 TS 调用 MCT 模块。为了探究是否有充足的请求，本文从实际场景中中收集了搜索引擎工作负载的快照。 其中大约 17% 的路径规划对应了直航，即不会生成 MCT 调用。而其他的每个请求会产生 1.24 个 MCT 查询。

实验探究

图 12 显示了 CPU 和 FPGA 的MCT 模块处理单个用户查询的执行时间与真实生成的 MCT 查询数量的关系。除此之外还绘制了执行用户查询所需的 FPGA 调用次数。 对于少于 400 个 MCT 查询的小工作负载，CPU 实现的执行时间更短，这是因为 PCIe 总线对 FPGA方案施加了重要的通信开销导致的。对于更大的工作负载，FPGA 的性能优于 CPU，即使是在同一个请求中多次调用MCT模块时。

讨论

考虑使用 FPGA 时，获得必要的性能是至关重要的。 比如：设计编码器是使 FPGA 发挥效果所必须的一步。 在这里，我们看到了另一个起到关键作用的方面：批量大小。 所有的实验结果都表明批量大小必须足够大才能使 FPGA 的性能超过CPU。 但是，批量大小由搜索引擎及其工作方式决定。在小批量的情况下，没有足够的工作负载来让FPGA充分利用，并且还会使得通信开销占主导地位。在短期内，负载不均匀会是不好改变的现实，这是因为通常情况下，并没有足够的 MCT 请求供FPGA处理。

成本问题

理论分析

目前的方案是将FPGA作为协处理器通过 PCIe 连接到 CPU 。 截至 2021 年 2 月，此设置是 AWS F1 和 Azure NP 系列中唯一可用的设置。下面对本地部署和云端部署两种方案进行了成本上的对比。

实验探究

表 2 简单估计了基于当前负载（需要 400 个服务器）和 FPGA 在最佳接管负载比例下成本的简化计算。 我们以每台 10K 的采购价格使用 400 台大型多核服务器作为基准。

本地方案中，新设计只有在使用较小的 FPGA 时才具有成本效益，这是因为因为我们不能充分利用 FPGA，使用性能好的FPGA也是一种浪费。本地在采用U50的时候，其价格能够低于只用服务器的版本。

但是在云中，现有的服务器配置对于提出的设计来说是不够的。 云上baseline分别采用AWS和Azure，其baseline分别用c5.12xlarge 和 F48s v2 实例，每个实例具有 48 个 vCPU 和 96 GiB 内存。 对比来看，在云上可用FPGA的 CPU 数量非常小，只有8个或10个CPU，假设 FPGA 承担了 40% 以上的负载，我们需要 1,464 个 f1.2xlarge 或 1,171 个 NP10s 实例才能处理当前负载。与纯 CPU 设计相比，其成本对应增加3倍或2.5倍。

讨论

云上成本问题的主要原因来自于 CPU 和 FPGA 之间的巨大不平衡。云上的CPU实例无法在 FPGA 上施加足够的负载，结果导致FPGA 部署成本过高。

在研究层面上，结果指出了考虑如何在 FPGA 上施加足够负载的重要性，尤其是在 PCIe 遇到了带宽瓶颈且无法使用流传输的情况下。

直接的一个想法是：使用FPGA 作为加速器的更好方法可能不是以协处理器的身份连接到 CPU 上，而是可直接从网络上进行访问。可以考虑更改搜索引擎，以远程使用FPGA模块。这是本文作者打算在未来同时使用 TCP/IP 通信和 RDMA探索的想法。

---

自己的思考

本文对FPGA部署在实际应用场景后存在的各种问题，包括性能、配置和开销上都做了详尽的探讨。