圖數(shù)據(jù)庫中基于GPU 的圖分析計算方法

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

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

0 概述

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

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

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

1 相關(guān)工作

1.1 圖數(shù)據(jù)庫系統(tǒng)

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

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

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

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

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

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

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

2 RockGraph 系統(tǒng)設(shè)計

本節(jié)首先介紹圖處理系統(tǒng)RockGraph 的整體架構(gòu)，然后具體描述主要模塊的基本框架和功能。

2.1 整體架構(gòu)

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

圖1 RockGraph 系統(tǒng)架構(gòu)Fig.1 Structure of RockGraph system

2.2 圖數(shù)據(jù)存儲模塊

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

2.3 圖數(shù)據(jù)讀寫模塊

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

圖2 圖數(shù)據(jù)讀寫模塊架構(gòu)Fig.2 Structure of garph data read and writing module

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

2.4 圖數(shù)據(jù)分析模塊

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

圖3 圖數(shù)據(jù)分析模塊架構(gòu)Fig.3 Structure of graph data analysis module

2.4.1 圖數(shù)據(jù)預(yù)處理

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

2.4.2 JNI 管理模塊

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

2.4.3 GPU 圖計算框架

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

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

3 子圖提取

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

3.1 子圖提取的目的與優(yōu)點

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

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

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

3.2 操作流程

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

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

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

4 超顯存GPU 計算

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

綜上所述，RockGraph 實現(xiàn)超顯存GPU 計算的過程可以分為兩個階段，即在CPU 端完成的分區(qū)階段和由CPU-GPU 端協(xié)作完成傳輸并在GPU 完成計算任務(wù)的工作階段。下文將詳細闡釋這兩個階段，并介紹分區(qū)動態(tài)調(diào)度的優(yōu)化方法。

4.1 分區(qū)階段

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

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

圖6 分區(qū)方案示例Fig.6 Example of partition scheme

4.1.1 邊切割

在CPU 端對拓撲結(jié)構(gòu)數(shù)據(jù)進行分區(qū)時，RockGraph采用邊切割的方法將頂點分為不相交的集合分別放入對應(yīng)分區(qū)。邊切割具有以下優(yōu)點：

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

2）易于將Gunrock 使用的CSR 格式數(shù)據(jù)進行劃分，并得到CSR 格式的分區(qū)。

3）無需對分區(qū)內(nèi)頂點進行重新編號，減少了預(yù)處理時間。

頂點的全局ID 與本地ID 的映射關(guān)系可以表示為：

其中，Pn代表分區(qū)編號，N代表分區(qū)內(nèi)頂點數(shù)，Llocal_id和Gglobal_id分別代表局部和全局頂點號。

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

4.1.2 Range 分區(qū)

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

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

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

4.2 工作流程

經(jīng)過分區(qū)階段的小圖劃分后，RockGraph 將分區(qū)循環(huán)傳輸?shù)紾PU 中執(zhí)行圖算法。超顯存GPU 圖計算工作流程如圖7 所示，具體步驟如下：

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

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

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

步驟3使用動態(tài)調(diào)度法，根據(jù)活躍頂點表將活躍分區(qū)調(diào)入GPU 顯存中。

步驟4調(diào)用Gunrock 計算引擎中的核函數(shù)，根據(jù)分區(qū)中的拓撲數(shù)據(jù)TD 和屬性數(shù)據(jù)執(zhí)行對應(yīng)圖算法，更新可讀寫屬性WA，得到WA’。

步驟5根據(jù)步驟4 所得結(jié)果更新活躍頂點表。當一次迭代完成后，將新的活躍頂點表傳輸?shù)街鞔嬷?，并更新CPU 中對應(yīng)的活躍頂點表。

若主機端檢測到活躍分區(qū)，則重復(fù)步驟3～步驟5，將活躍分區(qū)循環(huán)傳輸?shù)紾PU 中進行計算。當檢測不到任何活躍分區(qū)（即滿足所有分區(qū)收斂）時，將頂點屬性數(shù)據(jù)拷貝回CPU 主存中，得到最終結(jié)果。

4.3 動態(tài)調(diào)度

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

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

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

5 實驗與結(jié)果分析

5.1 實驗環(huán)境

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

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

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

表1 數(shù)據(jù)集基本信息Table 1 Basic information of datasets

5.2 GPU 對圖計算性能的影響

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

圖9 BFS 算法執(zhí)行時間Fig.9 Runtime of BFS algorithm

圖10 SSSP 算法執(zhí)行時間Fig.10 Runtime of SSSP algorithm

圖11 CC 算法執(zhí)行時間Fig.11 Runtime of CC algorithm

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

當數(shù)據(jù)集規(guī)模擴大到無法存儲到顯存中時，RockGraph 采用超顯存GPU 計算框架，將數(shù)據(jù)劃分為若干個分區(qū)后，依次循環(huán)傳輸?shù)紾PU 中執(zhí)行圖算法。因此，RockGraph 執(zhí)行時間中增加了分區(qū)劃分和傳輸時間，并且數(shù)據(jù)集越大，分區(qū)數(shù)量越多，導(dǎo)致分區(qū)劃分時間增加，同時，完成一次迭代所需的傳輸時間占比也相應(yīng)增加。

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

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

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

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

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

6 結(jié)束語

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