學術貼 | FPGA 加速圖資料庫查詢執行

語言: CN / TW / HK

導讀

本篇部落格主要講解發佈於 Microprocessors and Microsystems 的文章《Semi-static Operator Graphs for Accelerated Query Execution on FPGAs》,介紹它所提出的演算法與試驗結果,並結合實際情況給出一些思考。


一、背景介紹

在當今的資料化場景越來越豐富的大環境下,湧現出的非結構化資料儲存分析被應用於多數領域。為了使機器能夠自動分析資料,語義網路的概念被建立元資料被用來描述和連結任何型別的資料和資源。

面對儲存和處理大規模的資料,除了不斷被優化的資料結構外,硬體也是需要被極大優化的。海量資料的持續儲存在當今硬體環境下是沒有問題的,但是要實現在一個可以被接受的、被允許的時間範圍內進行處理和分析則變得愈發艱難。

因此,許多資料庫系統逐漸傾向於異構,由專門的計算核心來有效地執行特定的任務。

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

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

最後,則是最近被廣泛使用的 FPGA,它具有動態部分重配置的能力,可以縮小 CPU 的靈活性和專用硬體加速器的效能之間的差距,並且還擁有低功耗、高併發的優勢。

FPGA 卡的核心部分示意圖

如上圖所示,一塊 FPGA 晶片由可配置邏輯模組(CLB)構成,每個 CLB 都包含特定的結構,如:查詢表(LUT)、多路複用器、進位鏈、觸發器等。此之外,一塊 FPGA 卡上還有 BRAM(Block RAM),可以將其想象成 CPU 中 cache 的角色,以及 DSP (數字訊號處理器)和一些通訊介面(PCIe 等)。

這篇文章通過引入半靜態操作符圖,設計了一個 FPGA-CPU 異構的圖資料庫系統,加速了在大規模語義資料集上的查詢效能。

 

二、相關工作

上圖為一個 FPGA-CPU 混合處理運算的基本架構,客戶端應用程式向混合資料庫伺服器傳送查詢,該伺服器使用基於 FPGA 的硬體加速器透明地確定結果。

文中主要引用的內容為:

Dennl等人提出了關係型資料庫 MySQL 中 SQL 查詢的實時硬體加速的概念,但他們主要關注限制和聚合操作符,因此無法在 FPGA 上執行完整的查詢。

Becher等人添加了更復雜的運算子(例如:歸併連線、小資料集上的排序)。對於一個包含一個 Join 的簡單的查詢,它們的效能與標準的基於 x86 的系統相當,不過能源效率更高一些。

Woods等人提出了 Ibex,一種用於關係資料庫 MySQL 的智慧儲存引擎,可以支援使用 FPGA 解除安裝複雜的查詢操作符。

Wang等人使用 OpenCL high level synthesis(HLS) 將資料庫操作符實現為 FPGA 的 Kernel。但是查詢只用到了範圍檢查和一個 Join,相對簡單。

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

而本文是第一個針對語義 Web 資料庫完全整合的基於 FPGA 的查詢引擎。

在介紹本文的混合資料庫系統之前,先介紹一下本文用到的圖資料庫基礎。論文的工作是基於一個開源的圖資料庫系統 LUPOSDATE,它支援完整的 SPARQL 1.0 和 SPARQL 1.1 標準查詢語言。論文通過引入基於 FPGA 的查詢引擎,與 LUPOSDATE 系統結合在一起。

LUPOSDATE 使用 RDF 三元組作為基本資料格式來描述 Web 資源,RDF 三元組表示為<s,p,o>,其中 s 是 subject (主語)、p 是 predicate (謂詞)、o 是 object (賓語)。

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

如下圖所示,對於給定的一個 SPARQL 查詢:

LUPOSDATE 語法分析器會產生相應的變數陣列和操作符圖:

 

三、論文解決的問題

本文實現的混合資料庫系統是一個 LUPOSDATE 的擴充套件,由 CPU 主機和 FPGA 異構而成,如上圖所示。主機提供更高層級的功能,如使用者介面、查詢優化、評估指標維護等,而 FPGA 被用作查詢執行時的自適應加速器。主機和 FPGA 之間的通訊是基於外設原件 PCIe 的。

FPGA 區域被劃分為靜態邏輯和許多個小 RP,每個 RP 可以配置任意型別的運算子,每個運算子作為一個可配置模組是提前生成的。靜態邏輯包含與實際查詢結構獨立的模組,包括 PCIe 介面、一個管理模組和查詢協調器(QC)。

QC 的主要任務是將傳入的三元組交給最上層的 RP 進行相應索引結構的匯入,以及檢索和序列化變數陣列用以生成最終結果。此外,每個 RP 之間的互聯也位於靜態邏輯中。每個實現的查詢操作符都使用瞭如下圖所示的一個公共模板:

