FPGA 是实现绿色搜索技术的关键

　　FPGA 在加速 Web 搜索及类似信息检索等常见数据中心工作任务方面拥有巨大的潜力，因为它具备固有的并行处理与低功耗优势。充分认识到这一潜力的奥地利公司 Matrixware 购买了 FPGA 平台，但缺乏自身实施复杂信息检索应用的技术，因而公司聘请了我们联合格拉斯哥大学 (University of Glasgow) 计算机系组建的团队开发 FPGA 加速型专利搜索解决方案的概念验证方案。该团队成员包括三名设计人员和兼职助理研究员 STelios Papanastasious，他们在信息检索、FPGA 以及系统开发领域积累了丰富的专业知识，形成了一个开发原型应用所不可或缺的技能娴熟的组合。经讨论，大家一致同意采用 FPGA 加速型后端进行实时专利过滤应用的开发。

　　项目资源在人力和时间方面受到很大制约。因此，采用 HDL 实施过滤算法不可行，因而我们决定采用瑞典公司 MitriONics 开发的高级编程解决方案。

　　原型应用在去年 11 月于奥地利维也纳举行的信息检索设施研讨会 (Information Retrieval Facility Symposium) 上引起了专利研究人员的极大兴趣。处理数以百万份的专利通常需要几分钟，但若采用 FPGA 加速型后端，几秒钟就能反馈结果。

　　我们在 2009 年 7 月举行的 ACM SIGIR 国际信息检索研究暨开发大会 (ACM SIGIR International Conference on Information Retrieval Research and Development) 上发布了结果，介绍了相关的性能提升情况，并在 FPL 2009 国际现场可编程逻辑大会上对架构设计进行了详细阐述。

　　文档过滤的输入与输出

　　通常情况下，信息过滤任务是指检查传送进来的文档是否与一系列既定的需求信息或配置文件相匹配。这种任务可在多种情况下出于多种原因而进行，例如，检测传送进入的电子邮件是不是垃圾邮件，比较专利申请是否与现有专利发生重叠，监控是否存在恐怖活动通信，监测并跟踪新闻报道，等等。面对大量涌入的文档，处理工作必须实时完成，从而确保时效性成为重中之重。鉴于此，我们的目标就是采用 FPGA 来实施完成计算强度最大的过滤应用，从而在节约时间和降低能耗的情况下提高文档过滤的效率。

　　在本文中，我们将采用 Lavrenko 和 Croft 提出的相关性模型。这一理念适用于信息过滤任务，可通过生成概率语言模型确定传入文档是否与主题配置文件存在差异。如果文档得分超过用户定义的阈值，那么就视为与主题配置文件相关。

　　在 FPGA 上实施的算法表达如下：文档可以建模为一个“词袋”，即由(t,f )对组成的 D 集，其中 f=n(t,d)，t 表示 t 这个词在文档 d 中出现的次数。配置文件 M 为一组对 p=(t,w)，这里的 w 加权为：

　　给定文档对于给定配置文件的得分计算为：

　　这里，T 是指在 D 和 M 中都出现的词。该函数是大多数过滤算法的代表性内核算法，不同算法的主要区别在于配置文件中词的加权。

　　应用架构

　　文档过滤应用采用客户端—服务器架构，其构成形式为将基于 GUI 的客户端通过 TCP/IP 连接到通信服务器，该服务器可作为不同后端服务器和客户端之间的代理（参见图 1）。在典型的使用案例中，用户首先向查询服务器发出请求，常规搜索系统会返回选中排序列表。用户随后通过从该表中选择相关文档创建配置文件。接下来，配置文件服务器使用所有合并文档的完整文本构建配置文件（即词和加权列表）。配置文件服务器将该配置文件与完整的文档集合进行匹配，并向客户端返回分数流。

　　模块化的客户端—服务器架构有助于建立系统基准，因为我们可以在主机 CPU 上方便地添加配置文件服务器的 C++ 参考实施。如图 1 所示，应用由 FPGA 加速的部分受限于计算强度最大的任务，也就是文档与配置文件的匹配。主机系统则负责处理所有其他的任务（参见图 2）。

图 1 —— 系统架构以可作为客户端与后端服务器之间代理的通信服务器为中心。

