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

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

我们在具有两个 RC100 刀片的 SGI Altix 4700 设备上实施该应用，其中的每个刀片都包含两个运行频率为 100 MHz 的赛灵思 Virtex®-4 LX200FPGA；每个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 瓦特 [7]，而每个 Virtex-4 FPGA 的功耗仅约 1.25 W [8]。

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

对于 C++ 语言应用而言，我们实施 Lemur 信息检索 (IR) 框架，对于与 FPGA 应用的交互，我们则使用 SGI 可配置专用计算 (RASC) 库。Lemur Toolkit（详情访问 www.lemurproject.org）是一套开源工具集，专为 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)。