FPGA加速圖數(shù)據(jù)庫(kù)查詢(xún)執(zhí)行

來(lái)源 | OSCHINA 社區(qū)

作者 | KaiwuDB

導(dǎo)讀

本篇博客主要講解發(fā)布于 Microprocessors and Microsystems 的文章《Semi-static Operator Graphs for Accelerated Query Execution on FPGAs》，介紹它所提出的算法與試驗(yàn)結(jié)果，并結(jié)合實(shí)際情況給出一些思考。

一、背景介紹

在當(dāng)今的數(shù)據(jù)化場(chǎng)景越來(lái)越豐富的大環(huán)境下，涌現(xiàn)出的非結(jié)構(gòu)化數(shù)據(jù)存儲(chǔ)分析被應(yīng)用于多數(shù)領(lǐng)域。 為了使機(jī)器能夠自動(dòng)分析數(shù)據(jù)，語(yǔ)義網(wǎng)絡(luò)的概念被創(chuàng)建，元數(shù)據(jù)被用來(lái)描述和鏈接任何類(lèi)型的數(shù)據(jù)和資源。

面對(duì)存儲(chǔ)和處理大規(guī)模的數(shù)據(jù)，除了不斷被優(yōu)化的數(shù)據(jù)結(jié)構(gòu)外，硬件也是需要被極大優(yōu)化的。 海量數(shù)據(jù)的持續(xù)存儲(chǔ)在當(dāng)今硬件環(huán)境下是沒(méi)有問(wèn)題的，但是要實(shí)現(xiàn)在一個(gè)可以被接受的、被允許的時(shí)間范圍內(nèi)進(jìn)行處理和分析則變得愈發(fā)艱難。

因此，許多數(shù)據(jù)庫(kù)系統(tǒng)逐漸傾向于異構(gòu)，由專(zhuān)門(mén)的計(jì)算內(nèi)核來(lái)有效地執(zhí)行特定的任務(wù)。

那么不得不提的，便是高性能計(jì)算常用到的 GPU （圖形處理器）。 GPU 最突出的優(yōu)點(diǎn)是高性能，即高密度運(yùn)算和高效并行性，非常適合處理計(jì)算密集型的任務(wù)； 同時(shí)，其易于連接到處理器端的屬性也是它可以被廣泛應(yīng)用的原因。 然而，其缺點(diǎn)也是顯而易見(jiàn)的，就是高功耗。

在 GPU 之外，還存在為特定任務(wù)設(shè)計(jì)的專(zhuān)有硬件加速器，其對(duì)于指定的任務(wù)擁有較高的性能，但是其使用非常的不靈活，只能處理特定的任務(wù)，重新擴(kuò)展的性能幾乎為零。

最后，則是最近被廣泛使用的 FPGA，它具有動(dòng)態(tài)部分重配置的能力，可以縮小 CPU 的靈活性和專(zhuān)用硬件加速器的性能之間的差距，并且還擁有低功耗、高并發(fā)的優(yōu)勢(shì)。

FPGA 卡的核心部分示意圖

