圖數據庫中基于GPU 的圖分析計算方法

錢裳云，邵志遠，鄭 然，陳繼林

（1.華中科技大學計算機科學與技術學院，武漢 430074；2.華中科技大學服務計算技術與系統教育部重點實驗室，武漢 430074；3.華中科技大學 集群與網格計算湖北省重點實驗室，武漢 430074；4.中國電力科學研究院有限公司，北京 100192）

0 概述

隨著大數據時代的到來，用于存儲、管理和分析圖數據的圖數據庫應運而生。相較于傳統的關系型數據庫，圖數據庫使用了新穎的數據建模和存儲方法，可使檢索和分析效率提高一個甚至多個數量級［1］。圖數據庫系統對外一般支持聯機事務處理（On-Line Transaction Process，OLTP）和聯機分析處理（On-Line Analytics Process，OLAP）兩類應用。OLTP 強調對數據的增、刪、改、查，包括對圖數據庫所存儲的實體、實體屬性、實體間的關聯和圖結構等進行改動，并實現持久化存儲。OLAP 強調對數據庫內的圖數據進行分析計算，如佩奇排序（PageRank）、廣度優先查找（Breadth-First Search，BFS）等經典圖算法在全局圖上的分析操作。

雖然圖數據庫系統能夠實現對多屬性圖數據的存儲、檢索、更新和管理，支持數據的在線事務處理，但在對數據進行在線分析計算時，往往利用CPU 計算資源，采用基于分布式集群的GraphX［2］等軟件工具實現。CPU 有限的計算核心使其更適用于密集型算法，而與圖分析算法單指令多數據（Single Instruction Multiple Data，SIMD）［3］計算模式相悖。此外，使用傳統圖數據庫系統進行分析時會對數據進行重復讀取，從而消耗大量系統資源，導致較長的執行時間，同時集群間的同步也會導致額外的通信開銷。圖計算問題同樣是大數據時代的主流研究問題。目前，較新的思路是設計并使用專用的加速器，如采用圖形處理單元（Graphics Processing Unit，GPU）對圖計算進行加速。然而，這類研究考慮的對象往往是簡單圖（即只考慮圖數據的結構性數據，不考慮頂點與邊數據的屬性等信息），其只考慮計算本身的高效，脫離了具體的應用場景和應用本身的需求。從國內外發展現狀來看，現有的技術（圖數據庫和圖計算加速器）呈平行發展的趨勢，缺乏兩者之間的融合。

雖然現實世界的多屬性圖具有實體的屬性多、數據總量大、數據關系復雜等特點，但對圖數據進行的分析計算往往是基于實體的單個或幾個屬性進行。經研究發現，可以通過對數據的簡單查詢過濾將問題轉換為簡單圖分析，從而避免對大量數據的反復隨機讀取。基于此，本文提出在傳統的圖數據庫中融合GPU 圖計算加速器的思想，利用GPU 設備在圖計算上的高性能提升整體系統聯機分析處理的效率。在工程實現上，通過融合分布式圖數據庫HugeGraph［4］和典型的GPU圖計算加速器Gunrock［5］，構建新型的圖數據管理和計算系統RockGraph。該系統通過子圖提取功能從圖數據庫中提取出用戶所需數據，轉換格式后，利用JNI 工具把數據傳輸到GPU 進行在線分析，最后將得到的結果寫回圖數據庫并反饋給終端用戶。

1 相關工作

1.1 圖數據庫系統

圖數據庫普遍采用屬性圖作為數據模型。令一張屬性圖表示為G，其由頂點集合V、頂點屬性集P、頂點間的關系集合E（邊的集合）和邊的屬性集W組成。可以用四元組將G定義為：

以社交網絡圖為例，頂點V代表用戶，邊E代表用戶間的好友關系，點的屬性P代表用戶的個人信息（如昵稱、性別、年齡等），邊的屬性W代表關系的具體信息（如成為好友的時間）。