　　配置文件服务器根据从客户端获得的配置文件过滤一系列文档，并返回分数流。为了*估性能，我们同时创建了 C++ 参考实施和 FPGA 加速实施方案。两种版本的实施方案基本功能相同，都能通过 TCP/IP 接口接收构成配置文件的文档列表，用相关性模型构建配置文件，并根据该配置文件对存储器缓冲的文档进行*分，从而通过 TCP/IP 向客户端返回文档分数流。可在存储器中缓冲文档流，否则会由于缓慢的磁盘存取影响应用的性能。

　　我们在具有两个 RC100 刀片的 SGI Altix 4700 设备上实施该应用，其中的每个刀片都包含两个运行频率为 100 MHz 的赛灵思 Virtex?-4 LX200 FPGA；每个 FPGA 都通过 SGI NUMAlink 高速I/O 接口连接到主机平台，并能通过最高速度为每秒 16GB 的 128 位数据总线存取本地 64MB 的SRAM 存储库。主机系统是一套 80 个内核的 64 位 NUMA 设备，运行性能为 64 位 Linux (OpenSuSE)。处理器为双核 Itanium-2，运行频率为 1.6 GHz，其中每个处理器都能直接存取 4GB 的存储器，而且能通过 NUMAlink 存取完整的 320GB 存储器空间。值得注意的是，Itanium 处理器功耗约为 130 瓦特 ，而每个 Virtex-4 FPGA 的功耗仅约 1.25 W 。

图 2 —— 在 FPGA 子系统架构中，Virtex-4 器件通过 SGI 的 NUMAlink 接口与主机平台连接。

　　对于 C++ 语言应用而言，我们实施 Lemur 信息检索 (IR) 框架，对于与 FPGA 应用的交互，我们则使用 SGI 可配置专用计算 (RASC) 库。Lemur Toolkit是一套开源工具集，专为 IR 研究而精心设计，可支持索引以及多种相关性和检索模型。RASC 库是 SGI的专有解决方案，能够通过高性能 NUMAlink 互连机制将 FPGA 与主机系统相集成。RASC 库定义的硬件抽象 API 可控制系统中的所有硬件元素。

　　我们用 Mitrionics 软件开发工具套件 (SDK) 将特定域的 Mitrion-C 语言转换为 VHDL。生成的VHDL 现在能够方便地指向 FPGA 器件架构。我们采用带 XST 合成工具的赛灵思 ISE? 工具链来创建 Virtex-4 比特流。

　　高级 FPGA 编程

　　Mitrionics SDK 可提供 Mitrion-C 作为高级语言，专用于满足在 FPGA 上快速开发应用之需。不过，作为后缀的 C 有些误导作用。尽管这种语言采用了 C 风格的语法，但实际上是一种遵循函数编程风格的单赋值数据流语言。Mitrion-C 原生支持广泛（矢量）而深入（管道）的并行功能，因而非常适用于处理数据流的算法，例如过滤以及其他众多类型的文本和数据挖掘算法等。

　　Mitrion-C 还提供了一种流数据类型，可配合 foreach looping 构造实现流水线操作；此外，还提供矢量数据类型以支持数据并行工作，以及支持顺序列表的列表数据类型。具体而言，用户可过滤foreach loop 的流输出，生成较小的流，如以下 Mitrion-C 代码示例所示。此外，程序人员还能用元组结构 (tuple construct) 创建功能强大的数据类型。最后还有一个需要指出的特性是，该语言能支持可变宽度整数和浮点数。

　　为了在 FPGA 上高效实施*分操作，我们必须解决的关键问题是高效查询配置文件以及文档流的高效 I/O 流。

　　对于文档中的每个词，应用都要查询配置文件中相应的词并获得词加权 (term weight)。由于大多数查询都找不到结果（即大多数文档的大多数词不会出现在配置文件中），因此必须首先丢弃否定词。鉴于此，我们在 FPGA Block RAM 中采用了 Bloom 过滤器 [9]。BRAM 的内部带宽越高，拒绝否定词的结果就越快。由于需要查询，因此配置文件必须作为某种散列函数进行实施。不过，由于配置文件的大小不能提前知道，因而我们不可能构建出完美的散列函数。不完美的散列函数会出现冲突问题，进而降低性能。

　　为了解决这一问题，我们采用了分档方案，即将外部 SRAM 分区为 bin，每个 bin 都可包含固定数量的配置文件词。Bin 的大小决定了可处理的冲突数。如需给 bin 分配配置文件词，只需将词 ID 的较下部分作为存储器地址，从而避免了实际的散列操作。