如上圖所示，一塊 FPGA 芯片由可配置邏輯模塊（CLB）構(gòu)成，每個(gè) CLB 都包含特定的結(jié)構(gòu)，如：查找表（LUT）、多路復(fù)用器、進(jìn)位鏈、觸發(fā)器等。 除此之外，一塊 FPGA 卡上還有 BRAM（Block RAM），可以將其想象成 CPU 中 cache 的角色，以及 DSP (數(shù)字信號(hào)處理器）和一些通信接口（PCIe 等）。

這篇文章通過(guò)引入半靜態(tài)操作符圖，設(shè)計(jì)了一個(gè) FPGA-CPU 異構(gòu)的圖數(shù)據(jù)庫(kù)系統(tǒng)，加速了在大規(guī)模語(yǔ)義數(shù)據(jù)集上的查詢(xún)性能。

二、相關(guān)工作

上圖為一個(gè) FPGA-CPU 混合處理運(yùn)算的基本架構(gòu)，客戶端應(yīng)用程序向混合數(shù)據(jù)庫(kù)服務(wù)器發(fā)送查詢(xún)，該服務(wù)器使用基于 FPGA 的硬件加速器透明地確定結(jié)果。

文中主要引用的內(nèi)容為：

Dennl 等人提出了關(guān)系型數(shù)據(jù)庫(kù) MySQL 中 SQL 查詢(xún)的實(shí)時(shí)硬件加速的概念，但他們主要關(guān)注限制和聚合操作符，因此無(wú)法在 FPGA 上執(zhí)行完整的查詢(xún)。

Becher 等人添加了更復(fù)雜的運(yùn)算符（例如：歸并連接、小數(shù)據(jù)集上的排序）。 對(duì)于一個(gè)包含一個(gè) Join 的簡(jiǎn)單的查詢(xún)，它們的性能與標(biāo)準(zhǔn)的基于 x86 的系統(tǒng)相當(dāng)，不過(guò)能源效率更高一些。

Woods 等人提出了 Ibex，一種用于關(guān)系數(shù)據(jù)庫(kù) MySQL 的智能存儲(chǔ)引擎，可以支持使用 FPGA 卸載復(fù)雜的查詢(xún)操作符。

Wang 等人使用 OpenCL high level synthesis (HLS) 將數(shù)據(jù)庫(kù)操作符實(shí)現(xiàn)為 FPGA 的 Kernel。 但是查詢(xún)只用到了范圍檢查和一個(gè) Join，相對(duì)簡(jiǎn)單。

Heinrich 等人提出了一種混合索引結(jié)構(gòu)，它在 FPGA 上存儲(chǔ)包括根節(jié)點(diǎn)在內(nèi)的高層 B+ 樹(shù)，在主機(jī)上存儲(chǔ)包括葉子節(jié)點(diǎn)在內(nèi)的低層。

而本文是第一個(gè)針對(duì)語(yǔ)義 Web 數(shù)據(jù)庫(kù)完全集成的基于 FPGA 的查詢(xún)引擎。

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

LUPOSDATE 使用 RDF 三元組作為基本數(shù)據(jù)格式來(lái)描述 Web 資源，RDF 三元組表示為 ，其中 s 是 subject (主語(yǔ))、p 是 predicate (謂詞)、o 是 object (賓語(yǔ))。

相應(yīng)的，LUPOSDATE 存儲(chǔ)的 B+ 樹(shù)索引結(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 無(wú)法處理不定長(zhǎng)度的字符串。

如下圖所示，對(duì)于給定的一個(gè) SPARQL 查詢(xún)：

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

三、論文解決的問(wèn)題

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

FPGA 區(qū)域被劃分為靜態(tài)邏輯和許多個(gè)小 RP，每個(gè) RP 可以配置任意類(lèi)型的運(yùn)算符，每個(gè)運(yùn)算符作為一個(gè)可配置模塊是提前生成的。 靜態(tài)邏輯包含與實(shí)際查詢(xún)結(jié)構(gòu)獨(dú)立的模塊，包括 PCIe 接口、一個(gè)管理模塊和查詢(xún)協(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)的查詢(xún)操作符都使用了如下圖所示的一個(gè)公共模板：

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

下面介紹一下論文實(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í)行條件查詢(xún)。 復(fù)雜的 Filter 表達(dá)式將被分解為多個(gè)簡(jiǎn)單的 VALUE COND VALUE 的 Filter 操作符。 其中，VALUE 可以是一個(gè)值、一個(gè)變量或一個(gè)式子，COND 是比較條件。 但由于 FPGA 無(wú)法處理字符串的問(wèn)題，所以通過(guò)將字符串映射為整數(shù) id 之后，系統(tǒng)只能支持相等和不相等的比較。

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

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

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

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

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

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

在系統(tǒng)運(yùn)行時(shí)，主機(jī)通過(guò)分析輸入的 SPARQL 查詢(xún)，將其解析成相應(yīng)的操作符圖，檢測(cè)其是否可以用配置在 FPGA 上，如果有不支持的操作符存在，那么會(huì)直接 CPU 端執(zhí)行查詢(xún)，如果所有操作符都支持，那么 ICAP 會(huì)選擇對(duì)應(yīng)操作符的 RM 配置在 FPGA 的半靜態(tài)操作符圖上。 主機(jī)通過(guò) 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 查詢(xún)示例：

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

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

六、總結(jié)

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

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