每個操作符至多有兩個前向操作符和一個後向操作符,如果一個操作符只需要一個前向操作符,那麼只有左邊的輸入被啟用。每一個輸入或輸出都有如下引數:一個 data 向量對應輸入輸出的陣列,一個 valid 訊號表示資料的有效性,一個 finished 引數指定資料的結尾,一個反向 read 訊號通知前向操作符資料已經被讀取,並且在新資料到來之前不會進行操作。最後,資料的寬度也必須作為一個引數傳入,因為 FPGA 無法支援變長的資料型別。

下面介紹一下論文實現的操作符:

  • RDF3XIndexScan:RDF3XIndexScan 是 QC 和內部操作符之間的聯絡。這個操作符的主要目標是從 QC 中接收三元組,並將它們所需的元件對映到變數陣列的某個位置。它維護三個 one-hot 編碼的向量,每個向量的第 i 位代表第 i 個變數,如果某一個元素是常量,那麼就將其所有位置為 1。

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

  • Filter:Filter 操作符是用於執行條件查詢。複雜的 Filter 表示式將被分解為多個簡單的 VALUE COND VALUE 的 Filter 操作符。其中,VALUE 可以是一個值、一個變數或一個式子,COND 是比較條件。但由於 FPGA 無法處理字串的問題,所以通過將字串對映為整數 id 之後,系統只能支援相等和不相等的比較。

  • Projection:Projection 操作符是用於將需要的變數結果從變數陣列中投影出來。

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

  • Limit 和 offset:Limit 操作符會轉發特定數量的結果給變數陣列。而 offset 操作符會跳過特定數量的結果。它們一般作為操作符圖的最後幾步。

從混合系統結構圖中可以看到,每個 RP 之間並不是直接輸入輸出互聯,而是通過了一個上圖所示的半靜態路由元素(SRE)結構。論文以一個兩路複用 SRE 為例,當 succ_sel 訊號為 0 時,資料流會直接向下路由,為 1 時,會向另一側路由。SRE 的存在使得可以用更少的 RP 組成一個支援查詢範圍更大的半靜態操作符圖。

 

四、混合系統工程流程

上圖給出了混合系統的工作流程圖,可以將其分為部署階段和系統執行時。在部署階段,除了需要匯入資料之外,整個靜態邏輯必須部署在 FPGA 上,每個操作符對應的 RM 也需要提前生成並存儲在 RM 庫中。

在系統執行時,主機通過分析輸入的 SPARQL 查詢,將其解析成相應的操作符圖,檢測其是否可以用配置在 FPGA 上,如果有不支援的操作符存在,那麼會直接 CPU 端執行查詢,如果所有操作符都支援,那麼 ICAP 會選擇對應操作符的RM配置在 FPGA 的半靜態操作符圖上。主機通過 PCIe 向 FPGA 端提供輸入三元組,並接收 FPGA 端發回的結果進行後處理,FPGA 端負責具體的計算任務。

 

五、實驗結果

本文使用的是 Xilinx 的 Virtex-6 FPGA 卡和 PCIe 2.0 八通道通訊介面,在 SP2Bench 三個不同大小的資料集(66M,131M 和 262M 個三元組)上進行了實驗。下圖是他們採用的 SPARQL 查詢示例:

 

Query 1 是用到了 Filter 操作符的查詢,Query 2 是用到了 Union 操作符的查詢,Query 3-5 分別是用到了不同數量的 Join 操作符。他們在 FPGA 端部署的半靜態操作符圖如下:

最後的實驗結果表明,加入了 FPGA 的混合系統比原來的 LUPOSDATE 系統的查詢執行速度更快。並且隨著資料規模的增大,加速比會更大,說明混合系統更加適合大規模的資料集上的查詢。

 

六、總結

在這篇文章中,作者在 FPGA 上引入了半靜態運算子圖(SOG)的概念,為語義網資料庫中的查詢執行提供靈活的硬體加速器。作者沒有為給定的查詢系統執行時生成一個 FPGA 配置,而是以一定程度的靈活性部署了通用查詢結構。

SOG 由多個具有公共介面的 RP 組成。在為每個 RP 部署系統期間,會生成一組部分位檔案的 RM,並將其儲存到儲存庫中。在系統執行時,作者的混合系統針對給定的 SPARQL 查詢選擇 RM,並通過 ICAP 將其配置為 RP,RP 設定 FPGA 上運算子圖的最終結構。作為這項工作的主要貢獻,耗時的 RM 生成在系統執行時之前執行,並且訊號大大減少了查詢執行期間的重新配置。

 

END