無論為數(shù)以百萬計(jì)的用戶搜索請(qǐng)求提供服務(wù)還是處理超大量的信息，都需要數(shù)量龐大的計(jì)算資源，進(jìn)而消耗大量能源。事實(shí)上，用于計(jì)算與冷卻的能耗費(fèi)用是數(shù)據(jù)中心運(yùn)營(yíng)的最大成本 [1]。隨著數(shù)據(jù)中心的數(shù)量和規(guī)模不斷增長(zhǎng)，如果其能耗保持當(dāng)前水平的話，那么預(yù)計(jì)數(shù)據(jù)中心的二氧化碳排放量到 2020 年將超過航空公司 [2]。因而亟需開發(fā)能夠處理巨量數(shù)據(jù)的低能耗解決方案。數(shù)據(jù)中心的環(huán)?；l(fā)展是互利共贏的，服務(wù)供應(yīng)商不僅能夠顯著降低運(yùn)營(yíng)成本，同時(shí)還能最大限度減少對(duì)環(huán)境的影響。

FPGA在加速Web搜索及類似信息檢索等常見數(shù)據(jù)中心工作任務(wù)方面擁有巨大的潛力，因?yàn)樗邆涔逃械牟⑿刑幚砼c低功耗優(yōu)勢(shì)。充分認(rèn)識(shí)到這一潛力的奧地利公司Matrixware購買了FPGA平臺(tái)，但缺乏自身實(shí)施復(fù)雜信息檢索應(yīng)用的技術(shù)，因而公司聘請(qǐng)了我們聯(lián)合格拉斯哥大學(xué) (University of Glasgow) 計(jì)算機(jī)系組建的團(tuán)隊(duì)開發(fā) FPGA 加速型專利搜索解決方案的概念驗(yàn)證方案。該團(tuán)隊(duì)成員包括三名設(shè)計(jì)人員和兼職助理研究員Stelios Papanastasious，他們?cè)谛畔z索、FPGA以及系統(tǒng)開發(fā)領(lǐng)域積累了豐富的專業(yè)知識(shí)，形成了一個(gè)開發(fā)原型應(yīng)用所不可或缺的技能嫻熟的組合。經(jīng)討論，大家一致同意采用FPGA加速型后端進(jìn)行實(shí)時(shí)專利過濾應(yīng)用的開發(fā)。

項(xiàng)目資源在人力和時(shí)間方面受到很大制約。因此，采用HDL實(shí)施過濾算法不可行，因而我們決定采用瑞典公司Mitrionics開發(fā)的高級(jí)編程解決方案。原型應(yīng)用在去年11月于奧地利維也納舉行的信息檢索設(shè)施研討會(huì)(Information Retrieval Facility Symposium)上引起了專利研究人員的極大興趣。處理數(shù)以百萬份的專利通常需要幾分鐘，但若采用FPGA加速型后端，幾秒鐘就能反饋結(jié)果。

我們?cè)?009年7月舉行的ACM SIGIR國(guó)際信息檢索研究暨開發(fā)大會(huì)(ACM SIGIR International Conference
on Information Retrieval Research and Development) 上發(fā)布了結(jié)果，介紹了相關(guān)的性能提升情況 [3]，并在FPL 2009國(guó)際現(xiàn)場(chǎng)可編程邏輯大會(huì)上對(duì)架構(gòu)設(shè)計(jì)進(jìn)行了詳細(xì)闡述 [4]。

文檔過濾的輸入與輸出通常情況下，信息過濾任務(wù)是指檢查傳送進(jìn)來的文檔是否與一系列既定的需求信息或配置文件相匹配 [5]。這種任務(wù)可在多種情況下出于多種原因而進(jìn)行，例如，檢測(cè)傳送進(jìn)入的電子郵件是不是垃圾郵件，比較專利申請(qǐng)是否與現(xiàn)有專利發(fā)生重疊，監(jiān)控是否存在恐怖活動(dòng)通信，監(jiān)測(cè)并跟蹤新聞報(bào)道，等等。面對(duì)大量涌入的文檔，處理工作必須實(shí)時(shí)完成，從而確保時(shí)效性成為重中之重。鑒于此，我們的目標(biāo)就是采用FPGA來實(shí)施完成計(jì)算強(qiáng)度最大的過濾應(yīng)用，從而在節(jié)約時(shí)間和降低能耗的情況下提高文檔過濾的效率。

在本文中，我們將采用Lavrenko和Croft提出的相關(guān)性模型 [6]。這一理念適用于信息過濾任務(wù)，可通過生成概率語言模型確定傳入文檔是否與主題配置文件存在差異。如果文檔得分超過用戶定義的閾值，那么就視為與主題配置文件相關(guān)。