圖數據庫系統實現了對聯機事務圖的持久化存儲，對外一般支持聯機事務處理（如圖的增、刪、改、查）和聯機分析處理（如佩奇算法）。在底層存儲中，部分圖數據庫采用原生圖存儲，針對圖數據模型的特點設計了專用的棧，提高了可擴展性和其他一些性能；而另一部分則將圖數據結構化和序列化，保存到通用存儲后端中。在處理引擎方面，圖數據庫提供了查詢接口和查詢腳本語言來訪問圖數據庫。

Neo4j［6］是一種具有代表性的單機環境下的高性能圖數據庫，包含了專用于數據庫的組件，如圖查詢語言和可視化界面。Neo4j 通過交叉鏈表形式來存儲圖數據頂點、邊和對應的屬性，每個頂點都通過屬性鏈表和關系鏈表將圖數據的其他點、邊和屬性進行連接。然而，Neo4j 存在擴展性差、圖數據分析效率低等問題［7］。HugeGraph 是一種分布式圖數據庫，其支持多種后端存儲系統。該數據庫實現了Apache Tinker Pop［8］框架，能夠與以Hadoop［9］/Spark［10］為代表的工業級大數據相融合。HugeGraph 采用了Spark GraphX 的分布式圖計算模型，由于該模型利用CPU 計算資源且存在集群間同步開銷，因此圖分析算法執行性能受限于分布式系統的通信性能。

1.2 基于加速部件的圖計算引擎

由于圖數據集的擴大和圖計算不規則訪問的特性，在傳統處理器（CPU）上執行圖計算無法取得較高的效率，因此使用專門設計的加速部件（如圖形處理器GPU）進行圖計算成為了研究的熱點。GPU 采用單指令多數據流（SIMD）架構且擁有眾多的計算單元ALU，因此，能夠以極高的并行度執行圖算法。

基于加速部件（GPU）的圖計算引擎一般采用以頂點為中心的編程模型，由程序員定義頂點對應的執行函數，并在每個頂點上迭代運行，直到完成整個圖計算過程［11］。此外，GPU 的并行計算框架主要分為大規模同步并行（Bulk-Synchronous Parallel，BSP）模型和GAS（Gather-Apply-Scatter）模型。在使用BSP模型的GPU 加速圖計算系統中，大規模圖數據往往被劃分成多個分區，各圖分區對應執行用戶自定義的同一個核函數。在一個超步中，同一個核中的線程全部并行運行。在同一個核中，每個線程從上一個超步接收到消息后進行本地計算，并按需發送消息給對應頂點的鄰接點。最后，執行屏障同步，完成超步間的同步。在采用BSP編程模型的GPU 圖計算引擎中，具有代表性的有TOTEM［12］、Medusa［13］和GunRock。在GAS 模型中，頂點上的程序可分為3個階段，即收集鄰接點消息的Gather階段、調用用戶定義的應用函數的Apply 階段和將頂點新值傳遞到鄰接點的Scatter 階段。目前，常見的采用GAS 并行模型的GPU 圖計算引擎有MapGraph［14］、VertexAPI2［15］和Cusha［16］等。

2 RockGraph 系統設計

本節首先介紹圖處理系統RockGraph 的整體架構，然后具體描述主要模塊的基本框架和功能。

2.1 整體架構

RockGraph 系統架構如圖1 所示。該系統采用圖數據庫與圖計算系統相結合的架構，以傳統的大數據系統HDFS［17］和列式數據庫HBase［18］為存儲層，通過Gremlin［19］語言進行圖數據的存儲與查詢，使用新型加速部件GPU 完成大規模圖計算。RockGraph 系統可劃分為3 個主要模塊，即圖存儲模塊、遠程數據讀寫模塊和基于GPU 的圖分析模塊。

圖1 RockGraph 系統架構Fig.1 Structure of RockGraph system

2.2 圖數據存儲模塊

