淺析FPGA加速圖數(shù)據(jù)庫查詢執(zhí)行的步驟

一、背景介紹

在當(dāng)今的數(shù)據(jù)化場景越來越豐富的大環(huán)境下，涌現(xiàn)出的非結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)分析被應(yīng)用于多數(shù)領(lǐng)域。為了使機(jī)器能夠自動(dòng)分析數(shù)據(jù)，語義網(wǎng)絡(luò)的概念被創(chuàng)建，元數(shù)據(jù)被用來描述和鏈接任何類型的數(shù)據(jù)和資源。 面對存儲(chǔ)和處理大規(guī)模的數(shù)據(jù)，除了不斷被優(yōu)化的數(shù)據(jù)結(jié)構(gòu)外，硬件也是需要被極大優(yōu)化的。海量數(shù)據(jù)的持續(xù)存儲(chǔ)在當(dāng)今硬件環(huán)境下是沒有問題的，但是要實(shí)現(xiàn)在一個(gè)可以被接受的、被允許的時(shí)間范圍內(nèi)進(jìn)行處理和分析則變得愈發(fā)艱難。

因此，許多數(shù)據(jù)庫系統(tǒng)逐漸傾向于異構(gòu)，由專門的計(jì)算內(nèi)核來有效地執(zhí)行特定的任務(wù)。 那么不得不提的，便是高性能計(jì)算常用到的 GPU （圖形處理器）。GPU 最突出的優(yōu)點(diǎn)是高性能，即高密度運(yùn)算和高效并行性，非常適合處理計(jì)算密集型的任務(wù)；同時(shí)，其易于連接到處理器端的屬性也是它可以被廣泛應(yīng)用的原因。

然而，其缺點(diǎn)也是顯而易見的，就是高功耗。 在 GPU 之外，還存在為特定任務(wù)設(shè)計(jì)的專有硬件加速器，其對于指定的任務(wù)擁有較高的性能，但是其使用非常的不靈活，只能處理特定的任務(wù)，重新擴(kuò)展的性能幾乎為零。 最后，則是最近被廣泛使用的 FPGA，它具有動(dòng)態(tài)部分重配置的能力，可以縮小 CPU 的靈活性和專用硬件加速器的性能之間的差距，并且還擁有低功耗、高并發(fā)的優(yōu)勢。



FPGA 卡的核心部分示意圖 如上圖所示，一塊 FPGA 芯片由可配置邏輯模塊（CLB）構(gòu)成，每個(gè) CLB 都包含特定的結(jié)構(gòu)，如：查找表（LUT）、多路復(fù)用器、進(jìn)位鏈、觸發(fā)器等。除此之外，一塊 FPGA 卡上還有 BRAM（Block RAM），可以將其想象成 CPU 中 cache 的角色，以及 DSP (數(shù)字信號處理器）和一些通信接口（PCIe 等）。 這篇文章通過引入半靜態(tài)操作符圖，設(shè)計(jì)了一個(gè) FPGA-CPU 異構(gòu)的圖數(shù)據(jù)庫系統(tǒng)，加速了在大規(guī)模語義數(shù)據(jù)集上的查詢性能。

二、相關(guān)工作

上圖為一個(gè) FPGA-CPU 混合處理運(yùn)算的基本架構(gòu)，客戶端應(yīng)用程序向混合數(shù)據(jù)庫服務(wù)器發(fā)送查詢，該服務(wù)器使用基于 FPGA 的硬件加速器透明地確定結(jié)果。 文中主要引用的內(nèi)容為： Dennl 等人提出了關(guān)系型數(shù)據(jù)庫 MySQL 中 SQL 查詢的實(shí)時(shí)硬件加速的概念，但他們主要關(guān)注限制和聚合操作符，因此無法在 FPGA 上執(zhí)行完整的查詢。 Becher 等人添加了更復(fù)雜的運(yùn)算符（例如：歸并連接、小數(shù)據(jù)集上的排序）。

對于一個(gè)包含一個(gè) Join 的簡單的查詢，它們的性能與標(biāo)準(zhǔn)的基于 x86 的系統(tǒng)相當(dāng)，不過能源效率更高一些。 Woods 等人提出了 Ibex，一種用于關(guān)系數(shù)據(jù)庫 MySQL 的智能存儲(chǔ)引擎，可以支持使用 FPGA 卸載復(fù)雜的查詢操作符。 Wang 等人使用 OpenCL high level synthesis (HLS) 將數(shù)據(jù)庫操作符實(shí)現(xiàn)為 FPGA 的 Kernel。

但是查詢只用到了范圍檢查和一個(gè) Join，相對簡單。 Heinrich 等人提出了一種混合索引結(jié)構(gòu)，它在 FPGA 上存儲(chǔ)包括根節(jié)點(diǎn)在內(nèi)的高層 B+ 樹，在主機(jī)上存儲(chǔ)包括葉子節(jié)點(diǎn)在內(nèi)的低層。 而本文是第一個(gè)針對語義 Web 數(shù)據(jù)庫完全集成的基于 FPGA 的查詢引擎。

在介紹本文的混合數(shù)據(jù)庫系統(tǒng)之前，先介紹一下本文用到的圖數(shù)據(jù)庫基礎(chǔ)。論文的工作是基于一個(gè)開源的圖數(shù)據(jù)庫系統(tǒng) LUPOSDATE，它支持完整的 SPARQL 1.0 和 SPARQL 1.1 標(biāo)準(zhǔn)查詢語言。論文通過引入基于 FPGA 的查詢引擎，與 LUPOSDATE 系統(tǒng)結(jié)合在一起。

LUPOSDATE 使用 RDF 三元組作為基本數(shù)據(jù)格式來描述 Web 資源，RDF 三元組表示為 ，其中 s 是 subject (主語)、p 是 predicate (謂詞)、o 是 object (賓語)。 相應(yīng)的，LUPOSDATE 存儲(chǔ)的 B+ 樹索引結(jié)構(gòu)有六種：SPO、SOP、PSO、POS、OSP、OPS，可以在檢索時(shí)方便的得到有序的三元組。

除此之外，LUPOSDATE 還維護(hù)一個(gè) ISTree 和一個(gè) SITree，用于 RDF 字符串和整數(shù) id 之間的映射，這有利于 FPGA 模塊的設(shè)計(jì)，因?yàn)?FPGA 無法處理不定長度的字符串。 如下圖所示，對于給定的一個(gè) SPARQL 查詢：



