为了解决这一问题,我们采用了分档方案,即将外部SRAM分区为bin,每个bin都可包含固定数量的配置文件词。Bin的大小决定了可处理的冲突数。如需给bin分配配置文件词,只需将词ID的较下部分作为存储器地址,从而避免了实际的散列操作。 让SRAM存储器容量设定为NM配置文件词。词ID是一个无符号的整数,其范围取决于词汇量,就我们的例子而言约为 400 万个词,需要 24 位。词加权为 8.32 定点数,因而配置文件词需要64位。RC100上的SRAM包括4个16MB存储库,因此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亿分之一。应注意的是,由于我们假定词汇量无限大,因而这一估算还是保守数字。 通过将文档表述为“词袋”,文档流就是文档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;只对第四个进行实际计算。将文档中所有词的得分进行累加,最后得分流在输出到主机存储器之前与限值进行比较过滤。
图 3 —— 过滤应用的FPGA实施示意图
主机—FPGA接口将文档流从存储器缓冲器中传输至FPGA,并将得分流返回至客户端中。一旦从客户端接收到配置文档ID表,子进程即从主进程中分叉出来,以构建实际的配置文件,将其载入SRAM并在FPGA上运行算法。每个子进程都会产生一个独立的输出线程,以对从FPGA获得的得分进行缓冲,并通过TCP/IP将这些得分传输到客户端,从而使用网络对得分流进行多路复用。若没有该线程,网络吞吐量的波动就会降低系统性能。这种主机接口架构的主要优势在于,它具有很高的可扩展性,能轻松满足大量FPGA的需求。 |