　　让 SRAM 存储器容量设定为 NM 配置文件词。词 ID 是一个无符号的整数，其范围取决于词汇量，就我们的例子而言约为 400 万个词，需要 24 位。词加权为 8.32 定点数，因而配置文件词需要 64 位。RC100 上的 SRAM 包括 4 个 16 MB 存储库，因此 NM=223。Bins 的数量 nb=NM/b 和 bin 地址用词 ID“t”进行计算，即 (t&(nb-1)).b。

　　Bin 的占用概率 x 由组合决定，置换决定 bin 的数量 nb 和描述词的数量 np。这样，我们就能计算 bin 溢出的概率就是 bin 大小的函数（即 bin 的数量），即 NM=b.nb。bin 尺寸越大，查询就越慢，但是，由于 SRAM 存储库包括 4 个独立的 64 位可寻址双端口 SRAM，我们实际上可以并行查询四个配置文件词。因此，相对性能会降低 1/ceil(b/4)。我们的分析结果显示，即便对最大型的配置文件来说（16K，我们研究所用的最大配置文件为 12K，不过通常配置文件比这都要小得多），b=4时（最佳性能），bin 溢出概率为 10-9。换言之，描述词被丢弃的概率不到 10 亿分之一。应注意的是，由于我们假定词汇量无限大，因而这一估算还是保守数字。

图 3 —— 过滤应用的 FPGA 实施示意图

　　通过将文档表述为“词袋”，文档流就是文档 ID、文档词对组 (document term pair set) 等对列表。从物理上说，FPGA 以每秒 1.6 GB 的速度从 NUMAlin 接受 128 位字流。因此，文档流必须在字流上编码。可将文档词对 di =(ti,fi) 编码为 32 位：24 位用于词 ID（支持 1,600 万个词的词汇库），8 位用于词的频率。这样，我们就能将 4 个对组合到 128 位字中。要标示文档的起点与终点，我们需要插入包含文档 ID（64 位）和标志符（64 位）的报头与脚注字 (footer word)。

　　如上所述采用查询表架构和文档流格式，实际的查询和*分系统（图 3）会非常直接。我们只需扫描输入流以检查报头和脚注字即可。报头字将文档得分设为 0，而脚注字则收集并输出文档得分。对于文档中的每四个配置文件词，Bloom 过滤器首先丢弃否定词结果，再从 SRAM 读取四个配置文件词。并行计算并添加（图 4）每个词的得分。实际上，四分之三的配置文件词 ID 不会匹配于文档词 ID；只对第四个进行实际计算。将文档中所有词的得分进行累加，最后得分流在输出到主机存储器之前与限值进行比较过滤。

　　主机—FPGA 接口将文档流从存储器缓冲器中传输至 FPGA，并将得分流返回至客户端中。一旦从客户端接收到配置文档 ID 表，子进程即从主进程中分叉出来，以构建实际的配置文件，将其载入 SRAM 并在 FPGA 上运行算法。每个子进程都会产生一个独立的输出线程，以对从 FPGA 获得的得分进行缓冲，并通过 TCP/IP 将这些得分传输到客户端，从而使用网络对得分流进行多路复用。若没有该线程，网络吞吐量的波动就会降低系统性能。这种主机接口架构的主要优势在于，它具有很高的可扩展性，能轻松满足大量 FPGA 的需求。

　　大幅度提速

　　为了*估 FPGA 加速型过滤应用的性能，我们进行了一系列实验，将基于 FPGA 的实施方案与采用 C++ 编写的运行于 Altix 之上的优化参考实施方案进行了比较。在比较过程中，我们使用了三个 IR 测试集合（参见表 1）：一个是文本检索会议 (TREC) 提供的基准参考集合 TREC Aquaint，还有两个分别是美国专利与商标署 (USPTO) 和欧洲专利署 (EPO) 提供的专利集合。我们选择上述测试集合来*估不同文档长度和大小对过滤时间的影响。

　　为了仿真众多不同的过滤器，我们通过选择随机文档并用标题作为请求，随后再选择请求服务器返回的固定数量的文档作为伪相关文档，来为每个测试集合构建配置文件。我们接下来使用返回的文档构建相关性模型，该模型定义了文档集合中每个文档应当匹配（就好像从网络进行流处理一样）的配置文件。配置文件中的文档数量从 1 到 50 不等，可确定增加配置文件的大小（词数和文档数）会对性能有何影响。我们将上述进程重复 30 次，并计算平均处理时间。

图4 ——相关性模型