在FPGA上實(shí)施的算法表達(dá)如下：文檔可以建模為一個(gè)“詞袋”，即由(t,f )對(duì)組成的D集，其中 f=n(t,d)，t 表示 t 這個(gè)詞在文檔d中出現(xiàn)的次數(shù)。配置文件M為一組對(duì) p=(t,w)，這里的w加權(quán)為：

給定文檔對(duì)于給定配置文件的得分計(jì)算為：

這里，T是指在D和M中都出現(xiàn)的詞。該函數(shù)是大多數(shù)過濾算法的代表性內(nèi)核算法，不同算法的主要區(qū)別在于配置文件中詞的加權(quán)。

圖 1 —— 系統(tǒng)架構(gòu)以可作為客戶端與后端服務(wù)器之間代理的通信服務(wù)器為中心。

應(yīng)用架構(gòu)

文檔過濾應(yīng)用采用客戶端—服務(wù)器架構(gòu)，其構(gòu)成形式為將基于GUI的客戶由FPGA加速的部分受限于計(jì)算強(qiáng)度最大的任務(wù)，也就是文檔與配置文件的匹配。主機(jī)系統(tǒng)則負(fù)責(zé)處理所有其他的任務(wù)（參見圖 2）。

配置文件服務(wù)器根據(jù)從客戶端獲得的配置文件過濾一系列文檔，并返回分?jǐn)?shù)流。為了評(píng)估性能，我們同時(shí)創(chuàng)建了C++ 參考實(shí)施和FPGA加速實(shí)施方案。兩種版本的實(shí)施方案基本功能相同，都能通過TCP/IP接口接收構(gòu)成配置文件的文檔列表，用相關(guān)性模型構(gòu)建配置文件，并根據(jù)該配置文件對(duì)存儲(chǔ)器緩沖的文檔進(jìn)行評(píng)分，從而通過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都通過SGI NUMAlink高速I/O接口連接到主機(jī)平臺(tái)，并能通過最高速度為每秒 16GB 的 128 位數(shù)據(jù)總線存取本地 64MB 的 SRAM 存儲(chǔ)庫。主機(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ǔ)器，而且能通過 NUMAlink存取完整的320GB存儲(chǔ)器空間。值得注意的是，Itanium處理器功耗約為130瓦特 [7]，而每個(gè)Virtex-4 FPGA的功耗僅約1.25 W [8]。

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

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

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

高級(jí)FPGA編程

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

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

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

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

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

讓SRAM存儲(chǔ)器容量設(shè)定為NM配置文件詞。詞ID是一個(gè)無符號(hào)的整數(shù)，其范圍取決于詞匯量，就我們的例子而言約為 400 萬個(gè)詞，需要 24 位。詞加權(quán)為 8.32 定點(diǎn)數(shù)，因而配置文件詞需要64位。RC100上的SRAM包括4個(gè)16MB存儲(chǔ)庫，因此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ǔ)庫包括4個(gè)獨(dú)立的64位可尋址雙端口SRAM，我們實(shí)際上可以并行查詢四個(gè)配置文件詞。因此，相對(duì)性能會(huì)降低1/ceil(b/4)。我們的分析結(jié)果顯示，即便對(duì)最大型的配置文件來說（16K，我們研究所用的最大配置文件為12K，不過通常配置文件比這都要小得多），b=4時(shí)（最佳性能），bin溢出概率為10-9。換言之，描述詞被丟棄的概率不到10億分之一。應(yīng)注意的是，由于我們假定詞匯量無限大，因而這一估算還是保守?cái)?shù)字。

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

如上所述采用查詢表架構(gòu)和文檔流格式，實(shí)際的查詢和評(píng)分系統(tǒng)（圖3）會(huì)非常直接。我們只需掃描輸入流以檢查報(bào)頭和腳注字即可。報(bào)頭字將文檔得分設(shè)為 0，而腳注字則收集并輸出文檔得分。對(duì)于文檔中的每四個(gè)配置文件
詞，Bloom過濾器首先丟棄否定詞結(jié)果，再從SRAM讀取四個(gè)配置文件詞。并行計(jì)算并添加（圖4）每個(gè)詞的得分。實(shí)際上，四分之三的配置文件詞ID不會(huì)匹配于文檔詞ID；只對(duì)第四個(gè)進(jìn)行實(shí)際計(jì)算。將文檔中所有詞的得分進(jìn)行累加，最后得分流在輸出到主機(jī)存儲(chǔ)器之前與限值進(jìn)行比較過濾。

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