圖數據存儲模塊的主要目標是實現圖數據的高效存儲，將圖數據以多屬性圖的形式存儲在圖數據庫中。該模塊主要包含集群配置、數據處理、圖模式創建和多線程數據導入等功能。在導入前判斷數據庫模式與索引是否建立，若已建立則進行圖數據的導入，否則，先創建對應的圖數據庫模式與索引。為提高圖處理系統的導入效率，RockGraph 利用多線程技術實現數據的增量導入。此外，為避免導入重復的頂點數據并減少導入前判斷頂點是否存在的開銷，本文采用“先導入點，后導入邊”的方案。

2.3 圖數據讀寫模塊

圖數據讀寫模塊實現了對圖數據庫的遠程讀寫功能，是RockGraph 系統中圖數據庫與圖計算模塊間的I/O 接口，為圖分析模塊提供服務。圖數據讀寫模塊具有子圖提取和結果返回兩大功能，其基本結構如圖2 所示。在數據存儲模塊完成導入操作后，讀寫模塊利用遠程圖數據庫管理API 進行子圖提取操作，完成后將子圖文件提交給圖計算模塊。對子圖的分析任務結束后，利用圖數據讀寫模塊的結果返回功能，將計算結果寫回圖數據庫中。

圖2 圖數據讀寫模塊架構Fig.2 Structure of garph data read and writing module

在實現遠程讀數據時，用戶感興趣的往往不是完整的多屬性大圖，而是包含核心信息的子圖，因此，如何將子圖信息從龐大的圖數據庫中抽離出來便是遠程讀寫模塊面臨的首要問題。本文在RockGraph 中添加了子圖提取功能，根據用戶需求提取核心子圖并持久化保存在文本文件中。結果返回功能的實質是對圖數據庫的遠程寫入操作。得到圖分析模塊返回的結果數據后，根據結果文件中保留的數據信息在數據庫模式中構建新的屬性，將結果數據以屬性的形式插入到圖數據庫中。最后，用戶能夠通過圖數據系統中的Gremlin控制臺實現對圖計算結果的查詢。

2.4 圖數據分析模塊

圖數據分析模塊是RockGraph 系統的重要組成部分，其實現了OLAP 分析功能。相較于利用分布式平臺進行圖分析的傳統圖處理系統，RockGraph將圖分析任務交由加速部件GPU 處理。圖數據分析模塊架構如圖3 所示，其中包括數據轉換、JNI（Java Native Interface）管理和GPU 圖計算框架三個部分。

圖3 圖數據分析模塊架構Fig.3 Structure of graph data analysis module

2.4.1 圖數據預處理

在RockGraph 系統中，圖數據分析模塊將得到的子圖信息轉換成GPU 圖計算引擎所需的壓縮稀疏行（Compressed Sparse Row，CSR）格式。CSR 格式使用4 個一維數組存儲鄰接矩陣中的非零元素。其中：第1 個數組中存儲的值代表對應下標號碼的頂點的領接邊在第3 個數組中的偏移量；第3 個數組根據第1 個數組的偏移量表示對應領接點；第2 個和第4 個數組分別代表圖計算過程中頂點的屬性值和邊的權重。CSR 存儲格式實現了緊湊的數據存儲和常規內存訪問。

2.4.2 JNI 管理模塊

由于RockGraph 中對圖數據庫的交互操作使用Java 語言實現，而利用GPU 進行計算需要在Cuda 編程框架上進行，因此RockGraph 系統使用JNI 管理工具實現兩者的銜接。首先，對基于Cuda 框架的GPU圖計算引擎實現JNI 接口對應的函數，并編譯生成為動態鏈接庫。然后，利用JNI 管理工具將動態鏈接庫導入到Java 模型中，以此完成Java 環境下對C 語言程序的調用。在讀取數據時，Java 環境中的系統調用函數將數據從Java 堆傳入內存中，以供GPU 圖計算框架中的核函數使用。在寫入數據時，先將GPU圖計算得到的結果數據以數組的形式傳輸到Java 環境，再調用用戶自定義函數完成進一步分析，最后通過圖數據讀寫模塊將結果寫回圖數據庫中。