LUPOSDATE 語法分析器會(huì)產(chǎn)生相應(yīng)的變量數(shù)組和操作符圖：

三、論文解決的問題

本文實(shí)現(xiàn)的混合數(shù)據(jù)庫系統(tǒng)是一個(gè) LUPOSDATE 的擴(kuò)展，由 CPU 主機(jī)和 FPGA 異構(gòu)而成，如上圖所示。主機(jī)提供更高層級的功能，如用戶界面、查詢優(yōu)化、評估指標(biāo)維護(hù)等，而 FPGA 被用作查詢執(zhí)行時(shí)的自適應(yīng)加速器。主機(jī)和 FPGA 之間的通信是基于外設(shè)原件 PCIe 的。

FPGA 區(qū)域被劃分為靜態(tài)邏輯和許多個(gè)小 RP，每個(gè) RP 可以配置任意類型的運(yùn)算符，每個(gè)運(yùn)算符作為一個(gè)可配置模塊是提前生成的。靜態(tài)邏輯包含與實(shí)際查詢結(jié)構(gòu)獨(dú)立的模塊，包括 PCIe 接口、一個(gè)管理模塊和查詢協(xié)調(diào)器（QC）。 QC 的主要任務(wù)是將傳入的三元組交給最上層的 RP 進(jìn)行相應(yīng)索引結(jié)構(gòu)的導(dǎo)入，以及檢索和序列化變量數(shù)組用以生成最終結(jié)果。

此外，每個(gè) RP 之間的互聯(lián)也位于靜態(tài)邏輯中。每個(gè)實(shí)現(xiàn)的查詢操作符都使用了如下圖所示的一個(gè)公共模板：



每個(gè)操作符至多有兩個(gè)前向操作符和一個(gè)后向操作符，如果一個(gè)操作符只需要一個(gè)前向操作符，那么只有左邊的輸入被啟用。每一個(gè)輸入或輸出都有如下參數(shù)：一個(gè) data 向量對應(yīng)輸入輸出的數(shù)組，一個(gè) valid 信號表示數(shù)據(jù)的有效性，一個(gè) finished 參數(shù)指定數(shù)據(jù)的結(jié)尾，一個(gè)反向 read 信號通知前向操作符數(shù)據(jù)已經(jīng)被讀取，并且在新數(shù)據(jù)到來之前不會(huì)進(jìn)行操作。最后，數(shù)據(jù)的寬度也必須作為一個(gè)參數(shù)傳入，因?yàn)?FPGA 無法支持變長的數(shù)據(jù)類型。 下面介紹一下論文實(shí)現(xiàn)的操作符：

RDF3XIndexScan：RDF3XIndexScan 是 QC 和內(nèi)部操作符之間的聯(lián)系。這個(gè)操作符的主要目標(biāo)是從 QC 中接收三元組，并將它們所需的組件映射到變量數(shù)組的某個(gè)位置。它維護(hù)三個(gè) one-hot 編碼的向量，每個(gè)向量的第 i 位代表第 i 個(gè)變量，如果某一個(gè)元素是常量，那么就將其所有位置為 1。

Join：Join 操作符是自然連接，本文使用的是 MergeJoin 的方式。它維護(hù)一個(gè) one-hot 編碼的向量，向量的第 i 位代表第 i 個(gè)變量，指代要 Join 的變量。

