來源 | OSCHINA 社區(qū)

作者 | KaiwuDB

導讀

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

一、背景介紹

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

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

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

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

在 GPU 之外，還存在為特定任務設計的專有硬件加速器，其對于指定的任務擁有較高的性能，但是其使用非常的不靈活，只能處理特定的任務，重新擴展的性能幾乎為零。

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

FPGA 卡的核心部分示意圖

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

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

二、相關工作

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

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

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

Becher 等人添加了更復雜的運算符（例如：歸并連接、小數(shù)據(jù)集上的排序）。 對于一個包含一個 Join 的簡單的查詢，它們的性能與標準的基于 x86 的系統(tǒng)相當，不過能源效率更高一些。

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

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

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

而本文是第一個針對語義 Web 數(shù)據(jù)庫完全集成的基于 FPGA 的查詢引擎。

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

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

相應的，LUPOSDATE 存儲的 B+ 樹索引結構有六種：SPO、SOP、PSO、POS、OSP、OPS，可以在檢索時方便的得到有序的三元組。 除此之外，LUPOSDATE 還維護一個 ISTree 和一個 SITree，用于 RDF 字符串和整數(shù) id 之間的映射，這有利于 FPGA 模塊的設計，因為 FPGA 無法處理不定長度的字符串。

如下圖所示，對于給定的一個 SPARQL 查詢：

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

三、論文解決的問題

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

FPGA 區(qū)域被劃分為靜態(tài)邏輯和許多個小 RP，每個 RP 可以配置任意類型的運算符，每個運算符作為一個可配置模塊是提前生成的。 靜態(tài)邏輯包含與實際查詢結構獨立的模塊，包括 PCIe 接口、一個管理模塊和查詢協(xié)調(diào)器（QC）。

QC 的主要任務是將傳入的三元組交給最上層的 RP 進行相應索引結構的導入，以及檢索和序列化變量數(shù)組用以生成最終結果。 此外，每個 RP 之間的互聯(lián)也位于靜態(tài)邏輯中。 每個實現(xiàn)的查詢操作符都使用了如下圖所示的一個公共模板：

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

下面介紹一下論文實現(xiàn)的操作符：

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

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

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

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

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

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

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

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

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

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

五、實驗結果

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

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

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

六、總結

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

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