2.4.3 GPU 圖計算框架

RockGraph 采用Gunrock 圖計算引擎。然而，經由子圖提取操作得到的圖數據大小仍可能超過GPU 顯存，因此，RockGraph 對Gunrock 圖計算引擎進行擴展，使其支持超顯存計算，超顯存計算部分將在下文進行詳細介紹。Gunrock 采用了以數據為中心的大規模同步并行（BSP）模型，并以CSR格式數據作為輸入數據。在圖計算框架中，RockGraph實現了Connected Component、Single Source Shortest Path 和BFS 等基本的圖算法，因此，用戶無需學習復雜的Cuda 編程技術，利用JNI管理模塊即可調用所需的常見算法。

綜上所述，在構建圖計算加速器與圖數據庫相融的RockGraph 時，所面臨的兩個主要問題是提取用戶感興趣的核心數據和將超過顯存大小的圖數據傳輸到GPU 中進行圖計算。因此，本文在RockGraph 中分別加入子圖提取功能和超顯存GPU 圖計算框架。

3 子圖提取

在RockGraph 系統中，遠程讀寫模塊的子圖提取功能可刪除冗余數據，同時提取并存儲核心數據。下文將介紹子圖提取的目的、優點和具體操作流程。

3.1 子圖提取的目的與優點

在完成用戶的圖分析請求后，往往不需要對整張多屬性圖進行OLAP，而僅需要包含核心數據的子圖，因此，本文在RockGraph 中加入子圖提取功能。例如，對于某社交網絡的人際關系圖，教育部想分析標簽為學生的用戶間社交關系，利用子圖提取功能便可得到屬性為學生的頂點與其間的關系并組成新的子圖，持久化存儲后提交給圖計算模塊進行后續分析計算。如圖4 所示，白色節點代表標簽為學生的用戶，黑色節點代表其他類型用戶，連線代表用戶間的好友關系。由于教育部對頂點的標簽提出了篩選要求，子圖提取操作便自動生成對應對Gremlin 語句。該語句能夠實現對全圖所有頂點和邊的遍歷，提取出所有標簽為學生的點以及出點和入點均為學生的邊，并組成新的子圖。

圖4 子圖提取示例Fig.4 Example of subgraph extraction

除了為用戶提取感興趣的信息，子圖提取功能還能大幅減少后續圖計算所需的數據量，使其滿足GPU 有限的存儲空間，提高系統計算效率。

3.2 操作流程

子圖提取操作流程如圖5 所示。首先根據用戶需求檢查子圖名稱列表，判斷是否已生成過對應子圖。若存在，則直接將相應子圖導入到圖分析模塊；否則，將用戶給出的條件信息轉換為Gremlin 語言，調用遠程讀寫接口，對圖數據庫中的頂點和邊數據進行查詢和篩選。然后將篩選后提取出的子圖信息以邊表的形式持久化存儲在文本文件中。最后將包含核心信息的子圖導入到圖分析模塊進行后續分析操作。

圖5 子圖提取操作流程Fig.5 Operation process of subgraph extraction

持久化存儲子圖信息使得對同一子圖執行多次圖分析算法時無需再次對圖數據庫進行子圖提取操作，減少了冗余的全局遍歷開銷。此外，RockGraph 可根據用戶需求在圖數據庫模式中為屬性添加索引，從而提高子圖提取時對全局圖數據的遍歷和查詢速度。

4 超顯存GPU 計算

