FPGA 是實(shí)現綠色搜索技術(shù)的關(guān)鍵

配置文件服務(wù)器根據從客戶(hù)端獲得的配置文件過(guò)濾一系列文檔，并返回分數流。為了評估性能，我們同時(shí)創(chuàng )建了 C++ 參考實(shí)施和 FPGA 加速實(shí)施方案。兩種版本的實(shí)施方案基本功能相同，都能通過(guò) TCP/IP 接口接收構成配置文件的文檔列表，用相關(guān)性模型構建配置文件，并根據該配置文件對存儲器緩沖的文檔進(jìn)行評分，從而通過(guò) TCP/IP 向客戶(hù)端返回文檔分數流?？稍诖鎯ζ髦芯彌_文檔流，否則會(huì )由于緩慢的磁盤(pán)存取影響應用的性能。

我們在具有兩個(gè) RC100 刀片的 SGI Altix 4700 設備上實(shí)施該應用，其中的每個(gè)刀片都包含兩個(gè)運行頻率為 100 MHz 的賽靈思 Virtex®-4 LX200 FPGA；每個(gè) FPGA 都通過(guò) SGI NUMAlink 高速I(mǎi)/O 接口連接到主機平臺，并能通過(guò)最高速度為每秒 16GB 的 128 位數據總線(xiàn)存取本地 64MB 的SRAM 存儲庫。主機系統是一套 80 個(gè)內核的 64 位 NUMA 設備，運行性能為 64 位 Linux (OpenSuSE)。處理器為雙核 Itanium-2，運行頻率為 1.6 GHz，其中每個(gè)處理器都能直接存取 4GB 的存儲器，而且能通過(guò) NUMAlink 存取完整的 320GB 存儲器空間。值得注意的是，Itanium 處理器功耗約為 130 瓦特 [7]，而每個(gè) Virtex-4 FPGA 的功耗僅約 1.25 W [8]。

圖 2 —— 在 FPGA 子系統架構中，Virtex-4 器件通過(guò) SGI 的 NUMAlink 接口與主機平臺連接。

對于 C++ 語(yǔ)言應用而言，我們實(shí)施 Lemur 信息檢索 (IR) 框架，對于與 FPGA 應用的交互，我們則使用 SGI 可配置專(zhuān)用計算 (RASC) 庫。Lemur Toolkit（詳情訪(fǎng)問(wèn) www.lemurproject.org）是一套開(kāi)源工具集，專(zhuān)為 IR 研究而精心設計，可支持索引以及多種相關(guān)性和檢索模型。RASC 庫是 SGI的專(zhuān)有解決方案，能夠通過(guò)高性能 NUMAlink 互連機制將 FPGA 與主機系統相集成。RASC 庫定義的硬件抽象 API 可控制系統中的所有硬件元素。

我們用 Mitrionics 軟件開(kāi)發(fā)工具套件 (SDK) 將特定域的 Mitrion-C 語(yǔ)言轉換為 VHDL。生成的VHDL 現在能夠方便地指向 FPGA 器件架構。我們采用帶 XST 合成工具的賽靈思 ISE® 工具鏈來(lái)創(chuàng )建 Virtex-4 比特流。

高級 FPGA 編程

Mitrionics SDK 可提供 Mitrion-C 作為高級語(yǔ)言，專(zhuān)用于滿(mǎn)足在 FPGA 上快速開(kāi)發(fā)應用之需。不過(guò)，作為后綴的 C 有些誤導作用。盡管這種語(yǔ)言采用了 C 風(fēng)格的語(yǔ)法，但實(shí)際上是一種遵循函數編程風(fēng)格的單賦值數據流語(yǔ)言。Mitrion-C 原生支持廣泛（矢量）而深入（管道）的并行功能，因而非常適用于處理數據流的算法，例如過(guò)濾以及其他眾多類(lèi)型的文本和數據挖掘算法等。