主機(jī)—FPGA接口將文檔流從存儲(chǔ)器緩沖器中傳輸至FPGA，并將得分流返回至客戶端中。一旦從客戶端接收到配置文檔ID表，子進(jìn)程即從主進(jìn)程中分叉出來，以構(gòu)建實(shí)際的配置文件，將其載入SRAM并在FPGA上運(yùn)行算法。每個(gè)子進(jìn)程都會(huì)產(chǎn)生一個(gè)獨(dú)立的輸出線程，以對(duì)從FPGA獲得的得分進(jìn)行緩沖，并通過TCP/IP將這些得分傳輸?shù)娇蛻舳?，從而使用網(wǎng)絡(luò)對(duì)得分流進(jìn)行多路復(fù)用。若沒有該線程，網(wǎng)絡(luò)吞吐量的波動(dòng)就會(huì)降低系統(tǒng)性能。這種主機(jī)接口架構(gòu)的主要優(yōu)勢(shì)在于，它具有很高的可擴(kuò)展性，能輕松滿足大量FPGA的需求。

大幅度提速

為了評(píng)估FPGA加速型過濾應(yīng)用的性能，我們進(jìn)行了一系列實(shí)驗(yàn)，將基于FPGA的實(shí)施方案與采用C++編寫的運(yùn)行于Altix之上的優(yōu)化參考實(shí)施方案進(jìn)行了比較。在比較過程中，我們使用了三個(gè)IR測(cè)試集合（參見表 1）：一個(gè)是文本檢索會(huì)議 (TREC) 提供的基準(zhǔn)參考集合TREC Aquaint，還有兩個(gè)分別是美國(guó)專利與商標(biāo)署 (USPTO) 和歐洲專利署 (EPO) 提供的專利集合。我們選擇上述測(cè)試集合來評(píng)估不同文檔長(zhǎng)度和大小對(duì)過濾時(shí)間的影響。

表 1——集合統(tǒng)計(jì)

為了仿真眾多不同的過濾器，我們通過選擇隨機(jī)文檔并用標(biāo)題作為請(qǐng)求，隨后再選擇請(qǐng)求服務(wù)器返回的固定數(shù)量的文檔作為偽相關(guān)文檔，來為每個(gè)測(cè)試集合構(gòu)建配置文件。我們接下來使用返回的文檔構(gòu)建相關(guān)性模型，該模型定義了文檔集合中每個(gè)文檔應(yīng)當(dāng)匹配（就好像從網(wǎng)絡(luò)進(jìn)行流處理一樣）的配置文件。配置文件中的文檔數(shù)量從1到50不等，可確定增加配置文件的大小（詞數(shù)和文檔數(shù)）會(huì)對(duì)性能有何影響。我們將上述進(jìn)程重復(fù)30次，并計(jì)算平均處理時(shí)間。

圖4 ——相關(guān)性模型

我們?cè)诒?和圖5中對(duì)有關(guān)結(jié)果進(jìn)行了總結(jié)。從表中可以清晰地看出，F(xiàn)PGA實(shí)施方案在速度方面通常比標(biāo)準(zhǔn)實(shí)施方案快一個(gè)數(shù)量級(jí)。從圖中可以看出，配置文件大小（需要匹配的詞數(shù)）增加后，標(biāo)準(zhǔn)實(shí)施方案變得越來越慢，而FPGA實(shí)施方案的速度相對(duì)保持不變。這是因?yàn)镕PGA實(shí)施方案支持配置文件評(píng)分的流分線操作，這樣無論配置文件大小如何，時(shí)延基本保持不變。這些結(jié)果清晰表明，F(xiàn)PGA對(duì)加速IR任務(wù)有著巨大的潛力。FPGA的提速幅度已然相當(dāng)大（特別對(duì)大型配置文件而言尤其明顯），而且仍有進(jìn)一步提高的空間。通過仿真，我們確認(rèn)FPGA算法給一個(gè)文檔詞評(píng)分需要兩個(gè)時(shí)鐘周期。制約因素為每周期128位的SRAM存取速度，這需要兩個(gè)周期才能讀取四個(gè)配置文件詞。如果時(shí)鐘速度為 100 MHz，則意味著FPGA能在15秒之內(nèi)完成整個(gè)EPO文檔集合的評(píng)分。當(dāng)前應(yīng)用在四個(gè)FPGA上需要約8.5秒，因此原則上我們至少可以讓性能再翻一番。

表 2 —— 性能統(tǒng)計(jì)數(shù)據(jù)

圖 5 —— 時(shí)間（秒）和配置文件中文檔數(shù)量的對(duì)比圖