由于GPU 中的存儲空間有限，經過子圖提取操作得到的核心數據仍可能超過GPU顯存，因此RockGraph對圖計算引擎Gunrock 進行擴展，使其支持超顯存計算。RockGraph 實現超顯存GPU 計算的基本思想是把無法完整存儲到GPU 的大規模圖數據劃分為若干個適當大小的小圖，再將小圖依次循環從主存傳輸到GPU顯存中執行圖算法。每個小圖都是大圖通過一定的劃分策略得到的分區，通過對一個分區的一次傳輸與處理組成一個超步，而對每個分區完成一次超步操作，組成對全圖的一次迭代。通過多次迭代，直至所有分區收斂，最終完成圖計算任務。

綜上所述，RockGraph 實現超顯存GPU 計算的過程可以分為兩個階段，即在CPU 端完成的分區階段和由CPU-GPU 端協作完成傳輸并在GPU 完成計算任務的工作階段。下文將詳細闡釋這兩個階段，并介紹分區動態調度的優化方法。

4.1 分區階段

RockGraph 的超顯存GPU 圖計算引擎將數據分為3 種類型的數組，分別是拓撲數據（TD）、可讀寫屬性數據（WA）和只讀屬性數據（RA）。例如，除了拓撲數據之外，PageRank 還要求頂點有兩個屬性數組，即代表前一個PageRank 值的只讀屬性數組（prevPR）和代表下一個PageRank 值的可讀寫屬性數組（nextPR）。根據圖計算引擎Gunrock 采用的CSR 格式圖數據，拓撲數據對應CSR 格式中的行偏移量（row offset）和列索引（colume index）數組，以及屬性數據對應點的屬性值和邊的權重數組，并由具體算法分為只讀屬性和可讀寫屬性。

在分區階段，CPU 端實現對拓撲數據和只讀屬性數據的分區劃分，主要解決以下2 個問題：1）盡量減少預處理時間，從而減少最終端到端時間；2）劃分成合適大小的分區，使得每個分區能夠存儲到顯存中完成一次獨立計算。因此，本文在RockGraph 系統中采用邊分割和Range 分區法。本文使用一個簡單例子說明該分區方案，如圖6 所示。

圖6 分區方案示例Fig.6 Example of partition scheme

4.1.1 邊切割

在CPU 端對拓撲結構數據進行分區時，RockGraph采用邊切割的方法將頂點分為不相交的集合分別放入對應分區。邊切割具有以下優點：

1）分割后對頂點的訪問具有良好的空間位置。

2）易于將Gunrock 使用的CSR 格式數據進行劃分，并得到CSR 格式的分區。

3）無需對分區內頂點進行重新編號，減少了預處理時間。

頂點的全局ID 與本地ID 的映射關系可以表示為：

其中，Pn代表分區編號，N代表分區內頂點數，Llocal_id和Gglobal_id分別代表局部和全局頂點號。

此外，用戶也可以根據選擇對分區內頂點進行重新編號，維護一個數組實現本地頂點號與全局頂點號的映射，從而靈活地選取分區方案。

4.1.2 Range 分區

Range 分區將圖數據中的頂點根據編號分為若干個互不相交的區間。對于分區方案的選擇，通常有減少預處理時間和減少鄰接跨區點數目兩個目標。Gunrock 圖計算引擎通過頂點傳遞值，若多條跨界邊指向同一個跨區點，則只需要傳遞一組關于跨區點的值。因此，性能提升的關鍵在于減少鄰接跨區點的數目，而傳統的圖分區算法旨在減少跨界邊數量，對RockGraph 系統性能提升不明顯。因此，本文在系統中使用時空復雜度較小的Range 分區方法，從而減少最終端到端時間。

令GPU 顯存空間為|GPU|，可讀寫屬性數據大小為|WA|，為使每個分區都能在顯存中完成一次獨立計算，分區大小|Pn|應滿足以下條件：

在GPU實現循環計算分區之初，將可讀寫數據WA從主機端拷貝到GPU，并在迭代圖算法完成前在顯存中實現屬性數據的更新。因此，分區大小應當小于兩者之差。此階段的具體流程將在下文進行介紹。

