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

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

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

圖 2 —— 在 FPGA 子系統(tǒng)架構(gòu)中，Virtex-4 器件通過(guò) SGI 的 NUMAlink 接口與主機(jī)平臺(tái)連接。

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

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

高級(jí) FPGA 編程

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

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

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

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

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

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

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

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

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