Filter：Filter 操作符是用于執(zhí)行條件查詢。復(fù)雜的 Filter 表達(dá)式將被分解為多個(gè)簡單的 VALUE COND VALUE 的 Filter 操作符。其中，VALUE 可以是一個(gè)值、一個(gè)變量或一個(gè)式子，COND 是比較條件。但由于 FPGA 無法處理字符串的問題，所以通過將字符串映射為整數(shù) id 之后，系統(tǒng)只能支持相等和不相等的比較。

Projection：Projection 操作符是用于將需要的變量結(jié)果從變量數(shù)組中投影出來。

Union：Union 操作符就是簡單的將兩個(gè)前向操作符得到的結(jié)果做一個(gè)并集操作。

Limit 和 offset：Limit 操作符會(huì)轉(zhuǎn)發(fā)特定數(shù)量的結(jié)果給變量數(shù)組。而 offset 操作符會(huì)跳過特定數(shù)量的結(jié)果。它們一般作為操作符圖的最后幾步。

從混合系統(tǒng)結(jié)構(gòu)圖中可以看到，每個(gè) RP 之間并不是直接輸入輸出互聯(lián)，而是通過了一個(gè)上圖所示的半靜態(tài)路由元素（SRE）結(jié)構(gòu)。論文以一個(gè)兩路復(fù)用 SRE 為例，當(dāng) succ_sel 信號為 0 時(shí)，數(shù)據(jù)流會(huì)直接向下路由，為 1 時(shí)，會(huì)向另一側(cè)路由。SRE 的存在使得可以用更少的 RP 組成一個(gè)支持查詢范圍更大的半靜態(tài)操作符圖。

四、混合系統(tǒng)工程流程

上圖給出了混合系統(tǒng)的工作流程圖，可以將其分為部署階段和系統(tǒng)運(yùn)行時(shí)。在部署階段，除了需要導(dǎo)入數(shù)據(jù)之外，整個(gè)靜態(tài)邏輯必須部署在 FPGA 上，每個(gè)操作符對應(yīng)的 RM 也需要提前生成并存儲(chǔ)在 RM 庫中。

在系統(tǒng)運(yùn)行時(shí)，主機(jī)通過分析輸入的 SPARQL 查詢，將其解析成相應(yīng)的操作符圖，檢測其是否可以用配置在 FPGA 上，如果有不支持的操作符存在，那么會(huì)直接 CPU 端執(zhí)行查詢，如果所有操作符都支持，那么 ICAP 會(huì)選擇對應(yīng)操作符的 RM 配置在 FPGA 的半靜態(tài)操作符圖上。主機(jī)通過 PCIe 向 FPGA 端提供輸入三元組，并接收 FPGA 端發(fā)回的結(jié)果進(jìn)行后處理，F(xiàn)PGA 端負(fù)責(zé)具體的計(jì)算任務(wù)。

五、實(shí)驗(yàn)結(jié)果

本文使用的是 Xilinx 的 Virtex-6 FPGA 卡和 PCIe 2.0 八通道通信接口，在 SP2Bench 三個(gè)不同大小的數(shù)據(jù)集（66M，131M 和 262M 個(gè)三元組）上進(jìn)行了實(shí)驗(yàn)。下圖是他們采用的 SPARQL 查詢示例：





Query 1 是用到了 Filter 操作符的查詢，Query 2 是用到了 Union 操作符的查詢，Query 3-5 分別是用到了不同數(shù)量的 Join 操作符。他們在 FPGA 端部署的半靜態(tài)操作符圖如下：



最后的實(shí)驗(yàn)結(jié)果表明，加入了 FPGA 的混合系統(tǒng)比原來的 LUPOSDATE 系統(tǒng)的查詢執(zhí)行速度更快。并且隨著數(shù)據(jù)規(guī)模的增大，加速比會(huì)更大，說明混合系統(tǒng)更加適合大規(guī)模的數(shù)據(jù)集上的查詢。

六、總結(jié)

在這篇文章中，作者在 FPGA 上引入了半靜態(tài)運(yùn)算符圖（SOG）的概念，為語義網(wǎng)數(shù)據(jù)庫中的查詢執(zhí)行提供靈活的硬件加速器。作者沒有為給定的查詢系統(tǒng)運(yùn)行時(shí)生成一個(gè) FPGA 配置，而是以一定程度的靈活性部署了通用查詢結(jié)構(gòu)。 SOG 由多個(gè)具有公共接口的 RP 組成。

在為每個(gè) RP 部署系統(tǒng)期間，會(huì)生成一組部分位文件的 RM，并將其存儲(chǔ)到存儲(chǔ)庫中。在系統(tǒng)運(yùn)行時(shí)，作者的混合系統(tǒng)針對給定的 SPARQL 查詢選擇 RM，并通過 ICAP 將其配置為 RP，RP 設(shè)置 FPGA 上運(yùn)算符圖的最終結(jié)構(gòu)。作為這項(xiàng)工作的主要貢獻(xiàn)，耗時(shí)的 RM 生成在系統(tǒng)運(yùn)行時(shí)之前執(zhí)行，并且信號大大減少了查詢執(zhí)行期間的重新配置。

審核編輯：劉清