4.2 工作流程

經過分區階段的小圖劃分后，RockGraph 將分區循環傳輸到GPU 中執行圖算法。超顯存GPU 圖計算工作流程如圖7 所示，具體步驟如下：

圖7 超顯存GPU 計算工作流程Fig.7 Workflow of out-of-memory GPU computation

步驟1在CPU 中對WA 進行初始化。

步驟2將全部頂點的可讀寫屬性WA拷貝到GPU存儲空間中。此后，WA 數據的更新操作均在顯存中完成，這將減少每個分區將更新后數據寫回CPU 內存的通信開銷。由于現有的GPU 顯存最高可達24 GB，可存儲60 億頂點的INT 類型屬性值，因此完全滿足現實世界圖數據處理的需要。

步驟3使用動態調度法，根據活躍頂點表將活躍分區調入GPU 顯存中。

步驟4調用Gunrock 計算引擎中的核函數，根據分區中的拓撲數據TD 和屬性數據執行對應圖算法，更新可讀寫屬性WA，得到WA’。

步驟5根據步驟4 所得結果更新活躍頂點表。當一次迭代完成后，將新的活躍頂點表傳輸到主存中，并更新CPU 中對應的活躍頂點表。

若主機端檢測到活躍分區，則重復步驟3～步驟5，將活躍分區循環傳輸到GPU 中進行計算。當檢測不到任何活躍分區（即滿足所有分區收斂）時，將頂點屬性數據拷貝回CPU 主存中，得到最終結果。

4.3 動態調度

對于某些算法，一次迭代過程中只有部分點需要進行更新計算（如BFS 算法，每次迭代開始時只需要計算上次迭代中訪問到的鄰接點）。本文將本次迭代計算開始時所需要的點稱為活躍頂點，將包含有活躍頂點的分區稱為活躍分區。如果采用固定的調度順序，每次迭代都將全部分區依次傳輸到GPU中，使得不活躍的分區也調入GPU，會造成多余的通信和計算開銷。因此，RockGraph 采用動態調度策略，通過維護一個布爾類型的數組跟蹤活躍頂點，每次迭代只向GPU 傳輸含有活躍頂點的活躍分區。

圖8 展示了使用一個布爾數組判斷活躍頂點和活躍分區的方法。該數組的大小為全圖頂點數，活躍頂點的對應值置為1，否則為0。若分區含有活躍頂點，則該分區對應值為1，記為活躍分區。在每次向GPU 調入分區前，先檢查CPU 端的活躍點數組，依次將活躍分區傳輸到GPU 執行圖算法。對分區的計算完成后，更新GPU 中的活躍點數組。當一次迭代完成后，將新的布爾數組傳輸回CPU，更新CPU端活躍頂點表，并準備下一次迭代的分區傳輸。

圖8 活躍頂點表Fig.8 Table of active vertices

5 實驗與結果分析

5.1 實驗環境

在本實驗中，RockGraph 和對比系統GraphX 部署在3 臺服務器組成的集群系統中。每臺服務器配備8 核Intel i7 處理器，內存為256 GB，磁盤空間為3 TB，操作系統為Ubuntu14。此外，RockGraph 使用GPU 作為圖計算加速器，型號為Tesla-P100，顯存為16 GB，Cuda 版本為10.0。

實驗選取4 組公開數據集和2 組人工生成的隨機數據集，以分布式計算框架GraphX 為對比，對廣度優先算法（BFS）［20］、單源最短路徑算法（SSSP）［21］和聯通區間算法（CC）［22］這三種常用的圖算法進行分析。

數據集的基本信息如表1 所示，其中，4 組公開數據集（WikiTalk、Topcat、Pokec 和LiveJournal）來源于真實世界社交網絡，尺寸均小于顯存，而兩組隨機數據集（RMAT1 和RMAT2）的規模則超出了顯存容量，RockGraph 需要采用超顯存GPU 計算框。本文使用以上兩類數據分別分析圖數據庫中GPU 對圖計算性能的影響和超顯存GPU 計算框架的性能。