差異的原因在于I/O流 (streaming I/O)：通過主機(jī)操作系統(tǒng)設(shè)備驅(qū)動(dòng)器可將文檔流從用戶存儲(chǔ)器空間傳輸至NUMAlink，這需要直接存儲(chǔ)器存取(DMA) 傳輸。驅(qū)動(dòng)器可傳輸流的緩存模塊。目前，對(duì)所傳輸模塊的大小來說，這一傳輸并不是以最優(yōu)的方式實(shí)施的，進(jìn)而導(dǎo)致無法達(dá)到最高吞吐量。此外，用獨(dú)立的線程進(jìn)行傳輸排序也能避免傳輸時(shí)延。

遇到的問題和吸取的經(jīng)驗(yàn)

這一項(xiàng)目的意義不僅在于它展示了FPGA作為信息檢索任務(wù)加速器的優(yōu)勢(shì)，而且還為我們提供了FPGA加速系統(tǒng)軟硬件要求的重要信息。

至主機(jī)系統(tǒng)的I/O是確保性能的關(guān)鍵：NUMA存儲(chǔ)器與FPGA之間的DMA機(jī)制必須獲得Mitrionics SDK和SGI RASClib的支持。在此前的項(xiàng)目中，我們必須先將數(shù)據(jù)傳輸?shù)诫娐钒迳系腟RAM中才能進(jìn)行處理，但這會(huì)嚴(yán)重影響性能，因?yàn)閿?shù)據(jù)的載入和結(jié)果的卸載會(huì)造成非常大的開銷。此外，我們也清晰地認(rèn)識(shí)到，IR任務(wù)尤其需要大量的片上和板上存儲(chǔ)器，才能實(shí)現(xiàn)效率最大化。

此外，為了充分使用FPGA，未來的平臺(tái)必須具備兩個(gè)重要特性，一是必需能在FPGA之間直接傳輸數(shù)據(jù)，二是必需能夠關(guān)閉主機(jī)處理器（或用一個(gè)主機(jī)處理器控制多個(gè) FPGA）。關(guān)閉主機(jī)處理器的功能尤其重要：在Altix平臺(tái)上，即便Itanium處理器完全處于空閑狀態(tài)也不能關(guān)閉。但是，空閑的Itanium處理器的功耗也高達(dá)工作狀態(tài)下所需功耗的90%。因此，盡管FPGA加速的節(jié)能效果明顯，但我們目前的系統(tǒng)即便在加速器運(yùn)行過程中主機(jī)存儲(chǔ)器空閑狀態(tài)下，其總體節(jié)能作用仍然有限。

開發(fā)FPGA加速型系統(tǒng)的另一重要領(lǐng)域就是軟件。我們的經(jīng)驗(yàn)明確反映出，主要的復(fù)雜問題在于FPGA 和主機(jī)系統(tǒng)之間的接口連接：Mitrion-C中的實(shí)際 FPGA 應(yīng)用開發(fā)效率非常高；采用Lemur工具套件構(gòu)建查詢和服務(wù)文檔的框架也相對(duì)容易開發(fā)。但是，采用RASClib開發(fā)連接主機(jī)應(yīng)用和FPGA接口的代碼非常復(fù)雜，而且由于并發(fā)性問題，還非常難以調(diào)試。因而，接口代碼的開發(fā)占據(jù)了絕大部分的開發(fā)時(shí)間。

FPGA高級(jí)編程的最后一個(gè)問題是編譯速度。習(xí)慣于C++或Java等語言的開發(fā)人員認(rèn)為即便應(yīng)用非常復(fù)雜，構(gòu)建時(shí)間也應(yīng)該比較短。除了最基本的設(shè)計(jì)之外，當(dāng)前的FPGA工具執(zhí)行綜合以及放置路由工作幾乎都需要一整天的時(shí)間。非常長(zhǎng)的構(gòu)建時(shí)間會(huì)嚴(yán)重影響工作效率，因而時(shí)間應(yīng)當(dāng)縮短到一般性軟件構(gòu)建時(shí)間，這樣才能使 FPGA 加速更具吸引力。

定制硬件平臺(tái)

我們用這個(gè)項(xiàng)目探討了FPGA加速的可能性，并展示了FPGA作為數(shù)據(jù)中心綠色環(huán)保技術(shù)的巨大潛力。我們希望進(jìn)一步擴(kuò)展這項(xiàng)研究，調(diào)查文檔處理所需的全系列工作任務(wù)，如語法分析、詞干、索引、搜索以及過濾等。我們清楚地認(rèn)識(shí)到，現(xiàn)有系統(tǒng)在節(jié)能潛力方面很有限，我們希望研究能以業(yè)界最高效率專門執(zhí)行信息檢索任務(wù)的可定制硬件平臺(tái)。這樣，我們就能顯著加速算法的執(zhí)行，同時(shí)大幅度降低能耗，從而開發(fā)出更加環(huán)保、速度更快的數(shù)據(jù)中心。