　　我们在表 2 和图 5 中对有关结果进行了总结。从表中可以清晰地看出，FPGA 实施方案在速度方面通常比标准实施方案快一个数量级。从图中可以看出，配置文件大小（需要匹配的词数）增加后，标准实施方案变得越来越慢，而 FPGA 实施方案的速度相对保持不变。这是因为 FPGA 实施方案支持配置文件*分的流分线操作，这样无论配置文件大小如何，时延基本保持不变。

　　这些结果清晰表明，FPGA 对加速 IR 任务有着巨大的潜力。FPGA 的提速幅度已然相当大（特别对大型配置文件而言尤其明显），而且仍有进一步提高的空间。通过仿真，我们确认 FPGA 算法给一个文档词*分需要两个时钟周期。制约因素为每周期 128 位的 SRAM 存取速度，这需要两个周期才能读取四个配置文件词。如果时钟速度为 100 MHz，则意味着 FPGA 能在 15 秒之内完成整个 EPO 文档集合的*分。当前应用在四个 FPGA 上需要约 8.5 秒，因此原则上我们至少可以让性能再翻一番。

　　差异的原因在于 I/O 流 (streaming I/O)：通过主机操作系统设备驱动器可将文档流从用户存储器空间传输至 NUMAlink，这需要直接存储器存取 (DMA) 传输。驱动器可传输流的缓存模块。目前，对所传输模块的大小来说，这一传输并不是以最优的方式实施的，进而导致无法达到最高吞吐量。此外，用独立的线程进行传输排序也能避免传输时延。

　　遇到的问题和吸取的经验

　　这一项目的意义不仅在于它展示了 FPGA 作为信息检索任务加速器的优势，而且还为我们提供了 FPGA 加速系统软硬件要求的重要信息。

　　至主机系统的 I/O 是确保性能的关键：NUMA 存储器与 FPGA 之间的 DMA 机制必须获得 Mitrionics SDK 和 SGI RASClib 的支持。在此前的项目中，我们必须先将数据传输到电路板上的 SRAM 中才能进行处理，但这会严重影响性能，因为数据的载入和结果的卸载会造成非常大的开销。此外，我们也清晰地认识到，IR 任务尤其需要大量的片上和板上存储器，才能实现效率最大化。

　　此外，为了充分使用 FPGA，未来的平台必须具备两个重要特性，一是必需能在 FPGA 之间直接传输数据，二是必需能够关闭主机处理器（或用一个主机处理器控制多个 FPGA）。关闭主机处理器的功能尤其重要：在 Altix 平台上，即便 Itanium 处理器完全处于空闲状态也不能关闭。但是，空闲的 Itanium 处理器的功耗也高达工作状态下所需功耗的 90%。因此，尽管 FPGA 加速的节能效果明显，但我们目前的系统即便在加速器运行过程中主机存储器空闲状态下，其总体节能作用仍然有限。

　　开发 FPGA 加速型系统的另一重要领域就是软件。我们的经验明确反映出，主要的复杂问题在于FPGA 和主机系统之间的接口连接：Mitrion-C 中的实际 FPGA 应用开发效率非常高；采用 Lemur 工具套件构建查询和服务文档的框架也相对容易开发。但是，采用 RASClib 开发连接主机应用和FPGA 接口的代码非常复杂，而且由于并发性问题，还非常难以调试。因而，接口代码的开发占据了绝大部分的开发时间。

图 5 —— 时间（秒）和配置文件中文档数量的对比图

　　FPGA 高级编程的最后一个问题是编译速度。习惯于 C++ 或 Java 等语言的开发人员认为即便应用非常复杂，构建时间也应该比较短。除了最基本的设计之外，当前的 FPGA 工具执行综合以及放置路由工作几乎都需要一整天的时间。非常长的构建时间会严重影响工作效率，因而时间应当缩短到一般性软件构建时间，这样才能使 FPGA 加速更具吸引力。

　　定制硬件平台

　　我们用这个项目探讨了 FPGA 加速的可能性，并展示了 FPGA 作为数据中心绿色环保技术的巨大潜力。我们希望进一步扩展这项研究，调查文档处理所需的全系列工作任务，如语法分析、词干、索引、搜索以及过滤等。我们清楚地认识到，现有系统在节能潜力方面很有限，我们希望研究能以业界最高效率专门执行信息检索任务的可定制硬件平台。这样，我们就能显著加速算法的执行，同时大幅度降低能耗，从而开发出更加环保、速度更快的数据中心。