Mitrion-C 還提供了一種流數據類(lèi)型，可配合 foreach looping 構造實(shí)現流水線(xiàn)操作；此外，還提供矢量數據類(lèi)型以支持數據并行工作，以及支持順序列表的列表數據類(lèi)型。具體而言，用戶(hù)可過(guò)濾foreach loop 的流輸出，生成較小的流，如以下 Mitrion-C 代碼示例所示。此外，程序人員還能用元組結構 (tuple construct) 創(chuàng )建功能強大的數據類(lèi)型。最后還有一個(gè)需要指出的特性是，該語(yǔ)言能支持可變寬度整數和浮點(diǎn)數。

為了在 FPGA 上高效實(shí)施評分操作，我們必須解決的關(guān)鍵問(wèn)題是高效查詢(xún)配置文件以及文檔流的高效 I/O 流。

對于文檔中的每個(gè)詞，應用都要查詢(xún)配置文件中相應的詞并獲得詞加權 (term weight)。由于大多數查詢(xún)都找不到結果（即大多數文檔的大多數詞不會(huì )出現在配置文件中），因此必須首先丟棄否定詞。鑒于此，我們在 FPGA Block RAM 中采用了 Bloom 過(guò)濾器 [9]。BRAM 的內部帶寬越高，拒絕否定詞的結果就越快。由于需要查詢(xún)，因此配置文件必須作為某種散列函數進(jìn)行實(shí)施。不過(guò)，由于配置文件的大小不能提前知道，因而我們不可能構建出完美的散列函數。不完美的散列函數會(huì )出現沖突問(wèn)題，進(jìn)而降低性能。

為了解決這一問(wèn)題，我們采用了分檔方案，即將外部 SRAM 分區為 bin，每個(gè) bin 都可包含固定數量的配置文件詞。Bin 的大小決定了可處理的沖突數。如需給 bin 分配配置文件詞，只需將詞 ID 的較下部分作為存儲器地址，從而避免了實(shí)際的散列操作。

讓 SRAM 存儲器容量設定為 NM 配置文件詞。詞 ID 是一個(gè)無(wú)符號的整數，其范圍取決于詞匯量，就我們的例子而言約為 400 萬(wàn)個(gè)詞，需要 24 位。詞加權為 8.32 定點(diǎn)數，因而配置文件詞需要 64 位。RC100 上的 SRAM 包括 4 個(gè) 16 MB 存儲庫，因此 NM=223。Bins 的數量 nb=NM/b 和 bin 地址用詞 ID“t”進(jìn)行計算，即 (t(nb-1)).b。

Bin 的占用概率 x 由組合決定，置換決定 bin 的數量 nb 和描述詞的數量 np。這樣，我們就能計算 bin 溢出的概率就是 bin 大小的函數（即 bin 的數量），即 NM=b.nb。bin 尺寸越大，查詢(xún)就越慢，但是，由于 SRAM 存儲庫包括 4 個(gè)獨立的 64 位可尋址雙端口 SRAM，我們實(shí)際上可以并行查詢(xún)四個(gè)配置文件詞。因此，相對性能會(huì )降低 1/ceil(b/4)。我們的分析結果顯示，即便對最大型的配置文件來(lái)說(shuō)（16K，我們研究所用的最大配置文件為 12K，不過(guò)通常配置文件比這都要小得多），b=4時(shí)（最佳性能），bin 溢出概率為 10-9。換言之，描述詞被丟棄的概率不到 10 億分之一。應注意的是，由于我們假定詞匯量無(wú)限大，因而這一估算還是保守數字。

圖 3 —— 過(guò)濾應用的 FPGA 實(shí)施示意圖

通過(guò)將文檔表述為“詞袋”，文檔流就是文檔 ID、文檔詞對組 (document term pair set) 等對列表。從物理上說(shuō)，FPGA 以每秒 1.6 GB 的速度從 NUMAlin 接受 128 位字流。因此，文檔流必須在字流上編碼?？蓪⑽臋n詞對 di =(ti,fi) 編碼為 32 位：24 位用于詞 ID（支持 1,600 萬(wàn)個(gè)詞的詞匯庫），8 位用于詞的頻率。這樣，我們就能將 4 個(gè)對組合到 128 位字中。要標示文檔的起點(diǎn)與終點(diǎn)，我們需要插入包含文檔 ID（64 位）和標志符（64 位）的報頭與腳注字 (footer word)。