表1 數據集基本信息Table 1 Basic information of datasets

5.2 GPU 對圖計算性能的影響

如圖9～圖11 所示，RockGraph 中3 種圖算法的平均執行時間都大幅低于GraphX，性能平均提升了約5 倍。這是因為RockGraph 采用的圖計算加速器GPU 擁有眾多計算單元，且采用SIMD 計算模式，相較于僅使用3 臺服務器上CPU 的GraphX 并行度更高，更適合對迭代算法的計算，因此其在執行3 種常見的圖算法時，性能提升非常明顯。同時，隨著數據集規模的增長，GraphX 的執行時間急劇增長，而RockGraph 呈線性增長。數據集規模的擴大導致GraphX 集群間通信開銷增大。此外，集群系統的并行度依舊維持相對較低的水平，數據集的擴大使得算法的串行執行時間也大幅增加。所以，GraphX 的執行時間隨數據集規模擴大而大幅增加。然而，當數據集足夠容納進顯存時，利用GPU 進行圖計算沒有分區劃分與傳輸時間。同時，由于GPU 并行度更高，數據集規模的擴大對執行時間的影響較小。因此，數據規模越大，GPU 加速圖計算的效果越明顯。

圖9 BFS 算法執行時間Fig.9 Runtime of BFS algorithm

圖10 SSSP 算法執行時間Fig.10 Runtime of SSSP algorithm

圖11 CC 算法執行時間Fig.11 Runtime of CC algorithm

5.3 超顯存GPU 計算框架性能分析

當數據集規模擴大到無法存儲到顯存中時，RockGraph 采用超顯存GPU 計算框架，將數據劃分為若干個分區后，依次循環傳輸到GPU 中執行圖算法。因此，RockGraph 執行時間中增加了分區劃分和傳輸時間，并且數據集越大，分區數量越多，導致分區劃分時間增加，同時，完成一次迭代所需的傳輸時間占比也相應增加。

如圖12～圖14 所示，對于不同算法，GraphX 的執行時間約為RockGraph 的3 倍～5 倍。RockGraph圖計算性能雖然仍高于GraphX，但相較于計算無需采用超顯存的數據集時，提升幅度明顯下降。同時還可以看出，RockGraph 對BFS 和SSSP 算法性能提升比CC 算法更加明顯，這是由于BFS 和SSSP 算法每次迭代時無需所有頂點進行計算，因此可以使用動態分區調度策略進行優化，減少每次迭代過程中需要傳輸和計算的分區，從而減少執行時間。

圖12 BFS 算法執行時間（使用超顯存計算）Fig.12 Runtime of BFS algorithm（using out-of-memory computation）

圖13 SSSP 算法執行時間（使用超顯存計算）Fig.13 Runtime of SSSP algorihm（using out-of-memory computation）

圖14 CC 算法執行時間（使用超顯存計算）Fig.14 Runtime of CC algorithm（using out-of-memory computation）

上述實驗結果表明，在普遍情況下，無論是否采用超顯存計算框架，GPU 都能大幅提高圖數據庫的圖分析算法速度。

6 結束語

為提高圖數據在線分析性能，本文設計并實現了利用GPU 加速圖計算的圖數據庫系統RockGraph。該系統配置子圖提取功能，能夠從圖數據庫中提取出用戶感興趣的核心信息，從而減少計算量。在對提取出的數據進行格式轉換后，其利用JNI工具將數據傳輸到GPU，并采用超顯存圖計算框架進行在線分析，最后把得到的分析結果寫回圖數據庫中。實驗結果表明，相較于傳統圖數據庫系統采用的計算引擎GraphX，基于GPU 進行圖計算的RockGraph 速度大幅提升。下一步將利用異步多流方式提高超顯存GPU 的計算性能。